周赛 - 😺 第 74 场力扣夜喵双周赛 - 《学习笔记》

">
6020. 将数组划分成相等数对
6021. 字符串中最多数目的子字符串
6022. 将数组和减半的最少操作次数
6023. 用地毯覆盖后的最少白色砖块

T2考虑的不够周到，罚时了两次。。

6020. 将数组划分成相等数对

给你一个整数数组 nums ，它包含 2 * n 个整数。
你需要将 nums 划分成 n 个数对，满足：

每个元素 只属于一个 数对。
同一数对中的元素相等。

如果可以将 nums 划分成 n 个数对，请你返回 true ，否则返回 false 。

示例 1：
输入：nums = [3,2,3,2,2,2] 输出：true 解释： nums 中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。 nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。
示例 2：
输入：nums = [1,2,3,4] 输出：false 解释： 无法将 nums 划分成 4 / 2 = 2 个数对且满足所有要求。

提示：

nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

思路：
统计每个数出现的次数，判断是否为偶数即可
时间复杂度: O(n)
空间复杂度: 定长数组

class Solution {
    public boolean divideArray(int[] nums) {
        int[] cnt = new int[510];
        for (int x : nums)
                cnt[x]++;
        for (int i = 0; i < 510; i++)
            if (cnt[i] % 2 != 0)
                    return false;
        return true;
    }
}

6021. 字符串中最多数目的子字符串

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。
你可以在 text 中任意位置插入一个字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。
请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。
子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

示例 1：
输入：text = “abdcdbc”, pattern = “ac” 输出：4 解释： 如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = ‘a’ ，那么我们得到 “aba_dcdbc” 。那么 “ac” 作为子序列出现 4 次。其他得到 4 个 “ac” 子序列的方案还有 “aabdcdbc” 和 “abdacdbc” 。但是，”abdcadbc” ，”abdccdbc” 和 “abdcdbcc“ 这些字符串虽然是可行的插入方案，但是只出现了 3 次 “ac” 子序列，所以不是最优解。可以证明插入一个字符后，无法得到超过 4 个 “ac” 子序列。
示例 2：
输入：text = “aabb”, pattern = “ab” 输出：6 解释： 可以得到 6 个 “ab” 子序列的部分方案为 “aaabb” ，”aaabb” 和 “aabb_b” 。

提示：

1 <= text.length <= 105
pattern.length == 2
text 和 pattern 都只包含小写英文字母。

思路：
分类讨论，将第一个元素放在开头，或者将第二个元素放在结尾
如果两个元素相同，计算组合数直接返回
时间复杂度:O(N)
空间复杂度:O(N)

class Solution {
    public long maximumSubsequenceCount(String s, String p) {
        List<Character> list = new ArrayList<>();
        list.add(p.charAt(0));
        char c0 = p.charAt(0), c1 = p.charAt(1);
        for (int i = 0; i < s.length(); i++)
                if (s.charAt(i) == c0 || s.charAt(i) == c1)
                    list.add(s.charAt(i));
        if (c0 == c1)
            return (1L * list.size() * (list.size() - 1)) / 2;
        int cnt = 0;
        long res = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == c1) {
                res += cnt;
            } else {
                cnt++;
            }
        }
        list.add(c1);
        long res2 = 0;
        cnt = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) == c1) {
                res2 += cnt;
            } else {
                cnt++;
            }
        }
        return Math.max(res, res2);
    }
}

6022. 将数组和减半的最少操作次数

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择任意一个数并将它减小到恰好一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和至少减少一半的最少操作数。

示例 1：
输入：nums = [5,19,8,1] 输出：3 解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。以下是将数组和减少至少一半的一种方法：选择数字 19 并减小为 9.5 。选择数字 9.5 并减小为 4.75 。选择数字 8 并减小为 4 。最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。 nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。我们需要 3 个操作实现题目要求，所以返回 3 。可以证明，无法通过少于 3 个操作使数组和减少至少一半。
示例 2：
输入：nums = [3,8,20] 输出：3 解释：初始 nums 的和为 3 + 8 + 20 = 31 。以下是将数组和减少至少一半的一种方法：选择数字 20 并减小为 10 。选择数字 10 并减小为 5 。选择数字 3 并减小为 1.5 。最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。 nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 16.5 。我们需要 3 个操作实现题目要求，所以返回 3 。可以证明，无法通过少于 3 个操作使数组和减少至少一半。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 107

思路：
贪心，每次将最大的元素折半
不用考虑精度问题，不影响
时间复杂度: O(NlogN)
空间复杂度: O(N)

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> q = new PriorityQueue<>((o1, o2) -> o2 >= o1 ? 1 : -1);
        double sum = 0;
        for (int x : nums) {
            q.offer((double)x);
            sum += x;
        }
        double mid = sum / 2.0;
        int cnt = 0;
        while (sum > mid) {
            double x = q.poll();
            x /= 2;
            sum -= x;
            q.offer(x);
            cnt++;
        }
        return cnt;
    }
}

6023. 用地毯覆盖后的最少白色砖块

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

floor[i] = ‘0’ 表示地板上第 i 块砖块的颜色是黑色。
floor[i] = ‘1’ 表示地板上第 i 块砖块的颜色是白色。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条黑色的地毯，每一条黑色的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的最少数目。

示例 1：

输入：floor = “10110101”, numCarpets = 2, carpetLen = 2 输出：2 解释： 上图展示了剩余 2 块白色砖块的方案。没有其他方案可以使未被覆盖的白色砖块少于 2 块。
示例 2：

输入：floor = “11111”, numCarpets = 2, carpetLen = 3 输出：0 解释： 上图展示了所有白色砖块都被覆盖的一种方案。注意，地毯相互之间可以覆盖。

提示：

1 <= carpetLen <= floor.length <= 1000
floor[i] 要么是 ‘0’ ，要么是 ‘1’ 。
1 <= numCarpets <= 1000

思路：
线性DP
状态表示: f[i][j]表示前i个砖块使用j块地毯去覆盖的所有方案
属性：最小未被覆盖的白色砖块的相反数
状态转移：
t = ch[i] == '0' ? 1 : 0
f[i][j] = Math.max(f[i][j], f[i - 1][j] + t)
f[i][j] = Math.max(f[Math.max(0, i - len)][j - 1] + Math.min(len, i), f[i][j])

class Solution {
    public int minimumWhiteTiles(String floor, int m, int len) {
        int n = floor.length();
        floor = " " + floor;
        char[] ch = floor.toCharArray();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j > 0)
                    f[i][j] = Math.max(f[i][j], f[Math.max(0, i - len)][j - 1] + Math.min(len, i));
                int t = ch[i] == '0' ? 1 : 0;
                f[i][j] = Math.max(f[i][j], f[i - 1][j] + t);
            }
        }
        return n - f[n][m];
    }
}