且听疯吟

leetcode weekly contes 366

2023-10-17

leetcode weekly contes 366

今天工作日，竟然忘记今天还有周赛要参加了，果真掉大分了。给定的题目还是非常难的题目，不好作答。

100103. 分类求和并作差

给你两个正整数 n 和 m 。

现定义两个整数 num1 和 num2 ，如下所示：

  • num1：范围 [1, n] 内所有 无法被 m 整除 的整数之和。
  • num2：范围 [1, n] 内所有 能够被 m 整除 的整数之和。

返回整数 num1 - num2 。

示例 1：

输入：n = 10, m = 3
输出：19
解释：在这个示例中：
- 范围 [1, 10] 内无法被 3 整除的整数为 [1,2,4,5,7,8,10] ，num1 = 这些整数之和 = 37 。
- 范围 [1, 10] 内能够被 3 整除的整数为 [3,6,9] ，num2 = 这些整数之和 = 18 。
返回 37 - 18 = 19 作为答案。

示例 2：

输入：n = 5, m = 6
输出：15
解释：在这个示例中：
- 范围 [1, 5] 内无法被 6 整除的整数为 [1,2,3,4,5] ，num1 = 这些整数之和 =  15 。
- 范围 [1, 5] 内能够被 6 整除的整数为 [] ，num2 = 这些整数之和 = 0 。
返回 15 - 0 = 15 作为答案。

示例 3：

输入：n = 5, m = 1
输出：-15
解释：在这个示例中：
- 范围 [1, 5] 内无法被 1 整除的整数为 [] ，num1 = 这些整数之和 = 0 。 
- 范围 [1, 5] 内能够被 1 整除的整数为 [1,2,3,4,5] ，num2 = 这些整数之和 = 15 。
返回 0 - 15 = -15 作为答案。

提示：

  • 1 <= n, m <= 1000

地址

https://leetcode.cn/contest/weekly-contest-366/problems/divisible-and-non-divisible-sums-difference/

题意

枚举

思路

  1. 直接枚举统计所有能被 $m%$ 整除的数字之和即可。当然也可以使用数学方法， $O(1)$ 的时间复杂度内解决该问题。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的元素。
  • 空间复杂度：$O(1)$。

代码

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

100085. 最小处理时间

你有 n 颗处理器，每颗处理器都有 4 个核心。现有 n * 4 个待执行任务，每个核心只执行 一个 任务。

给你一个下标从 0 开始的整数数组 processorTime ，表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 最小时间 。

注意：每个核心独立执行任务。

示例 1：

输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。 
第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。
第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。
因此，可以证明执行完所有任务需要花费的最小时间是 16 。

示例 2：

输入：processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
输出：23
解释：
最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器（最早空闲时间 time = 10），下标为 0, 2, 3, 7 的任务分配给第二颗处理器（最早空闲时间 time = 20）。 
第一颗处理器执行完所有任务需要花费的时间 = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18 。 
第二颗处理器执行完所有任务需要花费的时间 = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23 。 
因此，可以证明执行完所有任务需要花费的最小时间是 23 。

提示：

  • 1 <= n == processorTime.length <= 25000
  • 1 <= tasks.length <= 105
  • 0 <= processorTime[i] <= 109
  • 1 <= tasks[i] <= 109
  • tasks.length == 4 * n

地址

https://leetcode.cn/contest/weekly-contest-365/problems/maximum-value-of-an-ordered-triplet-ii/

题意

贪心 + 排序

思路

  1. 如要使得最大时间尽可能的短，则应使得 $4$ 个核心中处理的任务尽可能尽可能的短，对于每个处理器到达最小的空闲时间，则其应该分配耗时更长的任务，这样才能保障最大值尽可能的小，我们的目标是让下面的值尽可能的小：
    $$
    T = \min(processorTime[0] + task[a_0], processorTime[1] + task[a_1], \cdots )
    $$
    在上述操作下，如何使得上述 $T$ 的值最小，此时我们将最短等带时间的处理器与耗时最长的任务匹配，比如 $i$ 与 $j$ 个任务匹配，则此时最优匹配应该是接下来连续的三个任务都应该由 $i$ 来进行处理, 需要数学归纳法证明，证明在此不再描述。

  2. 复杂度分析：

  • 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度。

