leetcode.1674 使数组互补的最少操作次数 - 差分
admin
2024-04-27 05:59:32
0次

1674. 使数组互补的最少操作次数

思路：

res[x] 表示当nums[i]+nums[n-1-i]==x时，所需的操作数

以下简称 a=nums[i]   b=nums[n-1-i]

所以答案就是最小的res[x]值

x取值范围为[ 2,2*limit ] 

  • 2——只要把a和b都改为1  x==2
  • limit*2——只要把a和b都改为limit   x==2*limit

计算数组里每一对a b的操作数 用差分数组进行对res区间的修改

  • 先把最大范围[2,2*limit]操作数置为2
  • [1+min(a,b),limit+max(a,b)]操作数为1  也就是在上一个区间的基础上-1
  • 【1+较小数，limit+较大数】该区间内的a b能保证在limit范围内只更改a或b
  • [a+b,a+b]区间内不用更改就满足，操作数为0，也就是在上一个区间的基础上-1

差分数组：res[i]=diff[1]+diff[2]+……+diff[i]

想给res的某个区间[l,r] +c 只需要给其差分数组diff[l]+=c diff[r+1]-=c即可

最后只要枚举每个res[x]  2~2*limit 求最小即可

class Solution {
public:int minMoves(vector& nums, int limit) {int n=nums.size();vector diff(2*limit+2,0);//因为res[x] x范围为[2,2*limit] 则res数组范围为[2,2*limit+1] 因为差分数组需要r+1 则diff数组开到2*limit+2for(int i=0;i

 看不懂差分的同学可以看看这篇哦~

【算法基础复习1】差分_Roye_ack的博客-CSDN博客

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：拆解特斯拉和兰博基尼，还招底盘工程师！雅迪也要造车？ 雅迪汽车雅迪工厂拆解特斯拉 雅迪被曝拆解兰博基尼特斯拉

下一篇：发明专利申请流程

相关内容

热门资讯

AI做攻略、“双向奔赴”……国... 本文转自：人民网人民网记者 许维娜今年国庆假期，AI（人工智能）成了不少年轻人的“旅行搭子”。行前做...
合肥的这个“梗”， 翻篇了 社交平台的评论区，曾长期流传一句专属于合肥的黑色幽默。有人问合肥哪里好玩，本地网友半开玩笑地回复：合...
7万+旅游中高层都在的群，今天... 做旅游这行，资源卡位、渠道互通、项目落地——往往就差一个“对的机会”。我们的行业社群已聚集70,00...
一场帐篷音乐节，如何让井研从“... 帐篷音乐节现场封面新闻记者 周洪攀10月的研溪湿地，晚风里裹着柑橘的清甜与民谣的回响。夜幕降临，10...
白鹤翩翩落星愿，上海迪士尼度假... 10月9日，世界候鸟日前夕，上海迪士尼度假区星愿公园的湖风里多了一分白鹤的灵动。三座白鹤雕塑正式揭幕...
成都锦江边赏初秋枫叶飘飘 目前，成都锦江边国华街枫叶树红了。近年来，国华街附近的几条街都栽种了红枫树，是城区较集中看枫叶的点位...
GBTA：商务旅行正在复苏，但... 亚太正在成为全球商务旅行增长的重要引擎。在经历疫情后的快速反弹之后，全球商务旅行正在进入一个新的增长...
从景区焕新到节赛引流 邹城双节... 齐鲁网·闪电新闻10月9日讯 中秋、国庆“双节”假期，邹城市文化和旅游局提前谋划、周密部署，立足自身...
江山如此多娇 且看石楼今朝 金秋十月，黄河岸畔秋意盎然，丰收盛会喜迎国庆。本次石楼国庆文旅活动以“江山如此多娇，且看石楼今朝”为...
海南国庆假期接待游客475.4... 2026年国庆假期，海南接待游客475.40万人次，较2025年增长13.1%，较2024年增长15...