本文主要是介绍第 402 场 LeetCode 周赛题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
A 构成整天的下标对数目 I
计数:遍历 h o u r s hours hours ,记录 h o u r s [ i ] % 24 hours[i]\%24 hours[i]%24 的出现次数
class Solution {public:long long countCompleteDayPairs(vector<int>& hours) {vector<int> cnt(24);long long res = 0;for (auto x : hours) {res += cnt[(24 - x % 24) % 24];cnt[x % 24]++;}return res;}
};
B 构成整天的下标对数目 II
计数:遍历 h o u r s hours hours ,记录 h o u r s [ i ] % 24 hours[i]\%24 hours[i]%24 的出现次数
class Solution {public:long long countCompleteDayPairs(vector<int>& hours) {vector<int> cnt(24);long long res = 0;for (auto x : hours) {res += cnt[(24 - x % 24) % 24];cnt[x % 24]++;}return res;}
};
C 施咒的最大总伤害
动态规划:设 p [ i ] p[i] p[i] 为最大伤害值不超过 i i i 的最大伤害值之和
class Solution {public:using ll = long long;long long maximumTotalDamage(vector<int>& power) {map<int, ll> s;for (auto x : power)s[x] += x;map<int, ll> p;for (auto it = s.begin(); it != s.end(); it++) {p[it->first] = it == s.begin() ? 0 : p[prev(it)->first];auto lb = s.lower_bound(it->first - 2);if (lb == s.begin())p[it->first] = max(p[it->first], it->second);else {p[it->first] = max(p[it->first], p[prev(lb)->first] + it->second);}}return p.rbegin()->second;}
};
D 数组中的峰值
树状数组:用树状数组维护前缀区间内的峰值元素数,对于更新 n u m s [ i n d e x ] nums[index] nums[index] 的操作,可能改变是否为峰值的位置有 i n d e x − 1 index-1 index−1 、 i n d e x index index 和 i n d e x + 1 index+1 index+1
class Solution {public:vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();BinaryIndexedTree bit(n);auto isval = [](int i, int j, int k) { return j > i && j > k; };for (int i = 1; i < n - 1; i++)if (isval(nums[i - 1], nums[i], nums[i + 1]))bit.add(i + 1, 1);//初始化vector<int> res;for (auto& qi : queries) {if (qi[0] == 1) {if (qi[2] - qi[1] + 1 > 2)res.push_back(bit.query(qi[2]) - bit.query(qi[1] + 1));elseres.push_back(0);} else { // updateint i = qi[1];int val = qi[2];if (i - 1 > 0) {//判断nums[i-1]是否改变峰值性if (!isval(nums[i - 2], nums[i - 1], nums[i]) && isval(nums[i - 2], nums[i - 1], val))bit.add(i - 1 + 1, 1);else if (isval(nums[i - 2], nums[i - 1], nums[i]) && !isval(nums[i - 2], nums[i - 1], val))bit.add(i - 1 + 1, -1);}if (i + 1 < n - 1) {//判断nums[i+1]是否改变峰值性if (!isval(nums[i], nums[i + 1], nums[i + 2]) && isval(val, nums[i + 1], nums[i + 2]))bit.add(i + 1 + 1, 1);else if (isval(nums[i], nums[i + 1], nums[i + 2]) && !isval(val, nums[i + 1], nums[i + 2]))bit.add(i + 1 + 1, -1);}if (i != 0 && i != n - 1) {//判断nums[i]是否改变峰值性if (!isval(nums[i - 1], nums[i], nums[i + 1]) && isval(nums[i - 1], val, nums[i + 1]))bit.add(i + 1, 1);if (isval(nums[i - 1], nums[i], nums[i + 1]) && !isval(nums[i - 1], val, nums[i + 1]))bit.add(i + 1, -1);}nums[i] = val;}}return res;}class BinaryIndexedTree {//树状数组模板public:int N;vector<int> a;BinaryIndexedTree(int n) {N = n;a = vector<int>(N + 1);}inline int lowbit(int x) {return x & -x;}void add(int loc, int val) { // li[loc]+=val;for (; loc <= N; loc += lowbit(loc))a[loc] += val;}int query(int loc) { // sum{li[k] | 1<=k<=loc}int res = 0;for (; loc > 0; loc -= lowbit(loc))res += a[loc];return res;}};
};
这篇关于第 402 场 LeetCode 周赛题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!