Title: "[[Weekly-Contest-402]]"
Contest: leetcode
status: DONE
tags: Contest
Rank: 1686
Total: 3283
Credits: 7
T1: Accepted
T2: Accepted
T3: New Complement
T4: New Complement
Author: AllenYGY
created: 2024-06-16T12:09
updated: 2024-06-22T16:18
给你一个整数数组 hours
,表示以 小时 为单位的时间,返回一个整数,表示满足 i < j
且 hours[i] + hours[j]
构成 整天 的下标对 i
, j
的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如,1 天是 24 小时,2 天是 48 小时,3 天是 72 小时,以此类推。
暴力没什么好说的
class Solution {
public:
int countCompleteDayPairs(vector<int>& hours) {
vector<int> remainderCount(24, 0);
int count = 0;
for (int hour : hours) {
int remainder = hour % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
};
给你一个整数数组 hours
,表示以 小时 为单位的时间,返回一个整数,表示满足 i < j
且 hours[i] + hours[j]
构成 整天 的下标对 i
, j
的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如,1 天是 24 小时,2 天是 48 小时,3 天是 72 小时,以此类推。
模运算技巧+哈希优化
0 | 0 |
23 | 1 |
22 | 2 |
21 | 3 |
... | ... |
1 | 23 |
class Solution {
public:
long long countCompleteDayPairs(vector<int>& hours) {
vector<int> remainderCount(24, 0);
long long count = 0;
for (int hour : hours) {
int remainder = hour % 24;
int complement = (24 - remainder) % 24;
count += remainderCount[complement];
remainderCount[remainder]++;
}
return count;
}
};
统计每个元素的出现次数,记到哈希表 cnt 中。将哈希表的 key 整理到数组 a 中,把 a 按照从小到大的顺序排序。
定义 dfs(i) 表示从 a[0] 到 a[i] 中选择,可以得到的伤害值之和的最大值。
考虑 a[i] 选或不选:
递归边界:dfs(−1)=0。没有数可以选,伤害值之和为0。
递归入口:dfs(n−1),即答案。注意这里 n 是 a 的长度,即 power 中的不同元素个数。
代码实现时,j 的计算可以用二分查找,也可以暴力用循环查找。
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
unordered_map<int,int>cnt;
for(int x:power){
cnt[x]++;
}
vector<pair<int,int>>a(cnt.begin(),cnt.end());
ranges::sort(a);
int n = a.size();
vector<long long>f(n+1);
for(int i = 0, j=0; i < n; i++){
auto& [x,c]=a[i];
while(a[j].first < x - 2){
j++;
}
f[i+1]=max(f[i],f[j]+(long long)x*c);
}
return f[n];
}
};
树状数组
class Fenwick {
vector<int> f;
public:
Fenwick(int n) : f(n) {}
void update(int i, int val) {
for (; i < f.size(); i += i & -i) {
f[i] += val;
}
}
int pre(int i) {
int res = 0;
for (; i > 0; i &= i - 1) {
res += f[i];
}
return res;
}
int query(int l, int r) {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1);
}
};
class Solution {
public:
vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
Fenwick f(n - 1);
auto update = [&](int i, int val) {
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
f.update(i, val);
}
};
for (int i = 1; i < n - 1; i++) {
update(i, 1);
}
vector<int> ans;
for (auto& q : queries) {
if (q[0] == 1) {
ans.push_back(f.query(q[1] + 1, q[2] - 1));
continue;
}
int i = q[1];
for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
update(j, -1);
}
nums[i] = q[2];
for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
update(j, 1);
}
}
return ans;
}
};