[Leetcode Weekly Contest]339

链接：LeetCode

[Leetcode]2609. 最长平衡子字符串

给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。

模拟遍历即可。

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int zero = 0, one = 0;
        int res = 0, result = 0;
        for(char ch: s.toCharArray()) {
            if(ch == '0') {
                if(one!=0) {
                    one = 0;
                    zero = 1;
                } else {
                    zero ++;
                }
            }
            else {
                one ++;
                result = Math.min(zero, one);
                res = Math.max(res, result);
            }
        }
        return 2 * res;
    }
}

[Leetcode]2610. 转换二维数组

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：
二维数组应该 只 包含数组 nums 中的元素。
二维数组中的每一行都包含 不同 的整数。
二维数组的行数应尽可能 少 。
返回结果数组。如果存在多种答案，则返回其中任何一种。

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

哈希。

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int num: nums) {
            hash.put(num, hash.getOrDefault(num, 0) + 1);
        }
        List<List<Integer>> res = new ArrayList<>();
        int length = 1;
        for(var key: hash.keySet()) {
            length = Math.max(length, hash.get(key));
        }
        for(int i=0;i<length;++i) res.add(new ArrayList<Integer>());

        for(int key: hash.keySet()) {
            int value = hash.get(key);
            for(int i=0;i<value;++i) res.get(i).add(key);
        }
        return res;
    }
}

[Leetcode]2611. 老鼠和奶酪

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大得分为多少。

排序+贪心。为了使最终得分最大，应该让每只老鼠吃到尽可能大的奶酪。由于两只老鼠吃的奶酪是互斥关系，因此我们可以先假设所有奶酪被第一只老鼠食得，然后再挑选 n - k 个奶酪还给第二只老鼠。
那么，对于每个位置 i，将奶酪从第一只老鼠还给第二只老鼠存在差值 diff = reward2[i] - reward1[i]，表示得分的差值为 diff。差值为正得分变大，差值为负得分降低，显然降低越少越好。
因此，我们的算法是对 diff 排序，将得分降低越大的位置保留给第一只老鼠，其他还给第二只老鼠。

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        List<List<Integer>> diff = new ArrayList<>();
        int length = reward1.length;
        for(int i=0;i<length;++i) {
            diff.add(new ArrayList<Integer>());
            diff.get(i).add(i);
            diff.get(i).add(reward2[i]- reward1[i]);
        }
        Collections.sort(diff, (n1, n2) -> n1.get(1)-n2.get(1));
        int res = 0;
        for(int i=0;i<k;++i) {
            res += reward1[diff.get(i).get(0)];
        }
        for(int i=k;i<length;++i) {
            res += reward2[diff.get(i).get(0)];
        }
        return res;
    }
}

[Leetcode]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] 相互之间独立计算。
• 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序

BFS 模拟。

class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        var ban = new boolean[n];
        ban[p] = true;
        for (int i : banned) ban[i] = true;
        TreeSet<Integer>[] sets = new TreeSet[2];
        sets[0] = new TreeSet<>();
        sets[1] = new TreeSet<>();
        for (int i = 0; i < n; i++)
            if (!ban[i])
                sets[i % 2].add(i);
        sets[0].add(n);
        sets[1].add(n); // 哨兵

        var ans = new int[n];
        Arrays.fill(ans, -1);
        var q = new ArrayList<Integer>();
        q.add(p);
        for (int step = 0; !q.isEmpty(); ++step) {
            var tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                ans[i] = step;
                // 从 mn 到 mx 的所有位置都可以翻转到
                int mn = Math.max(i - k + 1, k - i - 1);
                int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
                var s = sets[mn % 2];
                for (var j = s.ceiling(mn); j <= mx; j = s.ceiling(mn)) {
                    q.add(j);
                    s.remove(j);
                }
            }
        }
        return ans;
    }
}

参考：LeetCode