img
力扣第402场周赛
A
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int countCompleteDayPairs(vector<int>& hours) {
int n = hours.size(), ans = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if((hours[i] + hours[j]) % 24 == 0) ans++;
}
}
return ans;
}
};
|
B
直接用哈希：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
long long countCompleteDayPairs(vector<int>& hours) {
vector<int> res(24);
long long total = 0;
for(int i:hours)
{
if(i % 24 == 0)
{
total += res[0];
}
else
{
total += res[24-(i%24)];
}
res[i%24] += 1;
}
return total;
}
};
|
C
先进行一个映射，然后进行dp。因为选择一个物品，贪心的想每一个物品都要选，然后下一个物品要大于2才能转移，直接使用双指针进行移动就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
long long maximumTotalDamage(vector<int>& power)
{
unordered_map<int, int> mp;
for (int x : power)
{
mp[x]++;
}
vector<pair<int, int>> cnt(mp.begin(), mp.end());
int n = cnt.size();
sort(cnt.begin(), cnt.end());
vector<long long> dp(n + 1);
dp[1] =
(long long)cnt[0].first * cnt[0].second;
for (int i = 2, j = 0; i <= n; i++)
{
int x = cnt[i - 1].first;
int c = cnt[i - 1].second;
while (cnt[j].first < x - 2)
{
j++;
}
dp[i] = max(dp[i - 1],
dp[j] + (long long)x * c);
}
return dp[n];
}
};
|
D
用树状数组进行维护：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| const int N = 1e5+10;
int arr[N];
class Solution {
public:
int lowbit(int x)
{
return x&-x;
}
void add(int x,int val,int n)
{
while(x<=n)
{
arr[x] += val;
x += lowbit(x);
}
}
int query(int x)
{
int res = 0;
while(x)
{
res += arr[x];
x -= lowbit(x);
}
return res;
}
vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> ans;
memset(arr,0,sizeof arr);
for(int i=1;i<n-1;i++)
{
if(nums[i]>nums[i-1] && nums[i]>nums[i+1])
{
add(i+1,1,n);
}
}
for(auto &q:queries)
{
if(q[0] == 1)
{
int l = q[1]+1 , r = q[2]+1;
if(r-1<=l) ans.push_back(0);
else ans.push_back(query(r-1) - query(l));
}
else
{
int idx = q[1] , val = q[2];
if(val == nums[idx]) continue;
if(idx-1>0)
{
if(nums[idx-1]>nums[idx-2] && nums[idx-1]>nums[idx])
{
if(val >= nums[idx-1])
{
add(idx-1+1,-1,n);
}
}
if(nums[idx-1]>nums[idx-2] && nums[idx-1]<=nums[idx])
{
if(val < nums[idx-1])
{
add(idx-1+1,1,n);
}
}
}
if(idx < n-2)
{
if(nums[idx+1]>nums[idx] && nums[idx+1]>nums[idx+2])
{
if(val >= nums[idx+1])
{
add(idx+1+1,-1,n);
}
}
if(nums[idx+1]<=nums[idx] && nums[idx+1]>nums[idx+2])
{
if(val < nums[idx+1])
{
add(idx+1+1,1,n);
}
}
}
if(idx == 0 || idx == n-1)
{
nums[idx] = val;
continue;
}
if(nums[idx]>nums[idx-1] && nums[idx]>nums[idx+1])
{
if(val<=nums[idx-1] || val<=nums[idx+1])
{
add(idx+1,-1,n);
}
}
if(nums[idx]<=nums[idx-1] || nums[idx]<=nums[idx+1])
{
if(val>nums[idx-1] && val>nums[idx+1])
{
add(idx+1,1,n);
}
}
nums[idx] = val;
}
}
return ans;
}
};
|
