leetcode weekly contest 339

第四题的换根 dp 还是比较难的题目，最后一题典型的跳跃问题，确实比较难的题目

2609. 最长平衡子字符串

给你一个仅由 0 和 1 组成的二进制字符串 s 。

如果子字符串中 所有的 0 都在 1 之前且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。

返回 s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "01000111"
输出：6
解释：最长的平衡子字符串是 "000111" ，长度为 6 。

示例 2：

输入：s = "00111"
输出：4
解释：最长的平衡子字符串是 "0011" ，长度为  4 。

示例 3：

输入：s = "111"
输出：0
解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。

提示：

1 <= s.length <= 50
'0' <= s[i] <= '1'

地址

https://leetcode.cn/contest/weekly-contest-338/problems/k-items-with-the-maximum-sum/

题意

直接枚举

思路

枚举所有可能的子字符串并检测该字符串是否符合平衡即可。我们找到连续 $0$ 的最大长度，并求出后续的 $1$ 的长度，如果 $0$ 的长度小于当前 $0$ 的长度，则可能构成平衡字符串。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int n = s.size();
        int res = 0;
        int i = 0;
        while (i < n) {
            int cnt0 = 0;
            int cnt1 = 0;
            while (i < n && s[i] == '0') {
                i++;
                cnt0++;
            }
            while (i < n && s[i] == '1') {
                i++;
                cnt1++;
                if (cnt0 >= cnt1) {
                    res = max(res, cnt1 * 2);
                }
            }
        }
        return res;
    }
};

2610. 转换二维数组

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

二维数组应该只包含数组 nums 中的元素。
二维数组中的每一行都包含不同的整数。
二维数组的行数应尽可能少。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= nums.length

地址

https://leetcode.cn/problems/convert-an-array-into-a-2d-array-with-conditions/

题意

贪心

思路

题目比较简单，由于每行都不能存在重复的元素，因此不可能只统计数组中每个元素的出现次数，每次构造时从不相同的元素中挑选一个即可。
复杂度分析：

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

代码

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (auto v : nums) {
            cnt[v]++;
        }
        vector<vector<int>> res;
        while (cnt.size() > 0) {
            vector<int> arr;
            vector<int> remove;
            for (auto &[v, freq] : cnt) {
                arr.emplace_back(v);
                freq--;
                if (freq == 0) {
                    remove.emplace_back(v);
                }
            }
            for (auto v : remove) {
                cnt.erase(v);
            }
            res.emplace_back(arr);
        }
        return res;
    }
};

2611. 老鼠和奶酪

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大得分为多少。

示例 1：

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。

示例 2：

输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

提示：

1 <= n == reward1.length == reward2.length <= 105
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n

地址

https://leetcode.cn/contest/weekly-contest-339/problems/mice-and-cheese/

题意

贪心

思路

由于第一只老鼠必须要吃 $k$ 个奶酪，可以证明贪心原则，奶酪给第一个老鼠吃得分为 $r_1[i]$,给第二个奶酪吃得分为 $r_2[i]$ ，则此时差距为 $diff[i] = r_1[i] - r_2[i]$,由于必须选择 $k$ 个，因此我们尽量选择 $diff[i]$ 最大的即可。
复杂度分析：

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

代码

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        vector<int> diff;
        for (int i = 0; i < n; i++) {
            diff.emplace_back(reward1[i] - reward2[i]);
        }
        sort(diff.begin(), diff.end(), [&](int a, int b) {
            return a > b;
        });
        return accumulate(diff.begin(), diff.begin() + k, 0) + accumulate(reward2.begin(), reward2.end(), 0);
    }
};

2612. 最少翻转操作数

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它翻转。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的最少翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

子数组 指的是一个数组里一段连续非空的元素序列。
对于所有的 i ，ans[i] 相互之间独立计算。
将一个数组中的元素翻转指的是将数组中的值变成 相反顺序 。

示例 1：

输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

示例 2：

输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

示例 3：

输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

提示：

1 <= n <= 105
0 <= p <= n - 1
0 <= banned.length <= n - 1
0 <= banned[i] <= n - 1
1 <= k <= n
banned[i] != p
banned 中的值 互不相同 。

地址

https://leetcode.cn/contest/weekly-contest-339/problems/minimum-reverse-operations/

题意

广度优先搜索

思路

题目本身比较难的题目，关键在于理解翻转的思路，本质为一个跳跃游戏类似的题目，但跳跃的距离较远，参考题解即可，关键的思路如下：
- 区间 $[l,r]$ 内关 $x$ 的反转为 $l + r - x$；
- 我们每次向左移动 $1$ 时，反转的下标会减少 $2$;
- 我们每次向右移动 $1$ 时，反转的下标会减少 $2$;
- 反转本质即相当于跳跃，
  - 如 $k$ 为偶数，则反转后也只能跳转到与当前奇偶不同的位置上，即此时 $i$ 只能反转到 $i + 1, i + 3, \cdots$ 等位置上；
  - 如 $k$ 为奇数，则反转后也只能跳转到与当前奇偶相同的位置上，即此时 $i$ 只能反转到 $i + 2, i + 4, \cdots$ 等位置上；
我们用$bfs$ 来标记所有被跳跃过的位置，假设当前的位置处于 $x$ 处，则此时它可以跳跃的范围为 $A = [\max(x - k + 1, k - x - 1), \min(x + k - 1, 2 * n - k - x - 1)]$，然后将当前仍然处在 $A$ 区域的位置全部删除即可，按照层次遍历即可。确实是非常不错的题目，感觉比较新颖的题目。
复杂度分析：

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

代码

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        unordered_set<int> bannedArr(banned.begin(), banned.end());
        vector<set<int>> cnt(2);
        for (int i = 0; i < n; i++) {
            if (!bannedArr.count(i) && i != p) {
                cnt[i & 1].emplace(i);
            }
        }
        vector<int> res(n, -1);
        res[p] = 0;
        queue<int> qu;
        qu.emplace(p);
        int step = 0;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                int start = max(curr - k + 1, k - curr - 1);
                int end = min(curr + k - 1, 2 * n - k - curr - 1);
                int x = start & 1;
                for (auto it = cnt[x].lower_bound(start); it != cnt[x].end() && *it <= end;) {
                    int j = *it;
                    res[j] = step + 1;
                    qu.emplace(j);
                    it++;
                    cnt[x].erase(j);
                }
            }
            step++;
        }
        return res;
    }
};

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

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode biweekly contest 102 leetcode contest 341 →

扫描二维码，分享此文章