哈希

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思路居然是一样的,快慢指针在环形入口处相遇