当前位置：首页 > news >正文

leetcode 3224. 使差值相等的最少数组改动次数

news 来源：原创 2025/7/1 22:54:11

题目链接：3224. 使差值相等的最少数组改动次数

题目：

给你一个长度为 n 的整数数组 nums ，n 是偶数，同时给你一个整数 k 。

你可以对数组进行一些操作。每次操作中，你可以将数组中任一元素替换为 0 到 k 之间的任一整数。

执行完所有操作以后，你需要确保最后得到的数组满足以下条件：

存在一个整数 X ，满足对于所有的 (0 <= i < n) 都有 abs(a[i] - a[n - i - 1]) = X 。
请你返回满足以上条件最少修改次数。

提示：

2 <= n == nums.length <= 105

n 是偶数

0 <= nums[i] <= k <= 105

题解：

方法一：暴力解法

直接枚举 X 的取值，然后计算每个枚举值对应所需修改的次数，然后选出里面最小的即可。

这里的第一个问题是 X 的取值范围如何确定。从题目的提示内容可知数组中的数在 0-k 之间，又因为数组中的数字可以修改为 0-k之间的任意数，所以直接上 X 的取值范围为 0 <= X <= k

第二个问题是如何让数组中对称位置的两个数字在修改之后差值为 X，这里直接枚举两个数字可以修改的所有值，如果修改前后的数值不同则记录为1次修改，否则不记录为修改。

代码实现：

def minChanges(nums, k):n = len(nums)change_count = [0] * (k + 1)# 遍历前半部分for i in range(n // 2):a, b = nums[i], nums[n - i - 1]temp = [float('inf')] * (k + 1)  # 临时数组，用于计算当前的最小修改次数# 遍历每个可能的 Xfor x in range(k + 1):# 当前 |a - b| 与目标 X 的差异for v1 in range(k + 1):  # 枚举将 a 修改为 v1for v2 in range(k + 1):  # 枚举将 b 修改为 v2if abs(v1 - v2) == x:  # 如果调整后符合要求cost = (v1 != a) + (v2 != b)  # 计算修改次数temp[x] = min(temp[x], change_count[x] + cost)# 更新最小修改次数change_count = tempreturn min(change_count)

方法二：差分数组

注意到每一对数不会互相影响，所以可以把每一对数分开考虑。
设一对数中，一个是 $x$ ，一个是 $y$ ，那么改掉其中一个数可以获得的最大差值，肯定是把另一个数改成 0 或 k，即最大差值：

$m = ma x (x, k - x, y, k - y)$

参考下表：

x	y	差值
x	0	x
x	k	k-x
0	y	y
k	y	k-y

改掉两个数，那就可以获得从 0 到 k 里的任意差值。

所以对于这一对数来说， $X = ∣ x - y ∣$ 时不需要操作， $\leq X < |x-y|$ 以及 $\leq m$ 的时候需要一次操作， $X > m$ 的时候需要两次操作。

枚举所有数对，用差分数组维护 $X$ 的某个取值需要几次操作即可。复杂度 $O (n + k)$ 。

我们令 $d = ab s (n u m s [i] - n u m s [j])$ ，假如最后的这个 $\leq X < |x-y|$ ，那么就可以通过一次操作完成。
操作一次能达到的最大差值是多少呢？这个就是上面说的肯定是把另一个数改成 0 或 k。即最大差值为 $m = ma x (x, k - x, y, k - y)$ ，那么就是 $\leq m$ 时需要一次操作。
剩下就是 $X > m$ 时需要两次操作。

因为是对区间内的值进行统一的加一个常数的操作，如果一个一个操作的话时间复杂度为 $O (n)$ ，所以使用了差分数组，这样可以将时间复杂度降为 $O (1)$

