leetcode第325场周赛：值域二分专场

字数统计: 4.1k字 | 阅读时长: 17分

2022-12-26

摘要: 本文是 leetcode 第 325 周赛的记录。主要涉及的算法包括值域二分、双指针、动态规划

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

本周进行了 leetcode 第 325 场周赛，本场比赛由西门子公司赞助，奖品还比较丰富，前 30 名都有奖品，具体如下：

排名第 1 - 10 名可获西门子提供的「米狗蓝牙对耳 R9」 x1 。
排名第 11 - 20 名可获西门子提供的「韩国现代便捷挂绳电源」 x1 。
排名第 21 - 30 名可获西门子提供的「公牛环球旅行转换器」 x1 。

奖品后面有一个西门子数字化工业的研发岗位招聘的广告，但是奖品部分并没有内推奖励，还挺寒冬的。

西门子这家公司倒是很早就听过，是一个德国公司，成立时间很早，1847 年。主要做工业、工厂、供应链，基础设施这些。现在转型了 IoT、智能制造，卖的是解决方案，也有一些咨询业务。详细信息可以看下面的官网：

1	https://new.siemens.com/cn/zh.html

本场比赛的难度应该是比较大的，从评论区来看也是这样：

本次比赛的发挥跟前几次一样，也是过了三个题，但是排名比以前提高了很多 (396/3530)，之前有一次也是三个题但是排名只有 2601/5115，也侧面说明了这次难度比前几场高：

其中第二题和第三题都是以值域二分为主要算法框架的，如果不会值域二分的话就只能干瞪眼，之前都能过三题四题的，这次可能真就只过一题。第四题在比赛的时候是在往动态规划想，但是转移方程做了很多演算总是差一点，赛后看题解发现是背包问题，代码非常短。

这种背包问题以前是仔细学习过的，并且也写了很多文章:

不过是 2020 年的了，当时的力扣上所有背包问题一道不差都囊括在我这几篇文章里了。现在两年过去了有点忘了，比赛时候没有想到，这也带给我们一个启示，有时候稍微复习一下还是很有用的。

各个题目涉及到的知识点汇总如下：

A题: 枚举
B题: 值域二分+定长滑动窗口；单串单向双指针
- 参考: 尺取法(单串单向双指针)
C题: 值域二分+贪心
- 参考: 二分
D题: 动态规划+逆向思维
- 参考: 01背包和完全背包；逆向思维

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

2515. 到目标字符串的最短距离

给你一个下标从 0 开始的环形字符串数组 words 和一个字符串 target 。环形数组意味着数组首尾相连。

形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。
从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。

返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 和 target 仅由小写英文字母组成
0 <= startIndex < words.length

示例 1：
输入：words = [“hello”,”i”,”am”,”leetcode”,”hello”], target = “hello”, startIndex = 1
输出：1
解释：从下标 1 开始，可以经由以下步骤到达 “hello” ：

向右移动 3 个单位，到达下标 4 。

向左移动 2 个单位，到达下标 4 。

向右移动 4 个单位，到达下标 0 。

向左移动 1 个单位，到达下标 0 。
到达 “hello” 的最短距离是 1 。

示例 2：
输入：words = [“a”,”b”,”leetcode”], target = “leetcode”, startIndex = 0
输出：1
解释：从下标 0 开始，可以经由以下步骤到达 “leetcode” ：

向右移动 2 个单位，到达下标 3 。

向左移动 1 个单位，到达下标 3 。
到达 “leetcode” 的最短距离是 1 。

示例 3：
输入：words = [“i”,”eat”,”leetcode”], target = “ate”, startIndex = 0
输出：-1
解释：因为 words 中不存在字符串 “ate” ，所以返回 -1 。

算法: 枚举

依次枚举每个位置 i，如果 words[i] 是目标词，则从 startIndex 向两个方向到当前位置 i 的距离都有可能是候选答案，如果比当前的答案小，则更新答案。

代码(Python)

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        ans = n
        for i in range(n):
            if words[i] != target:
                continue
            ans = min(ans, abs(startIndex - i))
            ans = min(ans, n - abs(startIndex - i))
        if ans == n:
            ans = -1
        return ans

B 题

2516. 每种字符至少取 K 个

给你一个由字符 ‘a’、’b’、’c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧还是最右侧的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

提示：

1
2
3

1 <= s.length <= 1e5
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

示例 1：
输入：s = “aabaaaacaabc”, k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 ‘a’ 、一个字符 ‘b’ 。
从 s 的右侧取五个字符，现在共取到四个字符 ‘a’ 、两个字符 ‘b’ 和两个字符 ‘c’ 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：
输入：s = “a”, k = 1
输出：-1
解释：无法取到一个字符 ‘b’ 或者 ‘c’，所以返回 -1 。

算法1: 值域二分+定长滑动窗口

