且听疯吟

leetcode biweekly contes 112

2023-09-17

leetcode biweekly contes 112

双周赛算是比较简单的题目了，基本上一眼看到就知道题目解法了，特别是 T4 是一个比较简单的组合数学的问题。

2839. 判断通过操作能否让字符串相等 I

给你两个字符串 s1 和 s2 ，两个字符串的长度都为 4 ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

  • 选择两个下标 i 和 j 且满足 j - i = 2 ，然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

示例 1：

输入：s1 = "abcd", s2 = "cdab"
输出：true
解释： 我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbad" 。
- 选择下标 i = 1 ，j = 3 ，得到字符串 s1 = "cdab" = s2 。

示例 2：

输入：s1 = "abcd", s2 = "dacb"
输出：false
解释：无法让两个字符串相等。

提示：

  • s1.length == s2.length == 4
  • s1 和 s2 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-112/problems/check-if-strings-can-be-made-equal-with-operations-i/

题意

直接模拟

思路

  1. 由于字符串的长度为 4, 且题目最多只能交换 $2$ 次，我们分别灭局交换的次数即可，

    • 交换 $0$ 次：次数直接比较 $s_1,s_2$ 是否相等即可；
    • 交换 $1$ 次：要么交换 $s_0,s_2$, 要么交换 $s_1,s_3$；
    • 交换 $2$ 次：同时交换 $(s_0,s_2),(s_1,s_3)$；

    我们依次枚举上述的几种交换方式即可。

  2. 复杂度分析：

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

代码

[sol1-C++]
class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        if (s1 == s2) return true;
        string s = s1;
        swap(s[0], s[2]);
        if (s == s2) return true;
        s = s1;
        swap(s[1], s[3]);
        if (s == s2) return true;
        s = s1;
        swap(s[0], s[2]);
        swap(s[1], s[3]);
        if (s == s2) return true;
        return false;
    }
};

2840. 判断通过操作能否让字符串相等 II

给你两个字符串 s1 和 s2 ，两个字符串长度都为 n ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

  • 选择两个下标 i 和 j ，满足 i < j 且 j - i 是 偶数，然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

示例 1：

输入：s1 = "abcdba", s2 = "cabdab"
输出：true
解释：我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbadba" 。
- 选择下标 i = 2 ，j = 4 ，得到字符串 s1 = "cbbdaa" 。
- 选择下标 i = 1 ，j = 5 ，得到字符串 s1 = "cabdab" = s2 。

示例 2：

输入：s1 = "abe", s2 = "bea"
输出：false
解释：无法让两个字符串相等。

提示：

  • n == s1.length == s2.length
  • 1 <= n <= 105
  • s1 和 s2 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-112/problems/check-if-strings-can-be-made-equal-with-operations-ii/

题意

分类排序

思路

  1. 题目比较简单，本质上就是判断两个字符串的奇数位与偶数位上含有的字符是否都相等，我们同时将两个字符串的奇数位上的字符取出排序，将两个字符串上的偶数位上的字符取出排序，比较奇数位与偶数位上的字符是否相等即可。

  2. 复杂度分析：

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

代码

class Solution {
public:
    bool checkStrings(string s1, string s2) {
        int n = s1.size();
        vector<string> arr1(2), arr2(2);
        for (int i = 0; i < n; i++) {
            if (i & 1) {
                arr1[0].push_back(s1[i]);
                arr2[0].push_back(s2[i]);
            } else {
                arr1[1].push_back(s1[i]);
                arr2[1].push_back(s2[i]);
            }
        }
        sort(arr1[0].begin(), arr1[0].end());
        sort(arr2[0].begin(), arr2[0].end());
        sort(arr1[1].begin(), arr1[1].end());
        sort(arr2[1].begin(), arr2[1].end());
        if (arr1[0] == arr2[0] && arr1[1] == arr2[1]) {
            return true;
        } else {
            return false;
        }
    }
};

2841. 几乎唯一子数组的最大和

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

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

子数组指的是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。

示例 2：

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
输出：23
解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。

示例 3：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-112/problems/maximum-sum-of-almost-unique-subarray/

题意

滑动窗口

思路

  1. 简单的滑动窗口即可解决该题目，每次统计长度为 $k$ 的窗口中不同字符的统计数目是否大于等于 $m$ 即可，此时检测当前的子数组的和是否为最大；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度；
  • 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度；

代码

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        long long res = 0;
        long long sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]]++;
            sum += nums[i];
            if (i >= k - 1) {
                if (cnt.size() >= m) {
                    res = max(res, sum);
                }
                cnt[nums[i - k + 1]]--;
                if (cnt[nums[i - k + 1]] == 0) {
                    cnt.erase(nums[i - k + 1]);
                }
                sum -= nums[i - k + 1];
            }
        }
        return res;
    }
};

2842. 统计一个字符串的 k 子序列美丽值最大的数目

给你一个字符串 s 和一个整数 k 。

k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。

定义 f(c) 为字符 c 在 s 中出现的次数。

k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。

