第 375 场 LeetCode 周赛题解

2023-12-13 08:08:17

A 统计已测试设备

在这里插入图片描述
在这里插入图片描述

模拟:记录当前已测试设备数量

class Solution {
public:
    int countTestedDevices(vector<int> &batteryPercentages) {
        int res = 0;
        int s = 0;
        for (auto x: batteryPercentages) {
            if (x - s > 0) {
                res++;
                s++;
            }
        }
        return res;
    }
};

B 双模幂运算

在这里插入图片描述

快速幂

class Solution {
public:
    int fpow(int x, int n, int mod) {// x^n%mod
        int res = 1;
        for (int e = x; n; e = e * e % mod, n >>= 1)
            if (n & 1)
                res = res * e % mod;
        return res;
    }

    vector<int> getGoodIndices(vector<vector<int>> &variables, int target) {
        vector<int> res;
        for (int i = 0; i < variables.size(); i++)
            if (fpow(fpow(variables[i][0], variables[i][1], 10), variables[i][2], variables[i][3]) == target)
                res.push_back(i);
        return res;
    }
};

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

在这里插入图片描述

滑动窗口:枚举滑窗的左边界 l l l,找到满足条件的最小右边界 r r r ,则左边界为 l l l 的满足条件的子数组数目为 n u m s . s i z e ( ) ? r nums.size()-r nums.size()?r

class Solution {
public:
    long long countSubarrays(vector<int> &nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());
        int n = nums.size();
        long long res = 0;
        int cnt = 0;
        for (int l = 0, r = -1; l < n;) {
            while (cnt < k && r + 1 < n)
                if (nums[++r] == mx)
                    cnt++;
            if (cnt < k)
                break;
            res += n - r;
            if (nums[l++] == mx)
                cnt--;
        }
        return res;
    }
};

D 统计好分割方案的数目

在这里插入图片描述

计数:因为相同数字必须在一个子数组中,所以可以预先求出 n u m s nums nums 按要求最多可以划分成的子数组数目 c n t cnt cnt,原数组好分割方案数目等于 c n t cnt cnt 个互不相同的数形成的数组的好分割方案数目,即 2 c n t ? 1 2^{cnt-1} 2cnt?1

class Solution {
public:
    int numberOfGoodPartitions(vector<int> &nums) {
        int n = nums.size();
        unordered_map<int, int> r;//记录每个数出现的最右小标
        for (int i = 0; i < n; i++)
            r[nums[i]] = i;
        int cnt = 0;//按要求最多可以划分成的子数组数目
        for (int i = 0, right = r[nums[0]]; i < n;) {
            if (i != right) {
                right = max(right, r[nums[i++]]);
            } else {
                cnt++;
                if (i == n - 1)
                    break;
                right = r[nums[++i]];
            }
        }
        int mod = 1e9 + 7;
        int res = 1;
        for (int i = 0; i < cnt - 1; i++)
            res = res * 2 % mod;
        return (res + mod) % mod;
    }
};

文章来源:https://blog.csdn.net/weixin_40519680/article/details/134912754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。