Skip to content

Commit 6f55538

Browse files
coderharecoderhare
committed
update 84-biweekly and 305 weekly
1 parent 0b3645b commit 6f55538

File tree

2 files changed

+266
-0
lines changed

2 files changed

+266
-0
lines changed

‎leetcode/biweekly/84.md

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
### T1
2+
简单模拟
3+
```c++
4+
class Solution {
5+
int a[1010];
6+
public:
7+
vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
8+
for (auto & it: items1){
9+
a[it[0]] += it[1];
10+
}
11+
for (auto & it: items2){
12+
a[it[0]] += it[1];
13+
}
14+
vector <vector<int>> ans;
15+
for (int i = 1; i <= 1000; i++){
16+
if(a[i]){
17+
ans.push_back({i,a[i]});
18+
}
19+
}
20+
return ans;
21+
}
22+
};
23+
```
24+
25+
### T2
26+
注意到需要找到`j - i != nums[j] - nums[i]`的数对数目，我们可以反向做，就是所有数对数目减去`j - i == nums[j] - nums[i]`的数对数目，
27+
所有数对数目为:`n * (n - 1)/2`，然后变形一下，我们统计`nums[j] - j == nums[i] - i`的数目，这样可以在线性复杂度内完成计数
28+
```c++
29+
class Solution {
30+
using ll = long long;
31+
map <int,int> m;
32+
public:
33+
long long countBadPairs(vector<int>& nums) {
34+
int n = nums.size();
35+
ll ans = n * 1LL * (n - 1)/2;
36+
for (int i = 0; i < n; i++){
37+
if(m.count(nums[i] - i)){
38+
ans-= m[nums[i] - i];
39+
}
40+
m[nums[i] - i]++;
41+
}
42+
return ans;
43+
}
44+
};
45+
```
46+
47+
### T3
48+
简单模拟，每次如果当前时间戳太小，就更新到可以为止
49+
```c++
50+
class Solution {
51+
using ll = long long;
52+
public:
53+
long long taskSchedulerII(vector<int>& tasks, int space) {
54+
int n = tasks.size();
55+
map <int,ll> m;
56+
for (int x: tasks) m[x] = -1e9;
57+
ll ans = 0;
58+
for (int i = 0; i < n; i++){
59+
if(ans - m[tasks[i]] >= space) ans++;
60+
else {
61+
ans = m[tasks[i]] + space + 1;
62+
m[tasks[i]] = ans;
63+
}
64+
m[tasks[i]] = ans;
65+
}
66+
return ans;
67+
}
68+
};
69+
```
70+
71+
### T4
72+
贪心。
73+
首先需要倒着做，正着做的话，还需要考虑后面的数，不可行，
74+
我这里用了非常笨的`O(logn)`方法来得到改变这个数之后，能得到的最大数，因为它显然是有单调性的
75+
```c++
76+
class Solution {
77+
map <int,int> m;
78+
using ll = long long; //greedy
79+
public:
80+
long long minimumReplacement(vector<int>& nums) {
81+
ll ans = 0;
82+
int last = nums.back();
83+
auto check = [&](ll len, ll mid, ll last, ll r)->bool{
84+
ll need = mid - r;
85+
ll k = last - ((need - 1) / len + 1);
86+
return k >= mid;
87+
};
88+
auto get = [&](ll cur, ll len, ll last){
89+
ll l = cur, r = last, ans = l;
90+
while(l <= r){
91+
int mid = (l + r)>>1;
92+
if(check(len, mid, last, cur)) l = mid + 1, ans = mid;
93+
else r = mid - 1;
94+
}
95+
return ans;
96+
};
97+
for (int i = nums.size() - 1; i >= 0; i--){
98+
if(nums[i] > last){
99+
ans += nums[i] / last - 1; //div
100+
if(nums[i] % last == 0) last = last;
101+
else {
102+
//切分为一堆数，保证最小值最大
103+
int len = nums[i] / last;
104+
ans++;
105+
int r = nums[i] % last;
106+
if(r == nums[i] - 1) {
107+
last = nums[i] - 1;
108+
}
109+
else if(r + len > nums[i]) {
110+
last = nums[i] - 1;
111+
}
112+
else { //最大值拟合
113+
last = get(r, len, last);
114+
}
115+
}
116+
}
117+
else last = nums[i];
118+
}
119+
return ans;
120+
}
121+
};
122+
```
123+
但是它还有更好的`O(1)`作法
124+
其实这个值就是看他分割多少次，然后向下取整...
125+
```c++
126+
class Solution {
127+
using ll = long long;
128+
public:
129+
long long minimumReplacement(vector<int>& nums) {
130+
reverse(begin(nums), end(nums));
131+
ll ans = 0, last = 1<<30;
132+
for (int x: nums){
133+
if(x < last) last = x;
134+
else {
135+
int t = (x - 1) / last;
136+
ans += t;
137+
last = x / (t + 1);
138+
}
139+
}
140+
return ans;
141+
}
142+
};
143+
```

