★ FEATURED ARTICLE 2333. 最小差值平方和 - 力扣LeetCode在写这道题的时候我的思路是这样的思路 这里说要找所有对应位置数字的差值的最小平方和也就是说要找所有对应位置的数字的差值进行平方之后再加和计算返回求出的最小结果 这是在没有动用k的时候那如果我们分别动用k来处理两个数组的数字对于结果会有什么影响呢 我们发现这道题其实存在着可以运用的贪心思想 既然结果与各个差值的平方有关那只要让各个结果差值尽可能的小不就可以了吗 关键问题在于我们知道了让差值变小或者说让差值的绝对值变小就行了但是这么多差值我们怎么下手呢 我认为这里是贪心思想的体现 不难发现一个数越大平方后结果越大因此我们只要让最大的差值绝对值不断地变小就行了 临界情况呢 最大的差值变小第二大的差值会变成最大的然后循环往复直到用完k的次数因为我们处理的是差值结果的绝对值因此我们可以把k加到一起直接处理结果就行 先行条件应该是什么 k的次数没有被耗完。 怎么用算法表示最大的差值的前后位置变化呢 用while循环与sorted应该可以始终保持最大的差值绝对值在第一位综上所述我们得到了一份这样的代码class Solution: def minSumSquareDiff(self, nums1, nums2, k1: int, k2: int) - int: k k1 k2 arr [] for i in range(len(nums1)): cha nums1[i] - nums2[i] if cha 0: arr.append(cha) else: juedui -cha arr.append(juedui) # 到这里把所有的差值都添加完毕并且保证是正数 while arr and k 0: arr.sort(reverseTrue) if arr[0] 0: arr[0] - 1 k - 1 else: break result 0 for i in arr: result i ** 2 return result虽然经过ai的验证是正确的却无法在力扣里面跑完超时了。我的反思如下在我们获得差值数组的时候这些步骤应该是不能被优化的不过差值的绝对值两个分支判断却可以用abs方法来快速写abs就是用来获取绝对值的只需要将数字输入abs就能返回一个处理过的绝对值拓展对于复数仍适用因为abs是计算模长的。另外的一点是我们在while循环里面重复的运用了排序排序的时间复杂度挺高接着搭配着while循环他们的时间复杂度达到了一个很高的高度因此这里在想有没有一种方法绕过排序于是我们拓展出了计数数组的方法class Solution: def minSumSquareDiff(self, nums1, nums2, k1: int, k2: int) - int: kk1k2 arr[] if nums1[] or nums2[]: return 0 for i in range(len(nums1)): chanums1[i]-nums2[i] if cha0: arr.append(cha) else: juedui-cha arr.append(juedui) chaarr [0]*(max(arr)1) for i in arr: chaarr[i]1 #这里巧妙的将原差值数列与新的统计数列的索引结合在一起保证统计数列里面可以统计到所有的可能存在的值所以统计数列的长度是根据差值数列里面的最大值决定的 for i in range(len(chaarr)-1,-1,-1): while chaarr[i]0 and k0 : chaarr[i]-1 if i0: chaarr[i-1]1 k-1 if chaarr[i]0: continue if k0 : break result0 for i in range(len(chaarr)): resulti**2*chaarr[i] return result模拟过程我们先处理两个数组将两个数组的的对应位置计算出结果然后把他们的绝对值添加在数组里面依据数组的最大值开一个长度等于最大值的计数数组接着我们遍历这个绝对值数组遍历得到的每个值都是计数数组的下标下标即索引搭配所存储的值就能实现一个类似字典的功能索引是差值值是这样差值的数量到这里我们的思路是依据这个新的计数数组然后处理k边界关系是1.数组每项都为零k就不用管了2.k为零剩下的数组就不用管了模拟过程对于索引最大的一项我们一直对它减直到k等于零或者该项等于零这里我们发现每项每处理一次前一项应该加一边界条件如上不过多了一条不能是数组的第一项因为它没有前一项这里我尝试了用一种新方法解题最终答案虽然是正确的但是仍超时了我查证了答案之后发现根本原因在于我仍是一个一个处理数据的答案中是进行批量处理的什么意思就是从计数数组最大索引的最大值开始减一口气能减多少就减多少边界就是这个值与k之间的关系如果k这个值,那么这个值就清零k减小对应的值数组前一位加上对应的值如果k这个值k就清零值减小k关键点就是要把上述步骤中一个一个处理k与值改为这样的结构for i in range(len(chaarr) - 1, -1, -1): while chaarr[i] 0 and k 0: chaarr[i] - 1 if i 0: chaarr[i - 1] 1 k - 1 if chaarr[i] 0: continue if k 0: break把这个结构变为for i in range(len(chaarr) - 1, -1, -1): if k0 and chaarr[i]0: if kchaarr[i]: chaarr[i]0 k-charr[i] elif kchaarr[i]: k0 chaarr[i]-k if chaarr[i] 0: continue if k 0: break最终优化完的代码结构就是class Solution: def minSumSquareDiff(self, nums1, nums2, k1: int, k2: int) - int: kk1k2 arr[] if nums1[] or nums2[]: return 0 for i in range(len(nums1)): chanums1[i]-nums2[i] arr.append(abs(cha)) chaarr [0]*(max(arr)1) for i in arr: chaarr[i]1 #这里巧妙的将原差值数列与新的统计数列的索引结合在一起保证统计数列里面可以统计到所有的可能存在的值所以统计数列的长度是根据差值数列里面的最大值决定的 for i in range(len(chaarr)-1,-1,-1): if k 0 and chaarr[i] 0: if k chaarr[i]: if i0: chaarr[i-1]chaarr[i] k - chaarr[i] chaarr[i]0 elif k chaarr[i]: chaarr[i] - k if i0: chaarr[i-1]k k0 if chaarr[i]0: continue if k0 : break result0 for i in range(len(chaarr)): resulti**2*chaarr[i] return result如上代码能够顺利跑通这道题并且取得了不错的成绩总结算法实现的过程目前我认为有这么几步模拟在纸上写出或者在编程软件中用注释写出这个题目要求实现的东西的动态过程用语言描述出它们一定要分步骤然后找出对应的可以用的代码实现结构来实现这个思路一定要记得考虑好边界条件必须不漏尽量不重有些情况重复不影响有些情况影响如果语法能跑通逻辑没问题接着就是复盘优化如果不行那就修改语法逻辑等希望可以帮助到大家
阅读完成 · 觉得有帮助？
