Leetcode第375场周赛题解

Leetcode 第 375 场周赛题解 Leetcode 第 375 场周赛题解题目1：2960. 统计已测试设备思路代码复杂度分析 题目2：2961. 双模幂运算思路代码复杂度分析 题目3：2962. 统计最大元素出现至少 K 次的子数组思路代码复杂度分析 题目4：2963. 统计好分割方案的数目思路代码复杂度分析

Leetcode 第 375 场周赛题解 题目1：2960. 统计已测试设备 思路

按题意模拟即可。

代码 /* * @lc app=leetcode id=2960 lang=cpp * * [2960] 统计已测试设备 */ // @lc code=start class Solution { public: int countTestedDevices(vector<int> &batteryPercentages) { if (batteryPercentages.empty()) return 0; int count = 0; for (int i = 0; i < batteryPercentages.size(); i++) { if (batteryPercentages[i] > 0) { count++; for (int j = i + 1; j < batteryPercentages.size(); j++) batteryPercentages[j] = max(0, batteryPercentages[j] - 1); } } return count; } }; // @lc code=end 复杂度分析

时间复杂度：O(n2)，其中 n 是数组 batteryPercentages 的长度。

空间复杂度：O(1)。

题目2：2961. 双模幂运算 思路

快速幂。

带模运算的快速幂：

long long myPow(long long x, int n, const int mod) { long long res = 1; while (n) { if (n % 2) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; }

遍历数组 variables，设 a = variables[i][0]、b = variables[i][1]、c = variables[i][2]、m = variables[i][3]，当满足 myPow(myPow(a, b, 10), c, m) == target 时，将下标 i 插入 goodIndices 中，最后返回数组 goodIndices。

代码 /* * @lc app=leetcode id=2961 lang=cpp * * [2961] 双模幂运算 */ // @lc code=start // 快速幂 class Solution { public: vector<int> getGoodIndices(vector<vector<int>> &variables, int target) { vector<int> goodIndices; for (int i = 0; i < variables.size(); i++) { long long a = variables[i][0]; int b = variables[i][1]; int c = variables[i][2]; int m = variables[i][3]; if ((int)myPow(myPow(a, b, 10), c, m) == target) goodIndices.push_back(i); } return goodIndices; } // 辅函数 - 快速幂 long long myPow(long long x, int n, const int mod) { long long res = 1; while (n) { if (n % 2) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } }; // @lc code=end 复杂度分析

时间复杂度：O(nlogU)其中 n 为数组 variables 的长度，U 为 bi 和 ci 的最大值， 本题为 103。

空间复杂度：O(1)。

题目3：2962. 统计最大元素出现至少 K 次的子数组 思路

滑动窗口。

算法如下：

设 mx = max⁡(nums)。右端点 right 从左到右遍历 nums。遍历到元素 x=nums[right] 时，如果 x=mx，就把计数器 count_mx 加一。如果此时 count_mx>=k，则不断右移左指针 left，直到窗口内的 mx 的出现次数小于 k 为止。此时，对于右端点为 right 且左端点小于 left 的子数组，mx 的出现次数都至少为 k，把答案增加 left。 代码 /* * @lc app=leetcode id=2962 lang=cpp * * [2962] 统计最大元素出现至少 K 次的子数组 */ // @lc code=start // 滑动窗口 class Solution { public: long long countSubarrays(vector<int> &nums, int k) { int mx = *max_element(nums.begin(), nums.end()); long long ans = 0; int count_mx = 0, left = 0; for (int right = 0; right < nums.size(); right++) { if (nums[right] == mx) count_mx++; while (count_mx >= k) { if (nums[left] == mx) count_mx--; left++; } // [0, right],...,[left-1, right] 是 mx 至少出现 k 次的子数组 ans += left; } return ans; } }; // @lc code=end 复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

题目4：2963. 统计好分割方案的数目 思路

合并区间。

考虑如下数组：[3,1,2,1,2,4,4]，题目要求相同数字必须在同一个子数组中，所以两个 1 必须在同一个子数组，两个 2 也必须在同一个子数组。所以 [1,2,1,2] 这一段必须是完整的，不能分割。

把该数组分到无法再分，得到：[3]+[1,2,1,2]+[4,4]，考虑每个 + 号选或不选，一共有 22=4 种好分割方案。

代码实现时，用一个哈希表/有序集合记录每个元素首次出现的位置和最后一次出现的位置，每个元素就对应着一个不可分割的区间。然后按照 56. 合并区间 的做法，把这些区间都合并起来。假设合并后的区间个数为 m，那么答案就是 2m-1 % (109 + 7)。

代码 /* * @lc app=leetcode id=2963 lang=cpp * * [2963] 统计好分割方案的数目 */ // @lc code=start class Solution { private: static bool cmp(vector<int> &a, vector<int> &b) { return a[0] < b[0]; } public: int numberOfGoodPartitions(vector<int> &nums) { // <num, pair<firstIndex, lastIndex>> unordered_map<int, pair<int, int>> positions; for (int i = 0; i < nums.size(); i++) { int num = nums[i]; auto it = positions.find(num); if (it != positions.end()) it->second.second = i; else positions[num] = pair<int, int>(i, i); } // 合并区间 vector<vector<int>> intervals; for (auto &[_, p] : positions) intervals.push_back({p.first, p.second}); // 按区间左端点排序 sort(intervals.begin(), intervals.end(), cmp); vector<vector<int>> merge; for (int i = 0; i < intervals.size(); i++) { int left = intervals[i][0], right = intervals[i][1]; if (merge.empty() || merge.back()[1] < left) merge.push_back(intervals[i]); else merge.back()[1] = max(merge.back()[1], right); } return (int)myPow(2, merge.size() - 1, 1e9 + 7); } // 辅函数 - 快速幂 long long myPow(long long x, int n, const int mod) { long long res = 1; while (n) { if (n & 01) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } }; // @lc code=end 复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。