from typing import Listclass Solution:def minChanges(self, nums: List[int], k: int) -> int:n = len(nums)f = [0] * (k + 2)i, j = 0, n - 1while i < j:d = abs(nums[i] - nums[j])ma = max(nums[i], k - nums[i], nums[j], k - nums[j])# 0 <= x < d 时需要一次操作，如果没有用差分数组的话就成了 cnt[0]+1,cnt[1]+1,···,cnt[d]+1f[0] += 1f[d] -= 1# d < x <= ma 时需要一次操作f[d + 1] += 1f[ma + 1] -= 1# x > ma 时需要两次操作f[ma + 1] += 2i += 1j -= 1ans = f[0]for i in range(1, k + 2):f[i] += f[i - 1]ans = min(ans, f[i])return ans

参考1：3224. 使差值相等的最少数组改动次数
参考2：前缀和&差分

leetcode 3224. 使差值相等的最少数组改动次数

题目链接：3224. 使差值相等的最少数组改动次数题目： 给你一个长度为 n 的整数数组 nums ，n 是偶数 ，同时给你一个整数 k 。你可以对数组进行一些操作。每次操作中，你可以将数组中任一元素替换为 0 到 k 之间的任一…...

编程日记 2025/7/1 22:54:11

C# 小案例(IT资产管理系统)

开发工具：visual studio 2022 语言：C# 数据库：Sql Server 2008 页面展示一、登录二、主窗体三、用户管理四、资产管理五、关于 Java版地址：基于若依开发物品管理系统(springbootvue)_若依物品管理系统-CSDN博客 Python版…...

编程日记 2025/7/1 22:48:26

React第十四节useState使用详解差异

一、useState() Hook 使用 useState视图更新用法 1、写法： import { useState } from react const [name, setName] useState(Andy)利用数组解构写法， 第一个参数是自定义的属性，用于初始化时候渲染，如上面代码，初…...

编程日记 2025/6/30 20:39:44

1. 准备工作 1.1系统更新 sudo apt update sudo apt upgrade -y 1.2 检查系统版本 lsb_release -a 2.安装docker 2.1. 安装依赖 sudo apt install apt-transport-https ca-certificates curl software-properties-common 2.2 添加docker 官方GPG密钥 curl -fsSL https…...

编程日记 2025/7/1 22:46:10

图书管理系统｜Java｜SSM｜JSP｜前后端分离

【一】可以提供远程部署安装，包扩环境【二】提供软件相关的安装包【三】如果需要提供java入门资料可咨询【技术栈】 1⃣️：架构: B/S、MVC 2⃣️：系统环境：Windowsh/Mac 3⃣️：开发环境：IDEA、JDK1.8、M…...

编程日记 2025/7/1 15:55:22

Apache Echarts和POI

目录 Apache ECharts 介绍入门绘制一个简单的图表 Apache POI 介绍通过POI创建Excel文件并且写入文件内容通过POI读取Excel文件中的内容导出Excel表格 Apache ECharts 介绍 Apache ECharts 是一款基于 Javascript 的数据可视化图表库，提供直观&#xf…...

编程日记 2025/6/28 18:12:28

ubuntu下的chattts 学习8（结束）：长文本的语音转换优化及总结

代码 import ChatTTS import torch import numpy as np import torchaudio import re# 设置环境变量以避免内存碎片化 import os os.environ[PYTORCH_CUDA_ALLOC_CONF] expandable_segments:True# 使用 CPU 进行计算 device torch.device(cpu)chat ChatTTS.Chat() chat.loa…...

编程日记 2025/7/1 14:45:07

Luckysheet 实现 excel 多人在线协同编辑（全功能实现增强版）

前言感谢大家对 Multi person online edit(多人在线编辑器) 项目的支持，mpoe 项目使用 quill、luckysheet、canvas-editor 实现的 md、excel、word 在线协同编辑，欢迎大家Fork 代码，多多 Start哦~ Multi person online edit 多人协同编辑器…...

编程日记 2025/7/1 4:04:47

GitHub使用