本题要做的是在 s[0..n-1] 上选出一个区间 [l, r]，区间长度 length = r - l + 1，需要保证剩下的部分 [0, l-1], [r+1, n-1] 中，a, b, c 的数量均大于等于 k，问剩下的部分的元素个数 n - length 的最小值，也就是 length 的最大值。

在比赛中用的是值域二分+定长滑动窗口的做法，也就是二分 length，如果能在 s 中找到某个长度为 length 为 mid 的窗口，使得窗口中 a, b, c 的个数满足要求，则 check 成功，答案可能是 mid 也可能更大，于是 left 更新为 mid，否则如果 check 失败，则 mid 不可能是答案，答案只会比 mid 更小，于是 right 更新为 mid - 1。

每一次 check 的时间复杂度为 $O(N)$，而 length 的可能取值范围为 [0, n - 3 * k]，所以总的时间复杂度为 $O(N\log N)$。

代码(Python)

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        self.cnts = [0, 0, 0]
        for ch in s:
            self.cnts[ord(ch) - ord('a')] += 1
        for cnt in self.cnts:
            if cnt < k:
                return -1
        self.s = s
        self.k = k
        n = len(s)
        left = 0
        right = n - k * 3
        while left < right:
            mid = (left + right + 1) // 2
            if self.check(mid):
                left = mid
            else:
                right = mid - 1
        return n - left

    def check(self, w):
        # 滑动窗口
        def _check(_cnts):
            for i in range(3):
                if self.cnts[i] - _cnts[i] < self.k:
                    return False
            return True

        cnts = [0, 0, 0]
        for i in range(w):
            ch = self.s[i]
            cnts[ord(ch) - ord('a')] += 1
        if _check(cnts):
            return True

        n = len(self.s)
        for i in range(w, n):
            cnts[ord(self.s[i - w]) - ord('a')] -= 1
            cnts[ord(self.s[i]) - ord('a')] += 1
            if _check(cnts):
                return True
        return False

算法2: 单串单向双指针

比赛中用的是 $O(N\log N)$ 的值域二分+定长滑动窗口过得，实际上本题可以直接用不定长滑动窗口，也就是单串单向双指针，可以 $O(N)$。具体做法如下。

如果 s 中 a, b, c 的个数分别为 na, nb, nc，同时 s[0..l-1] 和 s[r+1..n-1] 中 a, b, c 分别至少有 k 个，那么 s[l..r] 中 a, b, c 的个数上限分别为 na - k, nb - k, nc - k。因此双指针在一轮推进中 l, r 的推进方式如下：

固定 l 的时候，推进 r 一直推进到 a, b, c 中的某个字符的个数超出的限制，就要停止推进 r，然后 r - l 就是一个可能的答案。然后固定 r，推进 l，一直推进到 a, b, c 中的字符个数均满足限制，然后进行新的一轮推进。

从 l = 0 开始，经过多轮推进，直到 r = n 结束，过程中维护窗口最大值即可。

代码(Python)

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        cnts = [0, 0, 0]
        for ch in s:
            cnts[ord(ch) - ord('a')] += 1
        for cnt in cnts:
            if cnt < k:
                return -1

        def _check(_cnts):
            for i in range(3):
                if cnts[i] - k < _cnts[i]:
                    return False
            return True

        max_length = 0
        n = len(s)
        cur_cnts = [0, 0, 0]
        left = 0
        right = -1
        while left < n:
            right += 1
            while right < n:
                cur_cnts[ord(s[right]) - ord('a')] += 1
                if not _check(cur_cnts):
                    break
                right += 1
            length = right - left
            max_length = max(max_length, length)
            if right == n:
                break
            while left <= right:
                cur_cnts[ord(s[left]) - ord('a')] -= 1
                left += 1
                if _check(cur_cnts):
                    break
        return n - max_length

C 题

2517. 礼盒的最大甜蜜度

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。

返回礼盒的最大甜蜜度。

提示：

1
2
3

1 <= price.length <= 1e5
1 <= price[i] <= 1e9
2 <= k <= price.length

示例 1：
输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例 2：
输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例 3：
输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

算法: 值域二分+贪心

直接计算组合 k 个糖果打包的最大甜蜜度比较难，但是给定一个甜蜜度 d，判断是否存在某 k 个糖果的组合使得甜蜜度大于等于 d 是比较容易的。

并且如果甜蜜度 d 可以实现，则最大甜蜜度一定大于等于 d。这样我就可以对 d 二分，然后在 check 里判断是否存在某 k 个糖果的甜蜜度大于等于 d 即可。

下面考虑给定甜蜜度 d 如何判定能否实现。

对 price 排序，然后先把价格最小的 price[0] 放到组合里，然后按价格从小到大的顺序考虑各个糖果，把第一个遇到的价格大于等于 price[0] + d 的糖果加入组合，然后继续向后考虑。

