LeetCode每日一题系列

题目：828. 统计子串中的唯一字符
难度：普通

文章目录

• LeetCode每日一题系列
• 题目
• 示例
• 思路
• 题解

题目

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。

• 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
• 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
• 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2中所有数的和相等。以下数组下标都从 0 开始。

• 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
• 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
• 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

1 <= nums1.length, nums2.length <= 105
1 <= nums1[i], nums2[i] <= 6

思路

题目要求的1是让调整后的两数组和相等，这一点我们可以转化为累加出两数组的和的差实现，2是最少次数实现，我们可以利用贪心的思想，让和较大的数组按从大到小的顺序依次减小、让和较小的数组按从小到大的顺序依次增大。具体做法

1. 分别求和值，将和值大的数组置为nums1, 小者为nums2，和值差值为diff
2. 对nums1 降序排列，对nums2升序排列（贪心思想,nums1中数据往下调，nums2中数据往上调，调整幅度大者优先）
3. 初始化累加和值为0，采用类似合并有序数组思路，选择 nums1[i] - 1或 6 - nums2[j]中大者进行累加, 直到累加和大于或等于diff, 返回操作计数（因为我们这里所做的操作都是对于每一步而言最大的贡献，所有累加贡献后大于等于原差值diff即可）

题解

class Solution(object):def minOperations(self, nums1, nums2):# 求出和较大的nums1，以及sum1sum1 = sum(nums1)sum2 = sum(nums2)if sum1 == sum2:return 0if sum1 < sum2:nums1, nums2 = nums2, nums1sum1, sum2 = sum2, sum1  #判断是否可行，差值不能超过可调的容限值diff = sum1 - sum2if diff > sum1 - len(nums1) + len(nums2)*6 - sum2:return -1#排序nums1.sort(reverse = True)nums2.sort()#贪心取数i = 0j = 0tmpSum = 0opCnt = 0while i < len(nums1) and j < len(nums2):if nums1[i] - 1 >= 6 - nums2[j]:tmpSum += nums1[i] - 1i += 1else:tmpSum += 6 - nums2[j]j += 1opCnt += 1if tmpSum >= diff:return opCntwhile i < len(nums1):tmpSum += nums1[i] - 1opCnt += 1if tmpSum >= diff:return opCnti += 1while j < len(nums2):tmpSum += 6 - nums2[j]opCnt += 1if tmpSum >= diff:return opCntj += 1return -1