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

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

题目链接: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 x x,一个是 y y y,那么改掉其中一个数可以获得的最大差值,肯定是把另一个数改成 0 或 k,即最大差值:

m = m a x ( x , k − x , y , k − y ) m=max(x, k-x, y, k-y) m=max(x,kx,y,ky)

参考下表:

xy差值
x0x
xkk-x
0yy
kyk-y

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

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

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

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

因为是对区间内的值进行统一的加一个常数的操作,如果一个一个操作的话时间复杂度为 O ( n ) O(n) O(n),所以使用了差分数组,这样可以将时间复杂度降为 O ( 1 ) O(1) 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. 使差值相等的最少数组改动次数

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

多线程动态库里面调用静态库分配内存函数导致的崩溃cltp汇编指令导致

1、概述 有这样的一个场景,我有一个动态库myso.so里面有函数start_crash()&#xff0c;用到静态库的内存分配函数&#xff0c;其实静态库里面的static.a 里面就封装了一个函数叫system_malloc(),函数返回的是分配的内存地址&#xff0c;然后发现&#xff0c;我在测试demo里面创…...

力扣刷题TOP101: 31.BM38 在二叉树中找到两个节点的最近公共祖先

目录&#xff1a; 目的 思路 复杂度 记忆秘诀 python代码 目的&#xff1a; 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2&#xff0c;请找o1 和 o2 的最近公共祖先节点。 思路 这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类…...

前端项目打包部署

打包和部署前端项目是将开发环境中的代码转化为生产环境可直接运行的静态文件&#xff0c;并将其部署到服务器上的过程。 # 项目打包 pnpm run build# 上传文件至远程服务器 将本地打包生成的 dist 目录下的所有文件拷贝至服务器的 /usr/share/nginx/html 目录。# nginx.cofig…...

《CSS 知识点》大屏卡片布局思路:弹性布局 flex-grow

思路 大屏左右两侧高宽一致&#xff0c;内部卡片可按比例设置&#xff01; 使用弹性布局和属性 flex-grow 设置比例&#xff1b;间隔使用 margin-bottom 设置&#xff0c;最后一个卡片不设置&#xff1b; 效果如图 代码说明 CSS代码 26 - 30&#xff0c;左右两侧设置弹性布…...

nVisual 登录页页面配置说明

一、概述 nVisual登录页面可根据具体客户需要通过public\config\access.js文件进行自定义配置。页面可以大致分为4个部分&#xff0c;头部、底部、可移动区域以及页面中间的信息填写区域。其中头部和底部又包含头部左侧、头部中间、头部右侧、底部左侧、底部中间、底部右侧六个…...

后端接受前端传递数组进行批量删除

问题描述&#xff1a;当我们需要做批量删除功能的时候&#xff0c;我们循环单次删除的接口也能进行批量删除&#xff0c;但要删除100条数据就要调用100次接口&#xff0c;或者执行100次sql&#xff0c;这样系统开销是比较大的&#xff0c;那么我们直接采用接收的数组格式数据sq…...

拍频实例 - 一组恒力矩电流采样数据

这是一组功率电机的感应电流波形。加载了重载恒力矩设备。你能看到什么&#xff1f; 首先&#xff0c;时间轴的坐标是对的&#xff0c;9.9~10.0秒&#xff0c;单位是秒&#xff0c;100ms有5个波形&#xff0c;所以是20ms一个波形。这是50Hz的信号。频差就体现为幅度的周期起伏…...

Jvm之NativeMemoryTracking 使用

开启 Native Memory Tracking 通过 -XX:NativeMemoryTracking 开启&#xff1a; -XX:NativeMemoryTrackingoff:这是默认值&#xff0c;即关闭 Native Memory Tracking -XX:NativeMemoryTrackingsummary: 开启 Native Memory Tracking&#xff0c;但是仅仅按照各个 JVM 子系统…...

PKCS#7、Bit padding(位填充)、Byte padding(字节填充)、Zero padding(零填充)

PKCS#7、Bit padding&#xff08;位填充&#xff09;、Byte padding&#xff08;字节填充&#xff09;、Zero padding&#xff08;零填充&#xff09;是密码学常见的填充方式。 Bit padding&#xff08;位填充&#xff09;&#xff1a; 位填充可以应用于任意长度的消息。在消息…...