直到 price 耗尽，我们看组合中的糖果数，如果小于 k 则甜蜜度 d 无法实现，否则就是可以实现的。

代码(Python)

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        self.price = price
        self.k = k
        right = int(1e9)
        left = 0
        while left < right:
            mid = (left + right + 1) // 2
            if self.check(mid):
                left = mid
            else:
                right = mid - 1
        return left

    def check(self, d):
        # 贪心
        n = len(self.price)
        cur = self.price[0]
        k = 1
        for i in range(1, n):
            if self.price[i] - cur >= d:
                cur = self.price[i]
                k += 1
                if k == self.k:
                    return True
        return False

D 题

2518. 好分区的数目

给你一个正整数数组 nums 和一个整数 k 。

分区的定义是：将数组划分成两个有序的组，并满足每个元素恰好存在于某一个组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回不同的好分区的数目。由于答案可能很大，请返回对 1e9 + 7 取余后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

提示：

1 2	1 <= nums.length, k <= 1000 1 <= nums[i] <= 1e9

示例 1：
输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。

示例 2：
输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。

示例 3：
输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。

算法: 动态规划，逆向思维

我们从背包问题的角度分析这道题。

nums 中的元素为物品的体积；所有物品都没有价值。

如果 nums 的总和为 sum，如果装入背包的物品体积总和为 i，则剩余的部分体积为 sum - i。要求 i >= k 且 sum - i >= k。因此 k 实际上对应着背包容量限制 [k, sum - k]。

我们要求的是取出的若干物品的体积总和在 [k, sum-k] 这个范围中的取法有多少种，因此这是一个可行方案数问题。每个物品只能取一次，因此背包类型为 01 背包，

在力扣中，我们遇到过物品没有价值的 01 背包的可行方案数问题，例如 494. 目标和、377. 组合总和 Ⅳ。但这两个题求的都是取出物品体积要求恰好为规定值的方案数，而本题取出物品体积要求是在一个范围中。

这里还一个点值得注意，就是体积总和在 [k, sum-k] 范围中这个限制不太好处理，因为 sum 会非常大，无法塞到 dp 数组的维度里。

如果逆向思维一下，要求好分区个数不好求，我们先求不好的分区的个数，也就是 i < k 或 sum - i < k 的方案数，由于对称性，我们只需要求 i < k 的方案数，这样背包容量限制就变成了 [0, k)，这就可以塞到 dp 数组的维度里了。

状态定义：
dp[i][k] := 在 nums[0..i-1] 上，也就是前 i 个元素中，取出的物品体积总和为 k 的取法的方案数

答案：
sum(dp[n][0..K-1])

初始化
dp[0][0] = 1

状态转移：
dp[i][k] = dp[i - 1][k - nums[i - 1]]    (nums[i - 1] 放入背包)
           +  dp[i-1][k]                 (nums[i - 1] 不放入背包)

求出 x = sum(dp[n][0..K-1]) 后，最终答案为 $2^{n} - 2x$。

还有一点需要注意，就是如果两个分区都小于 k 的情况怎么处理，因为如果有两个分区都小于 k 的情况，那么 2x 中就有重复计数了。可以在实现进行特判，如果 sum 小于 k，则直接返回 0 即可，此后在进行前面的算法，就不会出现两个分区都小于 k 的这种重复计数了。

代码(C++)

using ll = long long;
const int MOD = 1e9 + 7;

int quickpower_mod(int a, int n, int mod) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1)
            ans = ((ll)ans * a) % mod;
        a = (ll)a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

class Solution {
public:
    int countPartitions(vector<int>& nums, int K) {
        int sum = 0;
        bool flag = false;
        for(int x: nums)
        {
            sum += x;
            if(sum >= K * 2)
            {
                flag = true;
                break;
            }
        }
        if(!flag)
            return 0;
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(K, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int k = 0; k < K; ++k)
            {
                dp[i][k] = dp[i - 1][k];
                if(k >= nums[i - 1])
                    dp[i][k] = ((ll)dp[i][k] + dp[i - 1][k - nums[i - 1]]) % MOD;
            }
        int x = 0;
        for(int k = 0; k < K; ++k)
            x = ((ll)x + dp[n][k]) % MOD;
        int ans = quickpower_mod(2, n, MOD);
        ans = ((ans - (ll)x * 2 % MOD) + MOD) % MOD;
        return ans;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

leetcode第325场周赛：值域二分专场

总览

A 题

算法: 枚举

代码(Python)

B 题

算法1: 值域二分+定长滑动窗口

代码(Python)

算法2: 单串单向双指针

代码(Python)

C 题

算法: 值域二分+贪心

代码(Python)

D 题

算法: 动态规划，逆向思维

代码(C++)