‎leetcode/weekly/305.md

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
### T1
2+
由于数据范围比较小可以简单用O(n^3)的循环来暴力枚举，但是也可以使用哈希表或者其他快速查找的数据结构来降低时间复杂度
3+
```c++
4+
class Solution {
5+
public:
6+
int arithmeticTriplets(vector<int>& nums, int diff) {
7+
int n = nums.size(), ans = 0;
8+
for (int i = 0; i < n; i++){
9+
for (int j = i + 1; j < n; j++){
10+
for (int k = j + 1; k < n; k++){
11+
if(nums[j] - nums[i] == nums[k] - nums[j]&& nums[k] - nums[j] == diff){
12+
ans++;
13+
}
14+
}
15+
}
16+
}
17+
return ans;
18+
}
19+
};
20+
```
21+
22+
### T2
23+
简单BFS应用
24+
```c++
25+
class Solution {
26+
vector <int> g[100010];
27+
bool st[100010];
28+
public:
29+
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
30+
for (auto & e: edges){
31+
g[e[0]].push_back(e[1]);
32+
g[e[1]].push_back(e[0]);
33+
}
34+
for (int i: restricted) st[i] = 1;
35+
queue <int> q;
36+
q.push(0);
37+
int ans = 1;
38+
st[0] = 1;
39+
while(q.size()){
40+
auto u = q.front(); q.pop();
41+
for (int v: g[u]){
42+
if(st[v]) continue;
43+
st[v] = 1;
44+
q.push(v);
45+
ans++;
46+
}
47+
}
48+
return ans;
49+
}
50+
};
51+
```
52+
53+
### T3
54+
DFS找可行方案，但由于遍历的方案非常多，所以需要记忆化来剪枝，这里使用记忆化DFS；
55+
但是更好写的做法应该是线性DP
56+
```c++
57+
class Solution {
58+
int f[100010];
59+
public:
60+
bool validPartition(vector<int>& nums) {
61+
int n = nums.size();
62+
memset(f, -1, sizeof f);
63+
auto dfs = [&](auto & dfs, int u)->bool{
64+
if(u == n) return true;
65+
if(f[u] != -1) return f[u];
66+
if(n - u >= 2 && nums[u] == nums[u + 1] && dfs(dfs,u + 2)) {
67+
f[u + 2] = 1;
68+
return true;
69+
}
70+
if(n - u >= 3 && nums[u] == nums[u + 1] && nums[u] == nums[u + 2] && dfs(dfs,u + 3)) {
71+
f[u + 3] = 1;
72+
return true;
73+
}
74+
if(n - u >= 3 && nums[u] == nums[u + 1] - 1 && nums[u] == nums[u + 2] - 2 && dfs(dfs,u + 3)) {
75+
f[u + 3] = 1;
76+
return true;
77+
}
78+
return f[u] = false;
79+
};
80+
return dfs(dfs, 0);
81+
}
82+
};
83+
```
84+
线性DP
85+
```c++
86+
class Solution {
87+
bool f[100010];
88+
public:
89+
bool validPartition(vector<int>& nums) {
90+
int n = nums.size();
91+
f[0] = 1;
92+
for (int i = 0; i < n; i++){
93+
if(f[i]){
94+
if(n - i >= 2 && nums[i] == nums[i + 1]) f[i + 2] = 1;
95+
if(n - i >= 3 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) f[i + 3] = 1;
96+
if(n - i >= 3 && nums[i] == nums[i + 1] - 1&& nums[i] == nums[i + 2] - 2) f[i + 3] = 1;
97+
}
98+
}
99+
return f[n];
100+
}
101+
};
102+
```
103+
104+
### T4
105+
子序列问题，非常简单的O(26 * n) DP
106+
记录当前位置选与不选，产生的贡献
107+
```c++
108+
class Solution {
109+
public:
110+
int longestIdealString(string s, int k) {
111+
vector <int> pre(26), f(26);
112+
for (int i = 0; i < s.size(); i++){
113+
for (char c = 'a'; c <= 'z'; c++){
114+
if(abs(s[i] - c) <= k){
115+
f[s[i] - 'a'] = max(f[s[i] - 'a'], pre[c - 'a'] + 1);
116+
}
117+
}
118+
pre = f;
119+
}
120+
return *max_element(begin(f), end(f));
121+
}
122+
};
123+
```

0 commit comments

Comments
 (0)