比方说，s = "abbbdd" 和 k = 2 ，我们有：

  • f('a') = 1, f('b') = 3, f('d') = 2

  • s


       的部分 k 子序列为：

      - `"***ab***bbdd"` -> `"ab"` ，美丽值为 `f('a') + f('b') = 4`
      - `"***a***bbb***d***d"` -> `"ad"` ，美丽值为 `f('a') + f('d') = 3`
      - `"a***b***bb***d***d"` -> `"bd"` ，美丽值为 `f('b') + f('d') = 5`

    请你返回一个整数，表示所有 **k 子序列** 里面 **美丽值** 是 **最大值** 的子序列数目。由于答案可能很大，将结果对 `109 + 7` 取余后返回。

    一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。

    **注意：**

    - `f(c)` 指的是字符 `c` 在字符串 `s` 的出现次数，不是在 k 子序列里的出现次数。
    - 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。

     

    **示例 1：**

    
输入：s = "bcca", k = 2
输出：4
解释：s 中我们有 f('a') = 1 ，f('b') = 1 和 f('c') = 2 。
s 的 k 子序列为：
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('a') = 2
bcca ，美丽值为 f('c') + f('a') = 3
bcca ，美丽值为 f('c') + f('a') = 3
总共有 4 个 k 子序列美丽值为最大值 3 。
所以答案为 4 。


    **示例 2：**

    
输入：s = "abbcd", k = 4
输出：2
解释：s 中我们有 f('a') = 1 ，f('b') = 2 ，f('c') = 1 和 f('d') = 1 。
s 的 k 子序列为：
abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5
abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 
总共有 2 个 k 子序列美丽值为最大值 5 。
所以答案为 2 。


     

    **提示：**

    - `1 <= s.length <= 2 * 105`
    - `1 <= k <= s.length`
    - `s` 只包含小写英文字母。

    #### 地址

    https://leetcode.cn/contest/biweekly-contest-112/problems/count-k-subsequences-of-a-string-with-maximum-beauty/

    #### 题意

    >  贪心 + 组合数学

    #### 思路

    1. 刚开始理解的复杂了，实际题目只需要求出最大美丽值的子数组的数目，什么时候才能组成最大的美丽值，简单的贪心就可；

       + 由于 $k$ 序列的长度为 $k$，且每个子序列的中的字符都唯一，因此 $k$ 最长的长度只能为 $26$;

       + 如果 $k$ 大于当前字符串中的字符种类数目，则此时直接返回 $0$, 此时无法实现；

       + 统计每个字符出现的次数为 $f[x]$，则此时我们直接选取出现次数最多的 $k$ 个字符即可，但是需要注意的是第 $k$ 个字符可能有多种选择，这就涉及到组合数学的问题；

       + 设出现次数排在第 $k$ 的字符为 $a$, 则此时它出现的次数为 $f[a]$, 我们统计出现次数大于 $f[a]$ 的字符个数为 $x$, 等于 $f[a]$ 的字符个数为 $y$, 根据贪心可以知道，只需要贪心的选择出现次数最大的几个字符，此时前 $x$ 个字符肯定是要选择的，然后需要在 $y$ 中选择 $k-x$ 个字符即可，则此时可以知道总的可以选择的次数为:

         $$\sum_{i=1}^{x}f(a_i) \times C_{y}^{k-x}f(a_{x+1})^{k-x}$$
        其中 $a_i$ 表示次数从大到小排在第 $i$ 位的字符；
    2. 复杂度分析：
    + 时间复杂度：$O(n + |\Sigma| ^ 2)$，其中 $n$ 表示字符串的长度，$|\Sigma|$ 表示字符集的大小。
    + 空间复杂度：$O(|\Sigma| ^ 2)$，其中 $|\Sigma|$ 表示字符集的大小。

    #### 代码

    ```C++
    class Solution {
    public:
        int countKSubsequencesWithMaxBeauty(string s, int k) {
            long long mod = 1e9 + 7;
            vector<vector<long long>> comb(27, vector<long long>(27, 0));
            for (int i = 0; i <= 26; i++) {
                comb[i][0] = 1;
                comb[i][i] = 1;
            }
            for (int i = 1; i <= 26; i++) {
                for (int j = 1; j < i; j++) {
                    comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
                }
            }

            int n = s.size();
            unordered_map<char, int> cnt;
            vector<int> arr;
            for (auto c : s) {
                cnt[c]++;
            }
            if (k > cnt.size()) return 0;
            for (auto [_, x] : cnt) {
                arr.emplace_back(x);
            }
            if (arr.size() < k) return 0;
            sort(arr.begin(), arr.end(), [](int x, int y) {
                return x > y;
            });
            long long res = 1;
            int x = arr[k - 1];
            int count = 0;
            for (int i = 0; i < arr.size(); i++) {
                if (arr[i] == x) count++;
                if (arr[i] > x) {
                    res = (res * arr[i]) % mod;
                    k--;
                }
            }
            for (int i = 0; i < k; i++) {
                res = (res * x) % mod;
            }
            res = (res * comb[count][k]) % mod;
            return res;
        }
    };

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

Tags: 题解 力扣周赛赛
← leetcode weekly contes 362 leetcode biweekly contes 113 →

扫描二维码，分享此文章