力扣第375場周賽

統計已測試設備

差分數組優化

class Solution {
public:int countTestedDevices(vector<int> &batteryPercentages) {int dec = 0;for (int x : batteryPercentages) {dec += x > dec;}return dec;}
};

雙模冪運算

快速冪模擬

class Solution {
public:long long qmi(int a, int b, int p)// a^b % p{long long res = 1 % p;while (b){if (b & 1) res = res * a % p;a = a * (long long)a % p;b >>= 1;}return res;}vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {int n = variables.size();vector<int> ans;for(int i = 0 ; i < n ; i ++){int ai = variables[i][0] , bi = variables[i][1] , ci = variables[i][2] , mi = variables[i][3];if(qmi(qmi(ai , bi , 10) , ci , mi) == target)ans.push_back(i);}return ans;}
};

統計最大元素出現至少 K 次的子數組

滑窗統計K 次

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {int n = nums.size() , maxn = -1 ;for(auto x : nums)maxn = max(maxn , x);unordered_map<int , int> m;long long ans = 0;for(int i = 0 , j = 0 ; i < n ; i ++){m[nums[i]] ++;while(m[maxn] >= k){m[nums[j++]] --;}ans += j;}return ans;}
};

統計好分割方案的數目

區間合并求個數

class Solution {
public:int numberOfGoodPartitions(vector<int>& nums) {//找區間unordered_map<int,pair<int,int>> ps;for(int i = 0 ; i < nums.size() ; i ++){int x = nums[i];auto it = ps.find(x);if(it != ps.end()){it ->second.second = i;}else {ps[x] = {i , i};}}vector<pair<int,int>> a;for(auto &[_ , p] : ps){a.emplace_back(p);}//排序區間sort(a.begin() , a.end() , [](const auto &p , const auto &q){return p.first < q.first;});//區間合并int ans = 1;int max_r = a[0].second;for(int i = 1 ; i < a.size() ; i ++){int left = a[i].first , right = a[i].second;if(left > max_r){ans = ans * 2 % 1'000'000'007;}max_r = max(max_r, right);}return ans;}
};

–