代码

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        tasks.sort(key = lambda x : -x)
        processorTime.sort()
        return max([processorTime[i] + tasks[4 * i] for i in range(len(processorTime))])

8028. 执行操作使两个字符串相等

给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。

你可以对字符串 s1 执行以下操作 任意次 ：

  • 选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。
  • 选择满足 i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。

请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。

注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。

示例 1：

输入：s1 = "1100011000", s2 = "0101001010", x = 2
输出：4
解释：我们可以执行以下操作：
- 选择 i = 3 执行第二个操作。结果字符串是 s1 = "1101111000" 。
- 选择 i = 4 执行第二个操作。结果字符串是 s1 = "1101001000" 。
- 选择 i = 0 和 j = 8 ，执行第一个操作。结果字符串是 s1 = "0101001010" = s2 。
总代价是 1 + 1 + 2 = 4 。这是最小代价和。

示例 2：

输入：s1 = "10110", s2 = "00011", x = 4
输出：-1
解释：无法使两个字符串相等。

提示：

  • n == s1.length == s2.length
  • 1 <= n, x <= 500
  • s1 和 s2 只包含字符 '0' 和 '1' 。

地址

https://leetcode.cn/contest/weekly-contest-366/problems/apply-operations-to-make-two-strings-equal/

题意

动态规划

思路

  1. 题目还是非常有意思的，比如我们需要同时反转两个字符 $s[i], s[j]$ 时，此时可以有两种方法：

    • 同时反转 $s[i],s[j]$, 此时需要的代价为 $x$;
    • 假设 $i < j$, 则此时需要依次反转 $(s[i],s[i+1]),(s[i+1],s[i+2]), \cdots,(s[j-1],s[j])$, 一共需要反转 $j - i$ 次，此时需要的代价为 $j-i$;

    给定字符串 $s1$ 与 $s2$, 通过两两反转使得 $s1$ 与 $s2$ 相等，此时我们需要仔细分析该问题，首先看到题目给定的数量级为 $[1,500]$, 则可以肯定的是该题的时间复杂度为 $O(n^2)$ ，此时需要仔细思考哪些算法在这个时间复杂度范围内，由于给定的 $s[i]$ 可以与 $[0,n-1]$ 中的任意一个字符进行交换，我们需要仔细分析：

    • 首先需要统计字符中不同的字符位置 $diff$, 如果两个字符串中字符不同的位置数量为奇数个，则此时肯定无法实现反转使得两个字符串相等，因为根据题意可以知道一次操作会使得两个字符同时反转，所以如果字符串不同位置的数量为奇数个则一定无法通过反转使得两个字符串相等；
    • 其次我们需要思考一个问题，假设两个字符中不同的位置序列为 $[c_0,c_1,c_2,\cdots,c_m]$, 此时我们需要思考的是 $c_i$ 该与哪个字符交换，假设 $c_i$ 与 $c_j$ 进行了交换，则可以知道一定为如下三种情况：
      • $i = j + 1$, 此时两个最接近的位置进行了交换，此时使得 $[c_j,c_{j+1}]$ 两个相邻位置的字符相等，不再有其他的位置与其交换；
      • $i = j - 1$, 此时两个最接近的位置进行了交换，此时使得 $[c_{j-1},c_{j}]$ 两个相邻位置的字符相等，不再有其他的位置与其交换；
      • $i < j$, 此时两个位置进行了交换，此时使得 $(c_i,c_j)$ 两个相邻位置的字符相等, 处于位置 $c_{i+1},c_{i+2}, \cdots,c_{j-1}$ 的字符根据贪心原则，他们一定是在区间 $[i+1,j-1]$ 内部进行自交换，一定不会出现交换的情况，即 $s_k,k \in[i+1,j-1]$ 与 $s_p,p\in[0,i-1] \and [j+1,n-1]$ 进行交换，因为这样交换的代价一定不是最优的，可以用反证法来证明；
      • 根据前 $3$ 点分析可以知道，设 $dp[i][j]$ 表示区间 $[i,j]$ 之间的字符串通过反转与 $s2$ 相同的最小代价，此时我们可以知道如下：
        • 第 $j$ 个字符与第 $j - 1$ 个字符用第二种操作反转，则此时最小代价为 $dp[i][j] = \min (dp[i][j],dp[i][j-2] + diff[j] - diff[j-1])$;
        • 第 $i$ 个字符与第 $i + 1$ 个字符用第二种操作反转，则此时最小代价为 $dp[i][j] = \min (dp[i][j],dp[i+2][j] + diff[i+1] - diff[i])$;
        • 第 $i$ 个字符与第 $j$ 个字符用第一种操作反转，则此时最小代价为 $dp[i][j] = \min (dp[i][j],dp[i+1][j-1] + x)$;
      • 根据上述动态规划递推即可计算出最小结果 $dp[0][n-1]$；

  2. 复杂度分析：

  • 时间复杂度：$O(n^2)$，其中$n$ 表示字符串的长度；
  • 空间复杂度：$O(n^2)$，其中$n$ 表示字符串的长度；

