Weekly Contest 366 周赛题目解析

Posted on Mon 09 October 2023 in Leetcode

Weekly Contest 366

第 366 场周赛

题目列表

2894. Divisible and Non-divisible Sums Difference 分类求和并作差

按照题意模拟即可。

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        s1 = 0
        for i in range(1, n + 1):
            if i % m != 0:
                s1 += i
        s2 = n * (n + 1) // 2 - s1

        return s1 - s2

2895. Minimum Processing Time 最小处理时间

这道题题目描述太差劲了。有两个要点：

  • 每个核心最多只能处理4个任务。
  • 题目要求的是处理器被分配的任务中最大能够处理完的时间，而不是最长多久能处理完。

因此，将处理器时间与任务时长分别排序后，让最早的处理器处理接下来最长的四个任务即可获得答案。

这道题如果是要求最长多久能处理完的话，就是一道标准的scheduling题目，用堆Heap即可求得最优解。

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        proc = sorted(processorTime)
        tasks = sorted(tasks, reverse=True)
        result = 0

        for i, p in enumerate(proc):
            for j in range(i * 4, i * 4 + 4):
                result = max(result, p + tasks[j])

        return result

2896. Apply Operations to Make Two Strings Equal 执行操作使两个字符串相等

给定两个长度为n的二进制字符串s1和s2和正整数x。你可以对字符串执行两种操作：

  1. 把s1[i]和s1[i + 1]两位都进行反转，这个操作的消耗为1。
  2. 把s1[i]和s2[j]两位都进行反转，这个操作的消耗为x。

你需要通过有限次的操作使得s1和s2最终相等，并找到最小的消耗。若完全无法使两个字符串相等的话，则返回-1。

什么时候两个字符串完全无法相等？答案是当两个字符串不想等的位数为奇数的时候。为什么会这样呢，我们转换下思路思考一下。

首先假设我们有两个二进制数字，将他们进行位运算xor之后，我们得到了数字b。那么，上面的问题就可以转换成我们通过两种操作要使b = 0的最小操作数。则我们可以分别讨论以上两个操作对于b来说的情况。我们分别讨论题目中描述的两种操作对于b的影响。

首先是第一种：

  1. 若b[i] = 1且b[i + 1] = 0，则我们可以以消耗1的代价使b[i] = 0，b[i + 1] = 1。即把b[i]向右边位移一位。
  2. 若b[i] = 1且b[i + 1] = 1，则我们可以以消耗1的代价使得b[i]和b[i + 1]的代价使得b[i]和b[i + 1]都为0。
  3. 结合以上两点，若b[i:j+1] = 1000...0001，则我们可以以j - i的代价使得b[i]和b[j]变为0。

那么我们再来看看第二个操作对于b有什么影响：

  1. 若b[i] = 1且b[j] = 1，则我们可以以消耗x的代价使得b[i]和b[j]都变为0。

因此我们说，当b中存在偶数个1的时候才有办法在有限次数内使得两个字符串s1和s2相等。

从上面的分析中，我们可以看到，我们可以把这个问题分解成一些子问题进行求解。因为前述的操作中，存在一定的局部性。举个例子，当b = 1001001001，若我们使用第一种操作，最优解为将(0, 3)和(6, 9)进行消去，而不是(0, 9)和(6, 3)。此外，当我们要消去中间z > x位的时候，如b = 1000..[z]..0001，使用第二种操作会更优。因此，这道题我们可以使用动态规划dp进行求解。其中，dp[i]为b[i:]的最优解，且我们只需要考虑b[i] = 1的情况。

当i为奇数的时候，对于这道题的定义来说dp[i]是未定义的。因此，我们将第二个条件松弛一下。原来的定义是我们可以选择b[i] = 1和b[j] = 1两个点，以x的代价将两者置为0。松弛后的条件为，我们可以选择任意的一个点b[i] = 1，以x / 2（浮点数）的代价将这个点置为0。这样子，我们就可以定义dp[i]了。我们直接进行分类讨论dp[i]：

  • i = n，dp[i] = 0
  • i = n - 1，dp[i] = x / 2
  • 0 < i < n - 1，dp[i] = min(dp[i + 1] + x / 2, dp[i + 2] + dist)，其中dist为当前点b[i] = 1和上一个点b[j] = 1之间的距离dist = j - i。

且慢，我们忽略了一个要点。我们怎么确保最后不会出现奇数次的x / 2呢？考虑我们只有偶数个的b[i] = 1的情况，我们会使用m次操作一，和n次操作二。很明显可得，因为第一种操作只会消去两个，剩余的元素只能用偶数个第二种操作消去。这里就不再延伸了，感兴趣的同学可以自己使用n = 4的情况去推演一下。

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        diffs = [i for i in range(len(s1)) if s1[i] != s2[i]]

        if len(diffs) % 2 == 1:
            return -1
        if len(diffs) == 0:
            return 0
        # print(diffs)
        dp = [float("inf") for _ in range(len(diffs) + 1)]
        dp[-1] = 0
        dp[-2] = 0
        for idx in range(len(diffs) - 2, -1, -1):
            dp[idx] = min(
                dp[idx + 1] + x, 
                dp[idx + 2] + diffs[idx + 1] - diffs[idx],
            )
            # print(dp)
        return int(dp[0])

2897. Apply Operations on Array to Maximize Sum of Squares 对数组执行操作使平方和最大

给定一个数组列表nums和整数k，你可以对数组中的数字nums[i]和nums[j]做如下操作，使nums[i] = nums[i] AND nums[j]和nums[j] = nums[i] OR nums[j]。你可以重复这个操作任意次数。最终，你需要选择k个数字，并找到他们的平方和。要求求出最大的平方和结果。

先复习一下位运算

x y x&y x|y
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

虽然爱会消失，但是比特不会。我们可以看到，只有当(x, y) = (1, 0)的时候，结果才会改变。因此，只要我们执行这个操作无限次，我们会重组这个数字无限次，使得所有比特位都排好序。

class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        n = len(nums)

        idx = [0] * 32
        lst = [0] * n

        for x in nums:
            for i in range(32):
                if x >> i & 1:
                    lst[idx[i]] += 1 << i
                    idx[i] += 1

        result = 0
        mod = int(1e9 + 7)

        for i in range(k):
            result += lst[i] * lst[i]
            result %= mod

        return result

Contest