且听疯吟

leetcode biweekly contes 109

2023-07-31

leetcode biweekly contes 109

本周的题目质量还可以，都不算太难，题目本身质量还算比较高的，已经连续在残酷刷题群生存 $208$ 天了，基本上没啥大问题了。

2784. 检查数组是否是好的

给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个 好 数组。

base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n 两次的一个数组）。比方说，base[1] = [1, 1] ，base[3] = [1, 2, 3, 3] 。

如果数组是一个好数组，请你返回 true ，否则返回 false 。

注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。

示例 1：

输入：nums = [2, 1, 3]
输出：false
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 。但是 base[3] 有 4 个元素，但数组 nums 只有 3 个元素，所以无法得到 base[3] = [1, 2, 3, 3] 的排列，所以答案为 false 。

示例 2：

输入：nums = [1, 3, 3, 2]
输出：true
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 ，可以看出数组是 base[3] = [1, 2, 3, 3] 的一个排列（交换 nums 中第二个和第四个元素）。所以答案为 true 。

示例 3：

输入：nums = [1, 1]
输出：true
解释：因为数组的最大元素是 1 ，唯一可以构成这个数组的 base[n] 对应的 n = 1，可以看出数组是 base[1] = [1, 1] 的一个排列。所以答案为 true 。

示例 4：

输入：nums = [3, 4, 4, 1, 2, 1]
输出：false
解释：因为数组的最大元素是 4 ，唯一可以构成这个数组的 base[n] 对应的 n = 4 。但是 base[n] 有 5 个元素而 nums 有 6 个元素。所以答案为 false 。

提示：

  • 1 <= nums.length <= 100
  • 1 <= num[i] <= 200

地址

https://leetcode.cn/contest/biweekly-contest-109/problems/check-if-array-is-good/

题意

直接模拟

思路

  1. 直接模拟即可，直接模拟即可，按照题意检测数组排序后是否为好数组；
  2. 复杂度分析：
  • 时间复杂度：$O(n \log n)$。
  • 空间复杂度：$O(1)$。

代码

[sol1-C++]
class Solution {
public:
    bool isGood(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int x = nums.back();
        if (n != x + 1) {
            return false;
        }
        for (int i = 1; i <= x; i++) {
            if (nums[i - 1] != i) {
                return false;
            }
        }
        return true;
    }
};

2785. 将字符串中的元音字母排序

给你一个下标从 0 开始的字符串 s ，将 s 中的元素重新 排列 得到新的字符串 t ，它满足：

  • 所有辅音字母都在原来的位置上。更正式的，如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母，那么 t[i] = s[i] 。
  • 元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足 0 <= i < j < s.length 的下标 i 和 j ，如果 s[i] 和 s[j] 都是元音字母，那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。

请你返回结果字母串。

元音字母为 'a' ，'e' ，'i' ，'o' 和 'u' ，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。

示例 1：

输入：s = "lEetcOde"
输出："lEOtcede"
解释：'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。

示例 2：

输入：s = "lYmpH"
输出："lYmpH"
解释：s 中没有元音字母（s 中都为辅音字母），所以我们返回 "lYmpH" 。

提示：

  • 1 <= s.length <= 105
  • s 只包含英语字母表中的 大写 和 小写 字母。

地址

https://leetcode.cn/contest/biweekly-contest-109/problems/sort-vowels-in-a-string/

题意

排序

思路

  1. 题目非常简单，我们将元音字符取出来，按照元音字母的顺序进行排序，然后再将其放回到相应的位置即可。

  2. 复杂度分析：

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

代码

class Solution {
public:
    string sortVowels(string s) {
        int n = s.size();
        vector<char> t = {'a', 'e', 'i', 'o', 'u'};
        unordered_set<char> cnt(t.begin(), t.end());
        vector<char> arr;
        vector<int> brr;
        for (int i = 0; i < n; i++) {
            if (cnt.count(tolower(s[i]))) {
                arr.emplace_back(s[i]);
                brr.emplace_back(i);
            }
        }
        sort(arr.begin(), arr.end());
        sort(brr.begin(), brr.end());
        for (int i = 0; i < brr.size(); i++) {
            s[brr[i]] = arr[i];
        }
        return s;
    }
};