R语言学习笔记-1

1. 基础操作和函数 清空环境&#xff1a;rm(list ls()) 用于清空当前的R环境。 打印输出&#xff1a;print("Hello, world") 用于输出文本到控制台。 查看已安装包和加载包&#xff1a; search()&#xff1a;查看当前加载的包。install.packages("package_na…...

我在广州学 Mysql 系列之 数据“表”的基本操作

ℹ️大家好&#xff0c;我是&#x1f606;练小杰&#xff0c;今天主要讲得是Mysql数据表的基本操作内容~~ 昨天讲了“Mysql 数据“库“的基本操作”~~ 想要了解更多&#x1f236;️MYSQL 数据库的命令行总结&#xff01;&#xff01;&#xff01; “真相永远只有一个”——工藤…...

auto-gptq安装以及不适配软硬件环境可能出现的问题及解决方式

目录 1、auto-gptq是什么&#xff1f;2、auto-gptq安装3、auto-gptq不正确安装可能会出现的问题&#xff08;1&#xff09;爆出&#xff1a;CUDA extension not installed.&#xff08;2&#xff09;没有报错但是推理速度超级慢 1、auto-gptq是什么&#xff1f; Auto-GPTQ 是一…...

【R语言】基础知识

一、对象与变量 R语言中的所有事物都是对象&#xff0c;如向量、列表、函数&#xff0c;变量、甚至环境等。它的所有代码都是基于对象object的操作&#xff0c;变量只是调用对象的手段。 1、对象 在R语言中&#xff0c;对计算机内存的访问是通过对象实现的。 # 字符型向量 …...

【一本通】虫洞

【一本通】虫洞 C语言代码C代码JAVA代码 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边&#xff0c;并可以使你返回到过去的一个时刻&#xff08;相对你进入虫洞之…...

python爬虫--小白篇【爬虫实践】

一、前言 1.1、王者荣耀皮肤爬虫 根据王者荣耀链接&#xff0c;将王者荣耀的全部英雄的全部皮肤图片爬取保存到本地。经过分析得到任务的三个步骤&#xff1a; 根据首页全部英雄列表连接获取全部英雄的名称hero_name以及对应的hero_id&#xff1b;根据单个英雄的hero_name和h…...

Unity背包道具拖拽(极简版实现)

&#xff08;感觉Csdn代码页面可以再大一点或者加个放大功能 不然得划着看不太舒服&#xff09; 1.关键接口&#xff0c;三个拖拽相关的 2.关键参数&#xff0c;PointerEventData 一直没仔细看过&#xff0c;其实有包含鼠标相关的很多参数&#xff0c;鼠标点击次数&#xff…...

spark读取普通文件