太久不用GitHub发现自己又有些不会了，突发奇想为何不把每次看到的有指导意义的博客收录一下以便下次查阅呢如何上传文件夹到GitHub上（配图详解）？_github上傳資料夾-CSDN博客 github上如何删除自己的仓库_github删除仓库-CSDN博…...

编程日记 2025/7/1 15:47:55

阿里云服务器Linux(centos)系统安装nginx1.20.2

阿里云服务器Linux(centos)系统安装nginx1.20.2 1.安装依赖包一共要安装4种依赖（基于c语言） yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel2.下载nginx安装包并解压安装包 nginx官网下载：http://nginx.org/en/do…...

编程日记 2025/7/1 9:52:50

linux 用户名密码设置

安装linux时默认的密码最小长度是5个字节，但这并不够，要把它设为8个字节。修改最短密码长度需要编辑login.defs文件#vi /etc/login.defs PASS_MAX_DAYS 99999 #＃密码设置最长有效期（默认值) PASS_MIN_DAYS 0 ##密…...

编程日记 2025/7/1 1:24:05

MySQL是否可以配合Keepalived实现高可用

MySQL是否可以配合Keepalived实现高可用是的，MySQL 可以配合 Keepalived 实现高可用性。通常，使用 Keepalived 与 MySQL 配合的方式主要是通过配置虚拟IP（VIP） 来实现主从数据库的自动切换，从而保证在主数据库宕机时…...

编程日记 2025/6/28 19:29:51

windows下 mysql开启 binlog日志

一、查看是否开启 binlog -- 方式一 show binary logs;-- 方式二 show VARIABLES like log_bin 说明没有开启方式一 ：you are not using binary logging 方式二：log_bin off 二、编辑 my.ini 配置文件默认安装地点位于：C:\ProgramDat…...

编程日记 2025/7/1 15:56:29

59. 螺旋矩阵 II