2786. 访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

  • 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
  • 对于你访问的位置 i ，你可以获得分数 nums[i] 。
  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

示例 1：

输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

提示：

  • 2 <= nums.length <= 105
  • 1 <= nums[i], x <= 106

地址

https://leetcode.cn/contest/biweekly-contest-109/problems/visit-array-positions-to-maximize-score/

题意

动态规划

思路

  1. 设 $dp[i][0]$ 表示跳转前 $i$ 个位置且最后一个元素为偶数时的最大得分，$dp[i][1]$ 表示跳转前 $i$ 个位置且最后一个元素是奇数时的最大得分，因此我们可以有如下判断：

    • 当第 $i$ 个元素是偶数时，此时可以由某个奇数跳转到第 $i$ 时，此时的得分为 $dp[i-1][1] - x + nums[i]$，由某个偶数跳转到 $i$ 时，则此时的得分为 $dp[i-1][0] + nums[i]$, 此时可以得到递推公式如下：
      • $dp[i][0] = \max(dp[i-1][1] - x + nums[i], dp[i-1][0] + nums[i])$
    • 当第 $i$ 个元素是奇数时，此时可以由某个奇数跳转到第 $i$ 时，此时的得分为 $dp[i-1][1] + nums[i]$，由某个偶数跳转到 $i$ 时，则此时的得分为 $dp[i-1][0] - x + nums[i]$, 此时可以得到递推公式如下：
      • $dp[i][1] = \max(dp[i-1][0] - x + nums[i], dp[i-1][1] + nums[i])$

  2. 需要注意的是比较坑的是位置 $0$ 时也需要计算得分，此时位置 $0$ 的得分如下：

    • 如果 $nums[0]$ 为奇数：$dp[0][0] = -x, dp[0][1] = nums[0]$;
    • 如果 $nums[0]$ 为偶数：$dp[0][0] = nums[0], dp[0][1] = -x$;

  3. 复杂度分析：

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

代码

class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();
        vector<long long> dp(2);
        if (nums[0] & 1) {
            dp[1] = nums[0];
            dp[0] = -x;
        } else {
            dp[0] = nums[0];
            dp[1] = -x;
        }
        for (int i = 1; i < n; i++) {
            vector<long long> ndp = dp;
            if (nums[i] & 1) {
                ndp[1] = max(dp[0] - x + nums[i], dp[1] + nums[i]);
            } else {
                ndp[0] = max(dp[1] - x + nums[i], dp[0] + nums[i]);
            }
            dp = move(ndp);
        }
        return max(dp[0], dp[1]);
    }
};

2787. 将一个数字表示成幂的和的方案数

给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

提示：

  • 1 <= n <= 300
  • 1 <= x <= 5

地址

https://leetcode.cn/contest/biweekly-contest-109/problems/ways-to-express-an-integer-as-sum-of-powers/

题意

0,1背包

思路

  1. 刚开始想的太复杂了，实际本题目即为简单的 $0,1$ 背包即可解决当前问题，由于只有 $n$ 个数，我们可以提前计算出 $n$ 个数的 $x$ 次方方，然后在这 $n$ 个数刚好取出 $m$ 个数，使得 $m$ 个数的和恰好等于 $n$ 即可，典型的 $0,1$ 背包问题，取与不取，参考相关模板即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的元素。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定的元素。

代码

class Solution {
public:
    int numberOfWays(int n, int x) {
        long long mod = 1e9 + 7;
        vector<long long> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= 0 ; j--) {
                if (dp[j] > 0 &&  j + pow(i, x) <= n) {
                    dp[j + pow(i, x)] = (dp[j + pow(i, x)] + dp[j]) % mod;
                }
            }
        }
        return dp[n];
    }
};

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

Tags: 题解 力扣周赛赛
← leetcode weekly contes 356 leetcode biweekly contes 110 →

扫描二维码，分享此文章