哈希
1. 两数之和
49. 字母异位词分组
std::map可以接受vector作为key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<vector<int>, vector<string>> m;
vector<vector<string>> ans;
for (string s : strs) {
vector<int> v(26);
for (char c : s) {
v[c - 'a']++;
}
m[v].push_back(s);
}
for (auto& [_, v] : m) {
ans.push_back(v);
}
return ans;
}
|
deepseek表示：
在C++中，std::map的operator[]具有自动初始化的特性。当使用m[v]访问一个不存在的键v时，map会自动插入一个新键值对，其中：
键 为v（即当前的字符计数向量）。
值 为该类型的默认构造对象（对于vector<string>，默认构造一个空向量）
因此，m[v].push_back(s)的含义是：
若v不存在于map中，先插入一个键值对{v, vector<string>{}}，得到空vector。然后将字符串s添加到此向量中。 这种机制避免了手动初始化的繁琐，使得代码简洁高效。最终，所有相同字符构成的字符串会被自动归入同一分组。
128. 最长连续序列
遍历集合时要遍历哈希集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
int ans = 0;
for(int k:nums) s.insert(k);
for(int k:s){
if(s.contains(k-1)) continue;
int cur = k;
while(s.contains(cur++));
ans = max(ans,cur-k-1);
}
return ans;
}
};
|
双指针
283. 移动0
[[283.移动0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for(int quick = 0, slow = 0;quick < n;){
if(nums[quick] == 0&& nums[slow] == 0){
quick++;
}else if(nums[quick]!=0&&nums[slow]==0){
//swap
int t = nums[quick];
nums[quick] = nums[slow];
nums[slow] = t;
quick++;
slow++;
}else if(nums[slow]!=0){
quick++;
slow++;
}
}
return ;
}
};
|
3.19瞎写居然通过了
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
|
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int quick=0,slow=0;
int n = nums.size();
while(slow<n&&nums[slow]!=0)slow++;
//现在nums[slow]是0
quick=slow+1;
while(quick<n&&nums[quick]==0){
quick++;
}
if(quick>=n)return;
//现在nums[quick]是1
while(quick<n){
//swap
swap(nums[quick],nums[slow]);
while(slow<n&&nums[slow]!=0)slow++;
//现在nums[slow]是0
quick=slow+1;
while(quick<n&&nums[quick]==0){
quick++;
}
// quick++;
// slow++;
}
return;
//0 1 0 3 12
//1 0 0 3 12
// 1 2 0 0 3 0
}
};
|
11. 盛最多水的容器
双指针，两边向中间缩小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l <= r) {
if (height[l] > height[r]) {
ans = max(ans, (r - l) * height[r]);
r--;
} else {
ans = max(ans, (r - l) * height[l]);
l++;
}
}
return ans;
}
};
|
15. 三数之和
排序
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
|
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
if (n < 3)
return ans;
ranges::sort(nums);
if (nums[0] > 0)
return ans;
for (int i = 0; i < n; i++) {
if (i - 1 >= 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1, r = n - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] == 0) {
ans.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1])
l++;
while (l < r && nums[r] == nums[r - 1])
r--;
l++;
r--;
} else if (nums[i] + nums[l] + nums[r] > 0) {
r--;
} else {
l++;
}
}
}
return ans;
}
};
|
42. 接雨水
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int l = 0, r = n - 1, premax = 0, sufmax = 0;
int ans = 0;
while (l < r) {
premax = max(premax, height[l]);
sufmax = max(sufmax, height[r]);
if (premax < sufmax) {
ans += (premax - height[l]);
l++;
} else {
ans += (sufmax - height[r]);
r--;
}
}
return ans;
}
};
|
滑动窗口
3. 无重复字符的最长子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> has(129);
int n = s.size();
int ans = 0;
for(int l = 0, r = 0;r<s.length();){
while(has[s[r]]>=1){
has[s[l]]--;
l++;
}
ans = max(ans,r-l+1);
has[s[r]]++;
r++;
}
return ans;
}
};
|
438. 找到字符串中所有字母异位词
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
|
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = p.size();
vector<int>ans;
vector<int>vp(26),vs(26);
for(char c:p){
vp[c-'a']++;
}
if(s.size()<n) return ans;
for(int i = 0;i<n;i++){
vs[s[i]-'a']++;
}
for(int l=0,r=n;r<=s.size();){
if(match(vp,vs)) ans.push_back(l);
if(s.size()==r) break;
vs[s[l]-'a']--;
vs[s[r]-'a']++;
l++,r++;
}
return ans;
}
int match(vector<int> &a,vector<int> &b){
for(int i = 0 ;i<26;i++){
if(a[i]!=b[i]) return false;
}
return true;
}
};
|
子串
560.和为 K 的子数组
前缀和组成的哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size(),ans = 0,s=0;
unordered_map<int,int> m;
m[0] = 1;
for(int i=0;i<n;i++){
s+=nums[i];
if(m[s-k]>0) ans += m[s-k];
m[s]++;
}
return ans;
}
};
|
239. 滑动窗口最大值
单调栈
栈里面是index
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
|
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
//1 3 -1 -3 5 3 6 7
//q = [1]
//1<=3 所以1出队,
//q = [3]
//-1入队
//q = [3 -1]
//q = [3 -1 -3]
//q=[5]
//q=[5 3]
//q=[6]
vector<int> ans;
deque<int> q;
for(int i = 0; i < n; i++){
while(q.empty()==false&&nums[q.back()]<nums[i])q.pop_back();
q.push_back(i);
if(i-k>=q.front()) q.pop_front();
if(i>=k-1) ans.push_back(nums[q.front()]);
}
return ans;
}
};
|
76. 最小覆盖子串
滑动窗口
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
|
class Solution {
public:
bool match(vector<int>& vs,vector<int>& vt){
for(int i = 0;i<128;i++){
if(vs[i]<vt[i])return false;
}
return true;
}
string minWindow(string s, string t) {
int ns = s.length(),nt = t.length();
vector<int> vs(128),vt(128);
int ans_left = -1,ans_right = ns;
for(char c:t){
vt[c]++;
}
if(ns<nt) return "";
for(int l=0,r = 0;r<ns;r++){
vs[s[r]]++;
while(match(vs,vt)){
if(r-l<ans_right-ans_left){
ans_left=l;
ans_right=r;
}
vs[s[l]]--;
l++;
}
}
return ans_left<0?"":s.substr(ans_left,ans_right-ans_left+1);
}
};
|
串，即可双指针。而序列则需要考虑dp
这题需要注意，substr(start,count)的定义，以及每次记录ans时超内存的问题。
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
|
class Solution {
public:
bool isans(vector<int>& vs, vector<int>& vt) {
for (int i = 'A' - 'A'; i <= 'Z' - 'A'; i++) {
if (vs[i] < vt[i]) {
// printf(" false vs[i]=%d vt[i]=%d\n",vs[i],vt[i]);
return false;
}
}
for (int i = 'a' - 'A'; i <= 'z' - 'A'; i++) {
if (vs[i] < vt[i]) {
// printf(" false vs[i]=%d vt[i]=%d\n",vs[i],vt[i]);
return false;
}
} // printf("true\n");
return true;
}
string minWindow(string s, string t) {
int l = 0, r = 0, n_s = s.size(), n_t = t.size();
int ans_left = -1, ans_right = n_s;
if (n_s < n_t)
return "";
string ans;
vector<int> vs(128), vt(128);
for (char tt : t) {
vt[tt - 'A']++;
}
while (r < n_s) {
vs[s[r] - 'A']++;
// printf("s[%d]=%d ",r,s[r]-'A');
r++;
while (isans(vs, vt)) {
// printf(" l=%d r=%d ans.size=%d\n",l,r,ans.size());
if (r - l < ans_right - ans_left) { //r会向后读一个，正好前闭后开
// ans = s.substr(l, r - l);注意不能这么写会超内存
ans_left = l; // 记录此时的左右端点
ans_right = r;
// cout << "ans:" << ans<<endl;
}
vs[s[l] - 'A']--;
l++;
// printf("l++ l=%d r=%d\n",l,r);
}
}
return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left);
}
};
|
能否把while内的判断做成O1？
可以，增加一个less记录多少不满足的字母
普通数组
53. 最大子数组和
累加一旦遇到负数，放弃
56. 合并区间
按照左端点排序,std::sort默认就是这样
189. 轮转数组
技巧：反转数组
238. 除自身以外数组的乘积
前后缀，空间优化（只用后缀
41. 缺失的第n个正数
[[41.缺失的第n个正整数]]
注意：
[1,1] 相同数字不交换
[-2147483648]小心减法越界
矩阵
73. 矩阵置零
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
|
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int flag_i_i = 0; // 标记0行是否置零
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && matrix[0][j] == 0) {
flag_i_i = 1;
continue;
}
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// for(int i = m-1;i>=1;i--){// 两头遍历都可以
for (int i = 1; i < m; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; j++)
matrix[i][j] = 0;
}
}
// for(int j = n-1;j>=0;j--){
for (int j = 0; j < n; j++) { // 两头遍历都可以
if (matrix[0][j] == 0) {
for (int i = 1; i < m; i++)
matrix[i][j] = 0;
}
}
if (flag_i_i == 1) {
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
}
};
|
54. 螺旋矩阵
小心，注意边界
48. 旋转图像
[[48. 旋转图像]]
找了半天问题，发现把i写成j了
方法二：对角线翻转+水平翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
void rotate(vector<vector<int>>& m) {
int n = m.size();
for(int i = 0 ;i<n;i++){
for(int j = i ;j<n;j++){
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n/2;j++){
int tmp = m[i][j];
m[i][j] = m[i][n-j-1];
m[i][n-j-1] = tmp;
}
}
}
};
|
240. 寻找二维矩阵 ii
从右上角开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n-1;
while(i>=0&&i<m&&j>=0&&j<n){
int t = matrix[i][j];
if(t==target) return true;
else if(t>target){
j--;
}else i++;
}
return false;
}
};
|
链表
相交链表
反转链表
回文链表
环形链表
142. 环形链表ii
快慢指针在环形入口处相遇
合并两个有序链表
两数相加
删除链表的倒数第 N 个结点
二叉树
108. 将有序数组转换为二叉搜索树
没有难度，很简单的解法
98. 验证二叉搜索树
这一题没写出来，过几天再写
114. 二叉树展开为链表
采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。
为此，要按照 6→5→4→3→2→1 的顺序访问节点，也就是按照右子树 - 左子树 - 根的顺序 DFS 这棵树。
DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。
具体来说：
如果当前节点为空，返回。
递归右子树。
递归左子树。
把 root.left 置为空。
头插法，把 root 插在 head 的前面，也就是 root.right=head。
现在 root 是链表的头节点，把 head 更新为 root。
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
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* pre;
void flatten(TreeNode* root) {
if(root==nullptr) return ;
flatten(root->right);
flatten(root->left);
root->left = nullptr;
root->right = pre;
pre = root;
return;
}
}```
## 199. 二叉树的右视图
层序遍历改两行
## 240. 搜索二维矩阵2
从右上角开始搜索
## 1705. 吃苹果的最大数目
掌握priority_queue的构造方法
```c
typedef pair<int, int> pii;
class Solution {
public:
int eatenApples(vector<int>& apples, vector<int>& days) {
priority_queue<pii, vector<pii>, greater<>> pq;
int ans = 0;
for (int i = 0; i < apples.size() || !pq.empty(); i++) {
while (!pq.empty() && pq.top().first == i) { // 已腐烂
pq.pop();
}
if (i < apples.size() && apples[i] > 0) {
int rottenday = days[i] + i;
int count = apples[i];
pq.push({rottenday, count});
}
if (!pq.empty()) {
pii cur = pq.top();
pq.pop();
cur.second--;
ans++;
if (cur.second > 0) {
pq.push({cur.first, cur.second});
}
}
}
return ans;
}
}
|
437. 路径总和 III
dfs前缀
3218. 切蛋糕的最小总开销
最小生成树的思考方式，但是答案有更简单的解法。
3159. 查询数组中元素的出现位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
vector<int> ans(queries.size());
unordered_map<int,int>map ;
for(int i = 0, cnt=0;i<nums.size();i++){
if(nums[i]==x){
cnt++;
map[cnt] = i;
}
}
for(int i=0;i<queries.size();i++){
int t = queries[i];
if (auto search = map.find(t); search != map.end()){
ans[i] = map[t];
}else{
ans[i] = -1;
}
}
return ans;
}
};
|
学习map的搜索键的方法，这是c++17的语法
124. 二叉树中的最大路径和
还需要再写一遍，加深记忆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int ans_max = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return ans_max;
}
int dfs(TreeNode* root){
if(root==nullptr)return 0;
int l = dfs(root->left);
int r = dfs(root->right);
ans_max = max(ans_max,root->val+l+r);
return max(0,root->val+max(l,r));
}
};
|
不是hot100 1366. 通过投票对团队排名
自定义排序，注意投影函数的使用技巧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
string rankTeams(vector<string>& votes) {
int m = votes[0].length();
vector cnts(26, vector<int>(m));
for (string& vote : votes) {
for (int i = 0; i < m; i++) {
cnts[vote[i] - 'A'][i]--; // 改成负数（相反数），方便比大小
}
}
string ans = votes[0];
ranges::sort(ans, {}, [&](char a) { return make_pair(cnts[a - 'A'], a); });
return ans;
}
};
|
C++20 引入的 投影（Projection） 机制,ranges::sort(range, comparator, projection);
投影函数的作用：将字符 a 映射到一个 std::pair，其中包含 cnts[a - ‘A’]（字符的得分）和 a（字符本身）。然后，ranges::sort 会根据这个 std::pair 进行排序。std::sort 不支持投影机制，因此你需要显式地编写一个接受两个参数的比较函数。
在这一题中，写成这样也是可以的
1
2
3
|
std::sort(ans.begin(), ans.end(), [&](char a, char b) {
return make_pair(cnts[a - 'A'], a) < make_pair(cnts[b - 'A'], b);
});
|
不是hot100 1367. 二叉树中的链表
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:
bool ans = false;
ListNode* h;
bool isSubPath(ListNode* head, TreeNode* root) {
auto dfs = [&](this auto&& dfs, ListNode* node, TreeNode* root) {
if (node == nullptr) {
printf("true");
ans = true;
return true;
}
if (root == nullptr)
return false;
//printf("node=%d,root=%d\n",node->val,root->val);
//bool ans =false;
if (root->val == node->val) {
//printf("%d \n",root->val);
dfs(node->next, root->left);
dfs(node->next, root->right);
}
//if(ans) return true;
if(h==node){
dfs(h, root->left);
dfs(h, root->right);
}
return false;
};
h = head;
dfs(head, root);
return ans;
}
}
|
学习lambda的写法auto dfs = [&](this auto&& dfs, ListNode* node, TreeNode* root)
C++23 借助Deducing this实现lambda递归，最好只能在lc上写，版本太新了。
本来以为 C++23 要整个狠活，把 executor、network 甚至 reflection 都搞全了，结果全军覆没。现在来看 23 更多的还是对 C++20 的补全，甚至增加的特性里不少都是 DR20 的。核心语言方面，deducing this 应该是最有用的特性了，终于不用一个成员函数写 & / const & / && / const && 四个重载了。同时它也允许按值传递对象本身，在一些特殊场景下可以规避生命周期带来的一系列 Bug，典型的情景就是 coroutine lambda
作者：江东某人
链接：https://www.zhihu.com/question/637538344/answer/3348309130
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
图论
207. 课程表
三色标记法，附上我的代码
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
|
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int n = numCourses;
vector<vector<int>> v(n, vector<int>(n));
for (auto& p : prerequisites) {
v[p[0]][p[1]] = 1;
}
vector<int> colors(n, 0);
auto dfs = [&](this auto&& dfs, int x)-> bool {
if (colors[x] == 0) {
colors[x] = 1;
bool dy = 0;
for (int i=0;i<n;i++) {
if(v[x][i]==1){
dy =dy|| dfs(i);
}
}
if (dy == true) {
// 表示有环；
return true;
} else {
// 无环
colors[x] = 2;
return false;
//
}
}else if(colors[x]==1){
return true;
}else if(colors[x]==2){
return false;
}
return false;
};
for(int i=0;i<n;i++){
if(1== dfs(i))return false;
}
return true;
//dfs(0);
}
}
|
208. 实现前缀树
这一题有很多细节要注意
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
|
class Trie {
public:
vector<Trie*> t;
bool canbeEnd = false;
Trie() { t = vector<Trie*>(26, NULL); }
void insert(string word) {
if (search(word) == false) {
Trie* thist = this;
for (char c : word) {
if (thist->t[c - 'a'] == nullptr) {
thist->t[c - 'a'] = new Trie();
}
thist = thist->t[c - 'a'];
}
thist->canbeEnd = true;
}
}
bool search(string word) {
Trie* thist = this;
for (char c : word) {
printf("s:%c\n", c);
thist = thist->t[c - 'a'];
if (thist == nullptr)
return false;
}
if (thist->canbeEnd == true)
return true;
return false;
}
bool startsWith(string prefix) {
Trie* thist = this;
for (char c : prefix) {
thist = thist->t[c - 'a'];
if (thist == nullptr)
return false;
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*
|
回溯
46. 全排列
[[46.全排列]]
子集
17. 电话号码的字母组合
39. 组合总和
[[39. 组合总和]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int n = candidates.size();
vector<vector<int>> ans;
vector<int> tmp;
auto dfs = [&](auto&& dfs, int target, int start_idx) {
if (target == 0) {
ans.push_back(tmp);
return;
} else if (target < 0)
return;
for (int i = start_idx; i < n; i++) {
int x = candidates[i];
tmp.push_back(x);
dfs(dfs, target - x, i);
tmp.pop_back();
}
};
dfs(dfs, target, 0);
return ans;
}
};
|
131. 分割回文串
最难的一题，回溯回溯什么？是最关键的
n皇后
二分查找
栈
有效的括号
394. 字符串解码
使用dfs函数调用模拟栈，不要小看这一题
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
|
class Solution {
public:
string decodeString(string s) {
int i = 0;
return dfs(s, i);
}
private:
string dfs(string& s, int& i) {
string res;
int multi = 0;
while (i < s.size()) {
if (isdigit(s[i])) {
multi = multi * 10 + (s[i] - '0');
i++;
} else if (s[i] == '[') {
i++; // 跳过'['
string tmp = dfs(s, i);
for (int j = 0; j < multi; j++) {
res += tmp;
}
multi = 0;
} else if (s[i] == ']') {
i++; // 跳过']'
return res;
} else {
res+=s[i];
i++;
}
}
return res;
}
};
|
堆
215.数组中的第K个最大的元素
这是一个快速排序的过程，但是只需要排一半
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
|
class Solution {
public:
int qs(vector<int>& nums, int left, int right, int k) {
// 9 8 7 6 5 4 3 2 1
if (left > right)
return -100;
int l = left, r = right;
int pivot = nums[left];
while (l < r) {
while (l < r && nums[r] > pivot) r--;
if (l < r) nums[l++] = nums[r];
while (l < r && nums[l] < pivot) l++;
if (l < r) nums[r--] = nums[l];
}
nums[l] = pivot;
if (l == k)
return nums[k];
if (k > l)
return qs(nums, l + 1, right, k);
else
return qs(nums, left, l - 1, k);
}
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return qs(nums, 0, n - 1, n-k);
}
// int findKthLargest(vector<int>& nums, int k) {
// //if(nums.size()==1) return nums[0];
// vector<int> big,small,equal;
// int pivot = nums[0];
// for(int num:nums){
// if(num>pivot) big.push_back(num);
// else if(num<pivot) small.push_back(num);
// else equal.push_back(num);
// }
// //1 2 3 ||4|| 5 6 7 8,k=3
// if(k<=big.size()) return findKthLargest(big,k);
// //1 2 3 ||4|| 5 6 7 8,k=8
// else if(nums.size()-k<small.size()) {
// //assert(small.size()>=nums.size()-k);
// return findKthLargest(small,k-big.size()-equal.size());
// }else{
// return pivot;
// }
// }
};
|
347.前K个高频元素
295.数据流的中位数
第一次自己写出来了
两个堆，保证中位数是两个堆的top()
贪心算法
121.买卖股票的最佳时机
55.跳跃游戏
45.跳跃游戏2
763.划分字母区间
建一座桥到对岸
动态规划
300. 最长递增子序列
两个for
注意最后是ranges::max
152. 乘积最大的子数组
fmax,fmin两个数组，一次遍历比较max({fmax[i-1]*x,fmin[i-1]*x,x})
416. 分割等和子集
注意构造一个0，1的vector，思路类似于找零钱
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
|
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int target = 0;
for(int num:nums)target+=num;
if(target%2==1)return false;
target /= 2;
vector f(n+1,vector<int>(target+1));
f[0][0]=1;
for(int i = 1;i<=n;i++){
int x = nums[i-1];
for(int j = 0;j<=target;j++){
f[i][j] = f[i-1][j];
if(j>=x){
f[i][j] = f[i-1][j-x]||f[i-1][j];
//printf("%d %d %d\n",i,j,f[i][j]);
}
}
}
return f[n][target];
}
};
|
32. 最长有效括号
这题太难了，不看答案无法解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if(n==0)return 0;
vector<int> f(n,0);
for(int i=1;i<n;i++){
if(s[i]==')'){
if(s[i-1]=='(') f[i]=(i>=2?f[i-2]:0)+2;
else if(i-f[i-1]-1>=0&&s[i-f[i-1]-1]=='(')
f[i] = f[i-1] + ((i-f[i-1]-2>=0)?f[i-f[i-1]-2]:0) +2;
}
}
return ranges::max(f);
}
};
|
62. 不同路径
dp同时也是个组合问题
5. 最长回文子串
要学会中心扩散法，二维dp的复杂度太高了
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:
string longestPalindrome(string s) {
int n = s.length();
if(n<=1)return s;
int maxlen = 1;
int maxl = 0, maxr = 0;
for (int i = 0; i < n; i++) {
int l = i - 1, r = i + 1;
int len = 1;
while (l >= 0 && s[l] == s[i]) {
len++;
l--;
}
while (r < n && s[r] == s[i]) {
len++;
r++;
}
while (l >= 0 && r < n && s[l] == s[r]) {
len += 2;
l--;
r++;
}
if (len > maxlen) {
maxlen = len;
maxl = l+1;//注意为什么要+1,因为会往左多走一个
maxr = r-1;
}
}
return s.substr(maxl + 1, maxlen);
}
};
|
72. 编辑距离
太巧妙了这一题，认真回忆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length(),n=word2.length();
if(m*n==0)return m+n;
vector f(m+1,vector(n+1,0));
for(int i=0;i<=m;i++){
f[i][0]=i;
}
for(int j=0;j<=n;j++) f[0][j]=j;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(word1[i]==word2[j]) f[i+1][j+1]=f[i][j];
else f[i+1][j+1] = min({f[i+1][j],f[i][j+1],f[i][j]})+1;
}
}
return f[m][n];
}
};
|
技巧
169. 多数元素
摩尔投票的方法有点意思
投出多数元素只需要其他少数元素内耗就行了
75. 颜色分类
打了好久才过，还没有完全理解
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
|
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int i = 0, j0 = 0, j2 = n - 1;
for (; i <= j2;) {
if (nums[i] == 2) {
swap(nums[i], nums[j2]);
j2--;
} else if (nums[i] == 0) {
swap(nums[i], nums[j0]);
j0++;
i++;
} else i++;
}
return;
}
}```
## 31. 下一个排列
从后向前读，降序不需要考虑，（即最新读到的数字最大，已经是最大的字典序了），当读到非降序，即最新读到的数字比已读的最大数字小，此时只需要考虑已经读到的数字了。找到比这个数稍微大一点的数字。
```cpp
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
vector<int> readnum;
int mx = -1;
for (int i = n - 1; i >= 0; i--) {
int t = nums[i];
mx = max(t, mx);
readnum.push_back(t);
if (t < mx) {
ranges::sort(readnum);
auto it = upper_bound(readnum.begin(), readnum.end(), t);
//printf("nums[%d]=%d\n", i, *it);
nums[i] = *it;
readnum.erase(it);
int j = i + 1;
for (int tt : readnum) {
nums[j] = tt;
//printf("nums[%d]=%d\n", j, tt);
j++;
}
return;
// 可以终止了，因为一定能组成更大的字典序
}
}
// 全部为降序，全排列里最后一个
ranges::sort(nums);
printf("hello");
return;
}
};
|
287. 寻找重复数
这一题和142.环形链表2思路居然是一样的，快慢指针在环形入口处相遇