leetcode weekly contest 336

本场周赛第四题还算比较新的题目。

6315. 统计范围内的元音字符串数

给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。

如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。

返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

示例 1：

输入：words = ["are","amy","u"], left = 0, right = 2
输出：2
解释：
- "are" 是一个元音字符串，因为它以 'a' 开头并以 'e' 结尾。
- "amy" 不是元音字符串，因为它没有以元音字母结尾。
- "u" 是一个元音字符串，因为它以 'u' 开头并以 'u' 结尾。
在上述范围中的元音字符串数目为 2 。

示例 2：

输入：words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
输出：3
解释：
- "aeo" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
- "mu" 不是元音字符串，因为它没有以元音字母开头。
- "ooo" 是一个元音字符串，因为它以 'o' 开头并以 'o' 结尾。
- "artro" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
在上述范围中的元音字符串数目为 3 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 10
words[i] 仅由小写英文字母组成
0 <= left <= right < words.length

地址

https://leetcode.cn/contest/weekly-contest-336/problems/count-the-number-of-vowel-strings-in-range/

题意

直接遍历

思路

直接遍历所有的字符串即可，找到符合要求的字符串即可，检测每个字符的首字符与末尾的字符是否为元音字母。
复杂度分析：

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

代码

class Solution {
public:
    int vowelStrings(vector<string>& words, int left, int right) {
        vector<char> arr = {'a','e','i','o','u'};
        unordered_set<char> cnt(arr.begin(), arr.end());
        int res = 0;
        for (int i = left; i <= right; i++) {
            if (cnt.count(words[i][0]) && cnt.count(words[i].back())) {
                res++;
            }
        }
        return res;
    }
};

6316. 重排数组以得到最大前缀分数

给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。

令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的分数是 prefix 数组中正整数的个数。

返回可以得到的最大分数。

示例 1：

输入：nums = [2,-1,0,1,-3,3,-3]
输出：6
解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。

示例 2：

输入：nums = [-2,-3,0]
输出：0
解释：不管怎么重排数组得到的分数都是 0 。

提示：

1 <= nums.length <= 105
-106 <= nums[i] <= 106

https://leetcode.cn/contest/weekly-contest-336/problems/rearrange-array-to-maximize-prefix-score/

题意

排序

思路

贪心即可，我们将所有的元素按照从大到小的顺序进行排序，这样即可保证前缀中为正整数的数量尽可能的多，因为遇到负数时，所有的正整数全部都已经包含在其中。
复杂度分析：

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

代码

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end(), [&](int a, int b) {
            return a > b;
        });
        long long sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > 0) {
                ans++;
            }
        }
        return ans;
    }
};

6317. 统计美丽子数组数目

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个美丽的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

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

示例 1：

输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
  - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
  - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-336/problems/count-the-number-of-beautiful-subarrays/

题意

动态规划

思路

本题与力扣的某个题目基本上是一模一样的，由于每次减法两个数的第 $i$ 位，即一定存在两个数的第 $i$ 位均为 $1$。我们用 $mask$ 表示子序列中第 $i$ 位的数目的统计情况，存在奇数个元素的第 $i$ 位的为 $1$ ，此时 $mask$ 的第 $i$ 位为 $1$，否则第 $i$ 位为 $0$。如果满足题目要求，则我们知道一定满足存在偶数个元素使得其相同的第 $k$ 位都一定为 $1$，这样我们才能执行同时减去 $2^k$。我们找到当前前缀中 $mask$ 的每一位的奇偶性与当前的奇偶性相同的位置的个数，则从这些位置 $j$ 到当前位置$i$ 之间的子序列构成的一定满足题目要求。
复杂度分析：

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

代码

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        int mask = 0;
        long long ans = 0;
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            mask ^= nums[i];
            ans += cnt[mask]; 
            cnt[mask]++;
        }
        return ans;
    }
};

6318. 完成所有任务的最少时间

你有一台电脑，它可以同时运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。

当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。

请你返回完成所有任务的情况下，电脑最少需要运行多少秒。

示例 1：

输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
输出：2
解释：
- 第一个任务在闭区间 [2, 2] 运行。
- 第二个任务在闭区间 [5, 5] 运行。
- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
电脑总共运行 2 个整数时间点。

示例 2：

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
输出：4
解释：
- 第一个任务在闭区间 [2, 3] 运行
- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
- 第三个任务在闭区间 [5, 6] 运行。
电脑总共运行 4 个整数时间点。

提示：

1 <= tasks.length <= 2000
tasks[i].length == 3
1 <= starti, endi <= 2000
1 <= durationi <= endi - starti + 1

地址

https://leetcode.cn/contest/weekly-contest-335/problems/number-of-ways-to-earn-points/

题意

贪心

思路

最开始的贪心策略想错了，想成每次选择重叠数目最多的时间点了，这样我们就可能尽可能的少，但实际存在错误。实际的贪心规则时，优先选择每个序列每个区间的后缀，这样就能保证在去区间的时候尽量保证做到最优。
- 首先按照结束时间从小到大进行排序；
- 用数组标记已经取过的时间点，依次统计当前区间已经覆盖的时间点 $count$，如果 $count < tasks[i][2]$，表示还需要再该区间中再取部分点，此时我们依次从右向左取未访问过的时间点，直到 $count == tasks[i][2]$ 时结束；
- 对已经访问过的点同时进行标记。
复杂度分析：

时间复杂度：$O(n \times U)$，其中$ n$ 表示数组的长度，$U$ 表示题目中的左右边界的最大值。
空间复杂度：$O(U)$。其中 $U$ 表示题目中的左右边界的最大值。

代码

class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [&](const vector<int> &a, const vector<int> &b) {
           return a[1] < b[1]; 
        });
        
        int n = tasks.size();
        int total = 0;
        vector<bool> visit(2002, false);
        for (int i = 0; i < n; i++) {
            int start = tasks[i][0], end = tasks[i][1];
            int count = 0;
            for (int j = start; j <= end; j++) {
                if (visit[j]) {
                    count++;
                }
            }
            if (count >= tasks[i][2]) continue;
            for (int j = end, k = tasks[i][2] - count; j >= start && k > 0; j--) {
                if (!visit[j]) {
                    visit[j] = true;
                    total++;
                    k--;
                }
            }
        }
        return total;
    }
};

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

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

Tags: 力扣周赛题解

← Awesome Courses leetcode biweekly contest 100 →

扫描二维码，分享此文章