59. 螺旋矩阵 II class Solution { public:vector<vector<int>> generateMatrix(int n) {// for(int i0;i<n;i){ 这样的遍历方式不对// for(int j 0;j<n;j){// generateMatrix[i][j] // }// } //初始化矩阵vector<vector<int&…...

编程日记 2025/7/1 22:44:06

XML 查看器：深入理解与高效使用

XML 查看器：深入理解与高效使用 XML（可扩展标记语言）是一种用于存储和传输数据的标记语言。它通过使用标签来定义数据结构，使得数据既易于人类阅读，也易于机器解析。在本文中，我们将探讨 XML 查看器的功能…...

编程日记 2025/7/1 15:28:06

JDBC学习

配置文件 application.yml spring: datasource: username: root password: 123456 url: jdbc:mysql://localhost:3306/rbac?useUnicodetrue&characterEncodingutf-8&serverTimezoneUTC driver-class-name: com.mysql.jdbc.Driverrbac为我自己本地的数据库&…...

编程日记 2025/7/1 16:03:21

单元测试

junit5中五个方法为：Test、BeforeEach（修饰实例方法，在测试方法开始之前执行）、AfterEach（修饰实例方法，在测试方法完成之后开始执行）、BeforeAll（修饰静态static方法，在…...

编程日记 2025/7/1 9:47:00

24/12/9 算法笔记＜强化学习＞ PPO,DPPO

PPO是目前非常流行的增强学习算法，OpenAI把PPO作为目前baseline算法，首选PPO，可想而知，PPO可能不是最强的，但是是最广泛的。 PPO是基于AC架构，因为AC架构有一个好处，就是解决了连续动作空间的问…...

编程日记 2025/6/28 13:35:23

spring boot通过连接池的方式连接时序库IotDB

1、maven依赖 <dependency><groupId>org.apache.iotdb</groupId><artifactId>iotdb-session</artifactId><version>1.3.2</version></dependency>2、配置文件 iotdb:server:url: localhostport: 6667name: rootpwd: rootmax…...

编程日记 2025/7/1 15:59:46

maven多模块开发

目录聚合可选依赖排除依赖属性打包聚合聚合就是将多个模块组成一个整体，进行项目构建。聚合工程（也称为多模块项目）是 Maven 的一种项目结构，它允许将一个大型项目拆分为多个较小的、更易于管理的子模块。每个子模块…...

编程日记 2025/7/1 15:32:14

Kubernetes Nginx-Ingress | 禁用HSTS/禁止重定向到https

目录前言禁用HSTS禁止重定向到https关闭 HSTS 和设置 ssl-redirect 为 false 的区别前言客户请求经过ingress到服务后，默认加上了strict-transport-security，导致客户服务跨域请求失败，具体Response Headers信息如下； 分析 n…...

编程日记 2025/7/1 11:28:02

华为eNSP：VRRP

一、VRRP背景概述在现代网络环境中，主机通常通过默认网关进行网络通信。当默认网关出现故障时，网络通信会中断，影响业务连续性和稳定性。为了提高网络的可靠性和冗余性，采用虚拟路由冗余协议（VRRP）是一种…...

编程日记 2025/7/1 11:22:10

linux 安装composer

下载composer curl -sS https://getcomposer.org/installer | php下载后设置环境变量，直接通过命令composer -v mv composer.phar /usr/local/bin/composer查看版本看是否安装成功 composer -v...

编程日记 2025/6/28 13:34:59

ESP32-S3模组上跑通ES8388（24）

接前一篇文章：ESP32-S3模组上跑通ES8388（23）二、利用ESP-ADF操作ES8388 2. 详细解析上一回解析完了es8388_init函数中的第8段代码，本回继续往下解析。为了便于理解和回顾，再次贴出es8388_init函数源码，在components\audio_hal\driver\es8388\es8388.c中，如下： …...

编程日记 2025/7/1 16:28:36

类文件具有错误的版本 61.0, 应为 55.0 请删除该文件或确保该文件位于正确的类路径子目录中。

类文件具有错误的版本 61.0, 应为 55.0 请删除该文件或确保该文件位于正确的类路径子目录中。这个错误表明你的项目尝试加载的 .class 文件（编译好的 Java 类）是用比你的运行环境支持更高版本的 Java 编译的。具体来说： 版本 61.0 对应 Ja…...

编程日记 2025/6/28 19:35:40

AI 的时代，新科技和新技术如何推动跨学科的整合？

在当前AI的发展中，我们面临的一个主要挑战就是融合的问题，这实际上不仅是技术上的融合，还有更深层次的哲学层面的思考。或许在中国这方面的讨论较少，但在西方哲学和神学的语境中，探讨万物的根本和不同学科之间的联系…...

编程日记 2025/7/1 16:21:26

12.9-12.16学习周报

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录摘要Abstract一、SNN与传统ANN的比较1.SNN概述2.SNN神经元和ANN的比较结构3.spikingjelly1.数据格式2.状态的保存和重置3.传播模式4.神经元二、图数据库1.图数据库…...

编程日记 2025/6/28 18:28:24

CanFestival移植到STM32 F4芯片(基于HAL库)

本文讲述如何通过简单操作就可以把CanFestival库移植到STM32 F4芯片上，作为Slave设备。使用启明欣欣的工控板来做实验。一硬件连接观察CAN报文需要专门的设备，本人从某宝上买了一个兼容PCAN的开源小板子，二十几块钱，通过USB接…...

编程日记 2025/6/28 19:45:03

构建安全的数据库环境：群晖NAS安装MySQL和phpMyAdmin详细步骤

文章目录前言1. 安装MySQL2. 安装phpMyAdmin3. 修改User表4. 本地测试连接MySQL5. 安装cpolar内网穿透6. 配置MySQL公网访问地址7. 配置MySQL固定公网地址8. 配置phpMyAdmin公网地址9. 配置phpmyadmin固定公网地址前言本文将详细讲解如何在群晖NAS上安装MySQL及其数据库管理…...

编程日记 2025/7/1 15:31:27

相机（Camera）硬件组成详解

简介：个人学习分享，如有错误，欢迎批评指正。写在前面：可以去B站观看一些相机原理的视频来配合学习，这里推荐：推荐1，推荐2，推荐3 相机（Camera）是一种复杂的光…...

编程日记 2025/6/30 19:17:47

【Linux———基础IO】

每一滴眼泪，每一次心碎，什么爱能无疚无悔.......................................................................... 文章目录前言一、【认识文件I/O】 1.1、【回顾C语言文件I/O】 1.2、【操作系统文件I/O】 1.2.1、【open函数】 1、【open函数的三…...

编程日记 2025/6/28 18:11:38

WebRTC服务质量（03）- RTCP协议

一、前言： RTCP（RTP Control Protocol）是一种控制协议，与RTP（Real-time Transport Protocol）一起用于实时通信中的控制和反馈。RTCP负责监控和调节实时媒体流。通过不断交换RTCP信息，WebRTC应用…...

编程日记 2025/6/28 18:47:39

[python SQLAlchemy数据库操作入门]-10.性能优化：提升 SQLAlchemy 在股票数据处理中的速度

哈喽，大家好，我是木头左！当处理大量数据时，如股票数据，默认的ORM操作可能会显得效率低下。本文将探讨如何通过一些技巧和策略来优化SQLAlchemy ORM的性能，从而提升其在股票数据处理中的速度。 1. 选择合适的数据类型在定义模型时，选择合适的数据类型对于性能至关重要…...

编程日记 2025/6/28 18:07:27

23种设计模式之中介者模式

目录 1. 简介2. 代码2.1 Mediator （中介者接口）2.2 ChatRoom （具体中介者类）2.3 User （同事接口）2.4 ChatUser （具体同事类）2.5 Test （测试）2.6 运行结果 3. …...

编程日记 2025/7/1 15:46:12

MySQL:GROUP_CONCAT分组合并

目录一、概述二、用法三、分组去重一、概述 GROUP_CONCAT函数要配合group by才能发挥作用，主要用于分组之后合并某一字段。二、用法 SELECT GROUP_CONCAT(age) FROM tb_user GROUP BY banner;三、分组去重 SELECT GROUP_CONCAT(DISTINCT age) FROM tb_user GRO…...

编程日记 2025/7/1 14:59:13

递归方式渲染嵌套的菜单项

1. 递归组件递归方式渲染嵌套的菜单项，这个是非常好的做法。为了避免在每个子菜单上都渲染一个新的 <ul> 标签，可以使用 v-if 来判断是否有子菜单，再决定是否渲染子菜单的部分。 2. 提高性能对于递归渲染组件，Vue 可能…...

编程日记 2025/7/1 16:29:33

常用Vim操作

vimrc配置 ctags -R * 生成tags文件 set number set ts4 set sw4 set autoindent set cindent set tag~/tmp/log/help/tags 自动补全： ctrln：自动补全输入： a：从当前文字后插入i：从当前文字前插入s: 删除当前字…...

编程日记 2025/7/1 12:28:19

spark3 sql优化：同一个表关联多次，优化方案

目录 1.合并查询2.使用 JOIN 条件的过滤优化3.使用 Map-side Join 或 Broadcast Join4.使用 Partitioning 和 Bucketing5.利用 DataFrame API 进行优化假设 A 和 B 已经加载为 DataFramePerform left joins with specific conditions6.使用缓存或持久化7.避免笛卡尔积总结 1.合…...

编程日记 2025/7/1 11:34:53

XML 在线格式化 - 加菲工具

XML 在线格式化打开网站加菲工具选择“XML 在线格式化” 输入XML，点击左上角的“格式化”按钮得到格式化后的结果...

编程日记 2025/6/28 20:05:19

陪玩系统小程序源码/游戏陪玩APP系统用户端有哪些功能？游戏陪玩小程序APP源码开发

多客陪玩系统-游戏陪玩线下预约上门服务等陪玩圈子陪玩社区系统源码陪玩系统源码，高质量的陪玩系统源码，游戏陪玩APP源码开发，语音陪玩源码搭建: 线上陪玩活动组局与线下家政服务系统的部署需要综合考虑技术选型、开发流程、部署流程、功能实…...

编程日记 2025/7/1 16:49:26

力扣-图论-9【算法学习day.59】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非…...

编程日记 2025/7/1 16:03:24

ViT学习笔记（三） RepViT和TransNext简介

标准ViT的其他模块的功能以及源码解读，在CSDN上有很多优秀文章，参考文章将代码大致过一遍。像我这种只做工程不写论文的，个人认为大致明白就好，用不着特别细究。下面跟踪两个ViT比较新的变种继续深入学习一下：RepViT和…...

编程日记 2025/6/28 19:29:07

大华DSS数字监控系统 attachment_downloadAtt.action 任意文件下载漏洞复现

0x01 产品描述：大华 DSS 数字监控系统是大华开发的一款安防视频监控系统，拥有实时监视、云台操作、录像回放、报警处理、设备管理等功能。0x02 漏洞描述：大华DSS数字监控系统 attachment_downloadAtt.action接口存在任意文件读取漏洞，未经身份验证攻击者可通过该漏洞读取…...

编程日记 2025/7/1 4:26:30

Dockerfile容器镜像构建技术

文章目录 1、容器回顾1_容器与容器镜像之间的关系2_容器镜像分类3_容器镜像获取的方法 2、其他容器镜像获取方法演示1_在DockerHub直接下载2_把操作系统的文件系统打包为容器镜像3_把正在运行的容器打包为容器镜像 3、Dockerfile介绍4、Dockerfile指令1_FROM2_RUN3_CMD4_EXPOSE…...

编程日记 2025/6/28 18:07:30

LabVIEW实现MQTT通信

目录 1、MQTT通信原理 2、硬件环境部署 3、云端环境部署 4、程序架构 5、前面板设计 6、程序框图设计 7、测试验证本专栏以LabVIEW为开发平台，讲解物联网通信组网原理与开发方法，覆盖RS232、TCP、MQTT、蓝牙、Wi-Fi、NB-IoT等协议。结合实际案例，展示如何利用LabVIEW和常用…...

编程日记 2025/7/1 20:22:17

分布式事物XA、BASE、TCC、SAGA、AT

分布式事务——Seata 一、Seata的架构： 1、什么是Seata： 它是一款分布式事务解决方案。官网查看：Seata 2.执行过程在分布式事务中，会有一个入口方法去调用各个微服务，每一个微服务都有一个分支事务，因…...

编程日记 2025/7/1 7:35:09

[创业之路-182]：《华为战略管理法-DSTE实战体系》-1-华为的发展历程和战略管理演变

目录前言、华为在战略管理上做对了什么？ 1、前瞻性的战略眼光 2、有效的战略解码 3、灵活的战略调整 4、注重创新和研发 5、以客户为中心的战略导向 6、完善的内部管理体系一、华为不同时期的战略选择 1.1 华为不同时期的战略选择 1、创业初期&#xff…...

编程日记 2025/6/28 9:14:06

python爬虫--小白篇【爬取B站视频】

目录一、任务分析二、网页分析三、任务实现一、任务分析将B站视频爬取并保存到本地，经过分析可知可以分为四个步骤，分别是： 爬取视频页的网页源代码；提取视频和音频的播放地址；下载并保存视频和音频&#x…...

编程日记 2025/6/30 5:31:43

web 自动化 selenium

1、下载Chrome对应的driver版本我的chrome是 131.0.6778.109，我下载的driver是131.0.6778.69（想找一模一样的，但是没有） https://googlechromelabs.github.io/chrome-for-testing/ chromedriver下载 2、配置Chrome deriver及 …...

编程日记 2025/6/28 18:07:36

相关文章：