spark读取普通文件 txt文件 """ 将一行数据当做一个字段&#xff0c;需要自己切割 字段名称为value 表结构 可以从sql中搞 """ df spark.read.text("../../data/wordcount/input/data.txt") df spark.read.format("text"…...

MySQL SQL语句性能优化

MySQL SQL语句性能优化指南 一、查询设计优化1. 避免 SELECT *2. 使用 WHERE 进行条件过滤3. 避免在索引列上使用函数和表达式4. 使用 LIMIT 限制返回行数5. 避免使用子查询6. 优化 JOIN 操作7. 避免全表扫描 二、索引优化1. 使用合适的索引2. 覆盖索引3. 索引选择性4. 多列索引…...

【蓝桥杯每日一题】技能升级

技能升级 2024-12-10 蓝桥杯每日一题 技能升级 二分 题目大意 一个角色有 N 种可以增加攻击力的技能&#xff0c;对于第 i 个技能首次升级可以提升 A i A_i Ai​ 点攻击力&#xff0c;随后的每次升级增加的攻击力都会减少 B i B_i Bi​ 。升级 ⌈ A i B i ⌉ \lceil \frac{A…...

MacBook Pro运行OpenClaw与百川2-13B-4bits量化版:性能实测与调优

MacBook Pro运行OpenClaw与百川2-13B-4bits量化版&#xff1a;性能实测与调优 1. 为什么选择这个组合&#xff1f; 去年底换了M2 Max芯片的MacBook Pro后&#xff0c;我一直在寻找能充分利用本地算力的AI工作流。直到发现OpenClaw这个开源自动化框架&#xff0c;配合百川2-13…...

SpreadJS ReportSheet 与 DataManager 实现 Token 鉴权

在技术领域&#xff0c;我们常常被那些闪耀的、可见的成果所吸引。今天&#xff0c;这个焦点无疑是大语言模型技术。它们的流畅对话、惊人的创造力&#xff0c;让我们得以一窥未来的轮廓。然而&#xff0c;作为在企业一线构建、部署和维护复杂系统的实践者&#xff0c;我们深知…...

Zynq XADC测量电压从配置到换算:DRP接口实战与AXI4-Lite选择指南

Zynq XADC电压测量全解析&#xff1a;DRP与AXI4-Lite接口深度对比与实战指南 在嵌入式系统设计中&#xff0c;精确的模拟信号监测往往是实现智能控制的关键环节。Xilinx Zynq系列芯片内置的XADC&#xff08;Xilinx Analog-to-Digital Converter&#xff09;模块&#xff0c;为工…...

骨干网为什么偏爱IS-IS?从报文结构到PRC算法详解运营商级路由协议设计

骨干网为何青睐IS-IS&#xff1f;从协议设计到现网实践的深度解析 在互联网基础设施的底层&#xff0c;运营商骨干网如同数字时代的高速公路系统&#xff0c;承载着全球90%以上的跨域流量。而这条"信息高速公路"的交通指挥系统&#xff0c;则高度依赖IS-IS&#xff0…...

告别配置噩梦?LazyVim让你5分钟拥有专业开发环境

告别配置噩梦&#xff1f;LazyVim让你5分钟拥有专业开发环境 【免费下载链接】LazyVim Neovim config for the lazy 项目地址: https://gitcode.com/GitHub_Trending/la/LazyVim 1️⃣ 价值定位&#xff1a;从数小时到5分钟的配置革命 在软件开发领域&#xff0c;编辑器…...

天地图性能优化实践:uniapp中用leaflet实现百万级点位渲染(附动态加载方案)

百万级点位地图渲染优化&#xff1a;uniappleaflet性能提升全方案 在移动应用开发中&#xff0c;地图功能已成为许多应用的核心组件。当面对海量点位数据时&#xff0c;传统渲染方式往往导致应用卡顿、内存飙升甚至崩溃。本文将深入探讨uniapp框架下结合leaflet地图库实现百万级…...

东莞故意伤害罪律师在线咨询

在东莞遇到故意伤害罪相关法律问题&#xff0c;别慌&#xff01;广东秦仪律师团队为您提供专业且贴心的在线咨询服务。我们拥有经验丰富的律师&#xff0c;他们不仅是广东省律师协会会员&#xff0c;还在法律领域深耕多年&#xff0c;有着扎实的法律知识和丰富的实战经验。曾在…...

使用C#代码将 HTML 转换为 PDF、XPS 和 XML

HTML 是网页和在线内容的标准格式。然而&#xff0c;在许多场景中&#xff0c;您可能需要将 HTML 文档转换为其他文件格式&#xff0c;例如 PDF、XPS 和 XML。无论是想生成网页的可打印版本&#xff0c;将 HTML 内容以更通用的格式分享&#xff0c;还是从 HTML 中提取数据以便进…...

mbeduino:Arduino语法兼容层实现RTOS级嵌入式开发

1. 项目概述mbeduino是一个面向嵌入式开发者的桥接型开源库&#xff0c;其核心目标是将 Arduino 生态中高度抽象、易上手的编程范式&#xff08;如setup()/loop()结构、digitalWrite()/analogRead()等语义化 API&#xff09;无缝移植至 ARM mbed OS 平台。它并非 Arduino IDE 的…...

NaViL-9B中小企业AI落地方案:低成本双卡部署多模态智能助手

NaViL-9B中小企业AI落地方案&#xff1a;低成本双卡部署多模态智能助手 1. 平台介绍 NaViL-9B是上海人工智能实验室研发的原生多模态大语言模型&#xff0c;能够同时处理文本和图像输入&#xff0c;为中小企业提供经济高效的AI解决方案。这款模型特别适合需要同时处理文字和图…...