代码

class Solution {
public:
    static constexpr int INF = 0x3f3f3f3f;
    
    int minOperations(string s1, string s2, int x) {
        vector<int> diff;
        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i]) {
                diff.emplace_back(i);
            }
        }
        
        int n = diff.size();
        if (n & 1) return -1;
        if (n == 0) return 0;
        
        vector<vector<int>> dp(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (i - j == 1) {
                    dp[j][i] = min(x, diff[i] - diff[j]);
                } else {
                    dp[j][i] = min(dp[j][i], dp[j + 2][i] + min(x, diff[j + 1] - diff[j]));
                    dp[j][i] = min(dp[j][i], dp[j][i - 2] + min(x, diff[i] - diff[i - 1]));
                    dp[j][i] = min(dp[j][i], dp[j + 1][i - 1] + min(x, diff[i] - diff[j]));
                }
            }
        }
        return dp[0][n - 1];        
    }
};

100087. 对数组执行操作使平方和最大

给你一个下标从 0 开始的整数数组 nums 和一个 正 整数 k 。

你可以对数组执行以下操作 任意次 ：

  • 选择两个互不相同的下标 i 和 j ，同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) ，OR 表示按位 或 运算，AND 表示按位 与 运算。

你需要从最终的数组里选择 k 个元素，并计算它们的 平方 之和。

请你返回你可以得到的 最大 平方和。

由于答案可能会很大，将答案对 109 + 7 取余 后返回。

示例 1：

输入：nums = [2,6,5,8], k = 2
输出：261
解释：我们可以对数组执行以下操作：
- 选择 i = 0 和 j = 3 ，同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ，结果数组为 nums = [0,6,5,10] 。
- 选择 i = 2 和 j = 3 ，同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ，结果数组为 nums = [0,6,0,15] 。
从最终数组里选择元素 15 和 6 ，平方和为 152 + 62 = 261 。
261 是可以得到的最大结果。

示例 2：

输入：nums = [4,5,4,7], k = 3
输出：90
解释：不需要执行任何操作。
选择元素 7 ，5 和 4 ，平方和为 72 + 52 + 42 = 90 。
90 是可以得到的最大结果。

提示：

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-366/problems/apply-operations-on-array-to-maximize-sum-of-squares/

题意

数学问题

思路

  1. 题目出的比较有意思，关键在于如何理解该位运算，有题目可以知道：
    $$
    x \and y + x \or y = x + y \
    x, y = x \and y, x \or y
    $$
    我们可以看到通过与运算和或运算只是将 $x$ 中的 $1$ 转移到 $y$ 中，但是两者的和不会改变。我们还需要计算转移的大小，即此时假设从 $x$ 转移了 $d$ 到 $y$, 此时我们应该尽量进行转移，因为转移后的元素的平方和的值会更大。
    $$
    (x - d)^2 + (y + d)^2 \ge x^2 + y^2
    $$

    因此我们应该将尽可能多的 $1$ 转移到最大数上面，此时我们只需要每次尝试最多可以转移的 $1$ 个数即可构成最大的数。

  2. 复杂度分析：

  • 时间复杂度：$O(C(n + k))$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素；
  • 空间复杂度：$O(C)$，其中 $C = 32$ ；

代码

class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        cnt = [0] * 32
        for v in nums:
            for j in range(32):
                if v & (1 << j):
                    cnt[j] += 1
        
        res = 0
        for i in range(k):
            cur = 0
            for j in range(31, -1, -1):
                if cnt[j] > 0:
                    cur |= (1 << j)
                    cnt[j] -= 1
            res += cur * cur
        return res % (10**9 + 7)

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode weekly contes 367 leetcode biweekly contes 115 →

扫描二维码，分享此文章