Leetcode 374场周赛

Q1 100143. 统计已测试设备 [Easy] 题解

Q2 100155. 双模幂运算 [Medium] 题解

Q3 100137. 统计最大元素出现至少 K 次的子数组 [Hard] 题解

Q4 100136. 统计好分割方案的数目 [Hard] 题解

100143. 统计已测试设备

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

如果 batteryPercentages[i]大于 0：
- 增加已测试设备的计数。
- 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
- 移动到下一个设备。
否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

思路

暴力模拟一下

代码

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int n = batteryPercentages.size();
        int ans = 0;
        for (int i = 0;i < n;i++){
            if (batteryPercentages[i] > 0){
                ans++;
                for (int j = i+1;j < n;j++){
                    batteryPercentages[j] = max(0, batteryPercentages[j] - 1);
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间：O(n)。
空间：O(1)。

100155. 双模幂运算

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

0 <= i < variables.length
((ai^bi % 10)^ci) % mi == target

返回一个由 好下标 组成的数组，顺序不限 。

思路

用 python 自带的pow函数，可以传入取模参数。
C++手写一个快速幂。

代码

python

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = []
        x = 0
        for a, b, c, m in variables:
            tp = pow(a, b, 10)
            if pow(tp, c, m) == target:
                ans.append(x)
            x += 1
        return ans

C++

class Solution {
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        vector<int> ans;
        typedef long long ll;
        function<int(ll, ll, ll)> qpow = [&](ll a, ll b, ll m){
            ll res = 1;
            while (b){
                if (b&1) res = (res*a)%m;
                a = a*a%m;
                b >>= 1;
            }
            return (int)res;
        };
        int x = 0;
        for (vector<int>& x : variables){
            int a = x[0], b = x[1], c = x[2], m = x[3];
            if (qpow(qpow(a, b, 10), c, m) == target){
                ans.push_back(x);
            }
            x += 1;
        }
        return ans;
    }
};

复杂度分析

时间：O(n*log v)。n，v 分别是 variables 数组长度和 bi, ci 最大值。
空间：O(1)。

100137. 统计最大元素出现至少 K 次的子数组

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

请你统计有多少满足「 nums 中的最大元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

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

思路

~~一开始看成恰好出现 k 次了~~

枚举子数组的结尾i，再维护下标 j (nums[j]=MAXV)表示区间 [j, i]中有 k 个最大值，那么区间 [1, i], [2, i], ⋯, [j, i]都是符合要求的区间。因此答案增加 j。

代码

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size(), maxv = *max_element(nums.begin(), nums.end()), cnt = 0;
        vector<int> idx;
        for (int i = 0;i < n;i++){
            if (nums[i] == maxv){
                idx.push_back(i);
                cnt++;
            }
        }
        if (cnt < k) return 0;
        long long ans = 0;
        for (int i = 0, j = 0;i < n;i++){
            if (j < cnt && idx[j] <= i) j++;
            if (j >= k){
                ans += idx[j-k]+1L;
            }
        }
        return ans;
    }
};

复杂度分析

时间：O(n)。
空间：O(n)。

100136. 统计好分割方案的数目

给你一个下标从 0 开始、由 正整数 组成的数组 nums。

将数组分割成一个或多个连续子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。

返回 nums 的 好分割方案 的数目。

由于答案可能很大，请返回答案对 109 + 7 取余的结果。

思路

首先找出该数组究竟可以分成几段区间
- 利用哈希表记录所有元素最后出现的位置
- 依次遍历，同时维护遍历到的元素最后出现位置的最大值。
- 如果遍历的下标大于之前遍历的元素最后出现位置的最大值，则说明可以成为一段
1. 分割方案就相当于：对这 t 个不相交的区间有多少种合并方式。相当于往 t 个区间中插入 0,1,2…(t-1)个板子，两两板子之间的区间进行合并。组合数学中经典隔板法。

代码

class Solution {
public:
    int numberOfGoodPartitions(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        for (int i = 0;i < n;i++){
            mp[nums[i]] = i;
        }
        int cnt = 0;
        for (int i = 0;i < n;){
            int j = i, ed = mp[nums[j]];
            while (j <= ed){
                ed = max(ed, mp[nums[j]]);
                j++;
            }
            cnt++;
            i = j;
        }
        typedef long long ll;
        function<int(ll, ll, ll)> qpow = [&](ll a, ll b, ll m){
            ll res = 1;
            while (b){
                if (b&1) res = (res*a)%m;
                a = a*a%m;
                b >>= 1;
            }
            return (int)res;
        };
        long long M = 1e9+7, ans = qpow(2, cnt-1, M);
        return (int)ans;
    }
};

复杂度分析

时间：O(n)。
空间：O(n)。