什么叫营销型网站,网站模板定制,弹幕网站如何做,oa系统网站建设文章目录1. 题目2. 解题1. 题目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 #xff0c;长度为 n 。
数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 i n 的 (nums1[i] - nums2[i])^2 之和。
同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意…
文章目录1. 题目2. 解题1. 题目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 长度为 n 。
数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 i n 的 (nums1[i] - nums2[i])^2 之和。
同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 1 或者 -1 至多 k1 次。 类似的你可以将 nums2 中的任意元素 1 或者 -1 至多 k2 次。
请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。
注意你可以将数组中的元素变成 负 整数。
示例 1
输入nums1 [1,2,3,4], nums2 [2,10,20,19], k1 0, k2 0
输出579
解释nums1 和 nums2 中的元素不能修改因为 k1 0 和 k2 0 。
差值平方和为(1 - 2)^2 (2 - 10)^2 (3 - 20)^2 (4 - 19)^2 579 。示例 2
输入nums1 [1,4,10,12], nums2 [5,8,6,9], k1 1, k2 1
输出43
解释一种得到最小差值平方和的方式为
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为
(2 - 5)^2 (4 - 8)^2 (10 - 7)^2 (12 - 9)^2 43 。
注意也有其他方式可以得到最小差值平方和但没有得到比 43 更小答案的方案。提示
n nums1.length nums2.length
1 n 10^5
0 nums1[i], nums2[i] 10^5
0 k1, k2 10^9来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-sum-of-squared-difference 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
答案只与 对应元素的 非零 绝对值 有关系对这些绝对值进行排序大的优先减少
class Solution:def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) - int:diff list(filter(lambda x : x!0, [abs(x-y) for x, y in zip(nums1, nums2)]))# 非零 绝对值diff.sort(reverseTrue) # 逆序排列if len(diff) 0:return 0k k1k2 # 总的调整次数diff.append(0) # 代码编写简单需要prevnum diff[0]ct 1 # 前面相同元素的个数i 0while i len(diff)-1:delta diff[i]-diff[i1] # 跟后一个的差值if delta 0:ct 1 # 相同值的元素个数 1else: # 遇到有下降台阶了if k delta*ct: # k 的次数够ct个数降到下个元素的值prevnum diff[i1]k - delta*ctct 1else: # 不够 结束了delta k//ct # 把剩余的 k 次 均匀分给 ct 个数prevnum - delta # 每个数还能降低 deltaleft k - delta*ct # 剩余的次数每个数的值还能 -1return int(math.pow((prevnum-1), 2)*left math.pow(prevnum, 2)*(ct-left) sum([x*x for x in diff[ct:]]))i 1return 0188 ms 31.4 MB Python3
1648 题是一样的思路可以试试 https://leetcode.cn/problems/sell-diminishing-valued-colored-balls/ 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
