LC刷题笔记
2024-01-05 16:19:44 # 技术 # CS基础 #算法和数据结构

数组

215. 数组中的第 K 个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 小顶堆
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < k; ++i) {
            pq.push(nums[i]);
        }

        for(int i = k; i < nums.size(); ++i) {
            if(nums[i] > pq.top()) {
                pq.pop();
                pq.push(nums[i]);
            }
        }

        return pq.top();
    }
};

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 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
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        for(int i = 0; i < nums.size(); ++i) {
            counts[nums[i]]++;
        }

        auto comp = [](pair<int,int> it1, pair<int,int> it2) {
            return it1.second < it2.second;
        };
        priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(comp)> pq(comp);

        for(const auto& it : counts) {
            pq.push({it.first, it.second});
        }

        vector<int> ans;
        while(k) {
            ans.push_back(pq.top().first);
            pq.pop();
            --k;
        }
        return ans;
    }
};

搜索

深度优先搜索

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

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
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                ans = max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }

    int dfs(vector<vector<int>>& grid, int x, int y) {
        if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 0) {
            return 0;
        }
        int num = 1;
        grid[x][y] = 0;
        
        num += dfs(grid, x, y - 1);
        num += dfs(grid, x, y + 1);
        num += dfs(grid, x - 1, y);
        num += dfs(grid, x + 1, y);
        return num;
    }
};

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

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:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int ans = 0;
        int n = isConnected.size();
        vector<bool> visited(n, false);
        for(int i = 0; i < n; ++i) {
            if(!visited[i]) {
                ++ans;
                dfs(isConnected, visited, i);
            }
        }
        return ans;
    }
    void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int p) {
        visited[p] = true;
        for(int i = 0; i < isConnected.size(); ++i) {
            if(isConnected[p][i] && !visited[i]) {
                dfs(isConnected, visited, i);
            }
        }
    }
};

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
// 并查集解法
class Solution {
public:
    vector<int> ds;
    int count;
    void init(int n) {
        for(int i = 0; i < n; ++i) {
            ds.push_back(i);
        }
        count = n;
    }

    int findParent(int x) {
        if(ds[x] == x) {
            return x;
        }
        return findParent(ds[x]);
    }

    void connect(int x, int y) {
        int px = findParent(x);
        int py = findParent(y);
        if(px != py) {
            ds[py] = px;
            --count;
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int ans = 0;
        int n = isConnected.size();
        init(n);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(isConnected[i][j]) {
                    connect(i, j);
                }
            }
        }

        return count;
    }
};

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

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:
    vector<int> directions{-1, 0, 1, 0, -1};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int rows = heights.size();
        int cols = heights[0].size();
        vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
        for(int i = 0; i < cols; ++i) {
            dfs(heights, pacific, 0, i);
            dfs(heights, atlantic, rows-1, i);
        }

        for(int i = 0; i < rows; ++i) {
            dfs(heights, pacific, i, 0);
            dfs(heights, atlantic, i, cols-1);
        }

        vector<vector<int>> ans;
        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < cols; ++j) {
                if(pacific[i][j] && atlantic[i][j]) {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& ocean, int x, int y) {
        if(ocean[x][y]) return;
        ocean[x][y] = true;
        for(int i = 0; i < 4; ++i) {
            int nx = x + directions[i], ny = y + directions[i+1];
            if(nx >=0 && nx < heights.size() && ny >=0 && ny < heights[0].size() && 
               heights[x][y] <= heights[nx][ny]) {
                dfs(heights, ocean, nx, ny);
            }
        }
    }
};

回溯法

46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tample;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        backtracking(nums, visited);
        return ans;
    }

    void backtracking(vector<int>& nums, vector<bool>& visited) {
        if(tample.size() == nums.size()) {
            ans.push_back(tample);
            return ;
        }
        for(int i = 0; i < nums.size(); ++i) {
            if(!visited[i]) {
                visited[i] = true;
                tample.push_back(nums[i]);
                backtracking(nums, visited);
                tample.pop_back();
                visited[i] = false;
            }
        }
    }
};

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tample;
    vector<vector<int>> combine(int n, int k) {
        vector<bool> visited(n + 1, false);
        backtracking(visited, k, 0);
        return ans;
    }

    void backtracking(vector<bool>& visited, const int& k, int p) {
        if(tample.size() == k) {
            ans.push_back(tample);
            return ;
        }

        for(int i = p + 1; i < visited.size(); ++i) {
            visited[i] = true;
            tample.push_back(i);
            backtracking(visited, k, i);
            tample.pop_back();
            visited[i] = false;
        }
    } 
};

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

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
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        bool find = false;
        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < cols; ++j) {
                backtracking(board, visited, find, word, i, j, 0);
                if(find) return find;
            }
        }
        return find;
    }

    void backtracking(vector<vector<char>>& board, vector<vector<bool>>& visited, bool& find,  const string& word, int x, int y, int pos) {
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
            return ;
        }

        if(visited[x][y] || find || board[x][y] != word[pos]) {
            return ;
        }

        if(pos == word.size() - 1) {
            find = true;
            return ;
        }

        visited[x][y] = true;
        backtracking(board, visited, find, word, x + 1, y, pos + 1);
        backtracking(board, visited, find, word, x - 1, y, pos + 1);
        backtracking(board, visited, find, word, x, y - 1, pos + 1);
        backtracking(board, visited, find, word, x, y + 1, pos + 1);
        visited[x][y] = false;
    }
};

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

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
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        if(n == 0) return ans;
        vector<string> board(n, string(n, '.'));
        vector<bool> column(n, false), ldiag(2 * n - 1, false), rdiag(2 * n - 1, false);
        backtracking(ans, board, column, ldiag, rdiag, 0, n);
        return ans;
    }

    void backtracking(vector<vector<string>>& ans, vector<string>& board,
                      vector<bool>& column, vector<bool>& ldiag, vector<bool>& rdiag, int row, int n) {
        if(row == n) {
            ans.push_back(board);
            return ;
        }

        for(int i = 0; i < n; ++i) {
            if(column[i] || rdiag[row + i] || ldiag[n - i - 1 + row]) {
                continue;
            }

            board[row][i] = 'Q';
            column[i] = rdiag[row + i] = ldiag[n - i - 1 + row]  = true;
            backtracking(ans, board, column, ldiag, rdiag, row + 1, n);
            board[row][i] = '.';
            column[i] = rdiag[row + i] = ldiag[n - i - 1 + row]  = false;
        }
    }
};

广度优先搜索

934. 最短的桥

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。

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
class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        // 找到第一座岛屿，将其置为2
        bool find = false;
        queue<pair<int, int>> points;
        for(int i = 0; i < grid.size(); ++i) {
            if(find) break;
            for(int j = 0; j < grid[0].size(); ++j) {
                if(grid[i][j] == 1) {
                    dfs(grid, points, i, j);
                    find = true;
                    break;
                }
            }
        }

        int ans = 0;
        vector<int> directions{-1, 0, 1, 0, -1};
        while(!points.empty()) {
            ++ans;
            int size = points.size();
            while(size--) {
                auto ponit = points.front();
                points.pop();
                // grid[ponit.first][ponit.second] = 2;
                for(int i = 0 ; i < 4; ++i) {
                    int x = ponit.first + directions[i];
                    int y = ponit.second + directions[i+1];
                    if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) {
                        continue;
                    }
                    if(grid[x][y] == 2) {
                        continue;
                    } else if(grid[x][y] == 1) {
                        return ans;
                    } else {
                        points.push({x, y});
                        grid[x][y] = 2;
                    }
                }
            }
        }
        return 0;
    }

    // 将第一座岛屿的1全部转置为2，并保存邻接的第一层节点
    void dfs(vector<vector<int>>& grid, queue<pair<int,int>>& points, int x, int y) {
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 2) {
            return ;
        }

        if(grid[x][y] == 0) {
            points.push({x, y});
            grid[x][y] = 2;
            return ;
        }

        grid[x][y] = 2;
        dfs(grid, points, x + 1, y);
        dfs(grid, points, x - 1, y);
        dfs(grid, points, x, y + 1);
        dfs(grid, points, x, y - 1);
    }
};

动态规划

基本动态规划：一维

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;

        int n1 = 1, n2 = 2;
        for(int i = 3; i <= n; ++i) {
            int n = n1 + n2;
            n1 = n2;
            n2 = n;
        }
        return n2;
    }
};

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); ++i) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp.back();
    }
};

413. 等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

  • 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
    给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        vector<int> dp(nums.size(), 0); // dp[i] 表示以index i为结尾的等差子数组的个数
        for(int i = 2; i < nums.size(); ++i) {
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
            }
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};

基本动态规划：二维

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：每次只能向下或者向右移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if(i == 0) {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

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
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> dp(m, vector<int>(n, m + n));
        // 从左上到右下，保证每次到达当前位置的左边和上边该是0的都变为0
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(mat[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if(i > 0) 
                        dp[i][j] = min(dp[i][j], dp[i-1][j] + 1); // 上边
                    if(j > 0) 
                        dp[i][j] = min(dp[i][j], dp[i][j-1] + 1); // 左边
                }
            }
        }
        
        // 完成从左上到右下后，所有该是0的都变为0了。
        // 开始从右下到左上 
        for(int i = m-1; i >= 0; --i) {
            for(int j = n-1; j >= 0; --j) {
                if(mat[i][j] != 0) {
                    if(i < m - 1) 
                        dp[i][j] = min(dp[i][j], dp[i+1][j] + 1); // 下边
                    if(j < n - 1) 
                        dp[i][j] = min(dp[i][j], dp[i][j+1] + 1); // 右边
                }
            }
        }
        return dp;
    }
};

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int max_side = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(matrix[i][j] == '1') {
                    if(i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                    }
                    max_side = max(max_side, dp[i][j]);
                }
            }
        }
        return max_side * max_side;
    }
};

分割类型

279. 完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, 0);
        for(int i = 1; i <= n; ++i) {
            dp[i] = i;
            for(int j = 1; j * j <= i; ++j) {
                dp[i] = min(dp[i], 1 + dp[i - j * j]);
            }
        }
        return dp[n];
    }
};

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

1
2
3
4
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)
    注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
    给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
    题目数据保证答案肯定是一个 32 位 的整数。

提示：

  • 1 <= s.length <= 100
  • s 只包含数字，并且可能包含前导零。
    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
    class Solution {
    public:
        int numDecodings(string s) {
            if(s.size() == 0) return 0;

            int prev = s[0] - '0';
            if(prev == 0) return 0;
            if(s.size() == 1) return 1;

            vector<int> dp(s.size(), 1);
            int next = s[1] - '0';
            if(next == 0) {
                if(prev > 2) {
                    dp[1] = 0;
                } else {
                    dp[1] = 1;
                }
            } else {
                if(prev * 10 + next > 26) {
                    dp[1] = 1;
                } else {
                    dp[1] = 2;
                }
            }

            prev = next;
            for(int i = 2; i < s.size(); ++i) {
                next = s[i] - '0';
                if(prev == 0 && next == 0) {
                    return 0;
                }
                
                if(next == 0) {
                    if(prev > 2) {
                        dp[i] = 0;
                    } else {
                        dp[i] = dp[i-2];
                    }
                } else if(prev == 0) {
                    dp[i] = dp[i-1];
                } else {
                    int num = prev * 10 + next;
                    if(num > 26) {
                        dp[i] = dp[i-1];
                    } else {
                        dp[i] = dp[i-2] + dp[i-1];
                    }
                }
                prev = next;
            }
            return dp.back();
        }
    };

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n, false);
        for(int i = 0; i < n; ++i) {
            for(auto const& word : wordDict) {
                if(i + 1 >= word.size() && s.substr(i - word.size() + 1, word.size()) == word) {
                    if(i + 1 == word.size()) {
                        dp[i] = true;
                    } else {
                        dp[i] = dp[i] || dp[i - word.size()];
                    }
                }
            }
        }
        return dp.back();
    }
};

子序列问题

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 1;
        for(int i = 1; i < nums.size(); ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
    两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int longestCommonSubsequence(string text1, string text2) {
            int m = text1.size(), n = text2.size();
            vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
            int ans = 0;
            for(int i = 1; i <= m; ++i) {
                for(int j = 1; j <= n; ++j) {
                    if(text1[i-1] == text2[j-1]) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
            return dp[m][n];
        }
    };

背包问题

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

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 sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false;
        int target = sum / 2, n = nums.size();
        // dp[i][j] 表示能否从前i个元素中挑出和为j的数量
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        for(int i = 0; i <= n; ++i) {
            dp[i][0] = true;
        }

        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= target; ++j) {
                if(j >= nums[i-1]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
                    
            }
        }
        return dp[n][target];
    }
};

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

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
class Solution {
public:
    pair<int, int> count(const string& s) {
        int count0 = 0, count1 = 0;
        for(const auto& c : s) {
            if(c == '1') {
                ++count1;
            } else {
                ++count0;
            }
        }
        return {count0,count1};
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(const auto& str : strs) {
            auto [count0, count1] = count(str);
            for(int i = m; i >= count0; --i) {
                for(int j = n; j >= count1; --j) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i-count0][j-count1]);
                }
            }
        }
        return dp[m][n];
    }
};

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i) {
            for(const auto& coin : coins) {
                if(i >= coin) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

72. 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
    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
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.size(), n = word2.size();
            vector<vector<int>> dp(m + 1, vector<int>(n+1, 0));
            for(int i = 1; i <= m; ++i) dp[i][0] = dp[i-1][0] + 1;
            for(int j = 1; j <= n; ++j) dp[0][j] = dp[0][j-1] + 1;

            for(int i = 1; i <= m; ++i) {
                for(int j = 1; j <= n; ++j) {
                    if(word1[i-1] == word2[j-1]) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    }
                }
            }
            return dp[m][n];
        }
        // int minDistance(string word1, string word2) {
        //     int m = word1.length(), n = word2.length();
        //     vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        //     for(int i = 0; i <= m; ++i) {
        //         for(int j = 0; j <= n; ++j) {
        //             if(i == 0) {
        //                 dp[i][j] == j;
        //             } else if(j == 0) {
        //                 dp[i][j] == i;
        //             } else {
        //                 if(word1[i-1] == word2[j-1]) {
        //                     dp[i][j] = dp[i-1][j-1];
        //                 } else {
        //                     dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
        //                 }
        //             }
        //         }
        //     }
        //     return dp[m][n];
        // }
    };

    650. 只有两个键的键盘

    最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
  • Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
  • Paste（粘贴）：粘贴 上一次 复制的字符。
    给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int minSteps(int n) {
            vector<int> dp(n + 1);
            for(int i = 2; i <= n; ++i) {
                dp[i] = i;
                for(int j = 2; j <= sqrt(i); ++j) {
                    if(i % j == 0) {
                        // 如果j能被i整除，相当于
                        // 1. 先从1扩展到j，单位为1；
                        // 2. 再从j扩展到i，单位为i/j;
                        dp[i] = dp[j] + dp[i/j];
                        break;
                    }
                }
            }
            return dp[n];
        }
    };

    10. 正则表达式匹配

    给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 . 和 * 的正则表达式匹配。
  • . 匹配任意单个字符;
  • * 匹配零个或多个前面的那一个元素;
    所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。
    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
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.size(), n = p.size();
            vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
            dp[0][0] = true;
            for(int j = 1; j <= n; ++j) {
                if(p[j-1] == '*') {
                    dp[0][j] = dp[0][j-2];
                }
            }
            for(int i = 1; i <= m; ++i) {
                for(int j = 1; j <= n; ++j) {
                    if(p[j-1] == '.' || p[j-1] == s[i-1]) {
                        dp[i][j] = dp[i-1][j-1];
                    } else if(p[j-1] == '*') {
                        // p[j-1]为*，且p[j-2]和s[i-1]匹配
                        if(p[j-2] == s[i-1] || p[j-2] == '.') {
                            dp[i][j] = dp[i][j-2] || // p[j-2] 匹配0次
                                       dp[i-1][j-2] || // p[j-2] 匹配1次
                                       dp[i-1][j] ; // p[j-2] 匹配多次
                        } else {
                            // * 匹配0次
                            dp[i][j] = dp[i][j-2];
                        }
                    }
                }
            }
            return dp[m][n];
        }
    };

股票交易

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int buy = prices[0];
        for(int i = 1; i < prices.size(); ++i) {
            ans = max(ans, prices[i] - buy); // 不断比较最大收益
            buy = min(buy, prices[i]); // 不断更新买入时机
        }
        return ans;
    }
};

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
注：没太搞懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<int> buy(k + 1, INT_MIN); // buy[j]表示第j次买入时的最大收益
        vector<int> sell(k + 1, 0); // buy[j]表示第j次出售时的最大收益
        for(int i = 0; i < prices.size(); ++i) {
            for(int j = 1; j <= k; ++j) {
                buy[j] = max(buy[j], sell[j-1] - prices[i]);
                sell[j] = max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k];
    }
};

309. 最佳买卖股票时机含冷冻期

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(3, 0));
        dp[0][0] = -prices[0]; // 当前持有股票
        dp[0][1] = 0; // 刚卖出股票，处于冷冻期
        dp[0][2] = 0; // 不持有股票，也不处于冷冻期，可以买股票
        for(int i = 1; i < prices.size(); ++i) {
            // 继续持有原来的股票，或买入新股票
            dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);
            // 卖出股票
            dp[i][1] = dp[i-1][0] + prices[i];
            // 不持有股票，也不处于冷冻期
            dp[i][2] = max(dp[i-1][1], dp[i-1][2]);
        }
        return max(dp.back()[1], dp.back()[2]);
    }
};

分治

241. 为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

  • expression 由数字和算符 '+'、'-' 和 '*' 组成。
    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> diffWaysToCompute(string expression) {
            vector<int> ways;
            for(int i = 0; i < expression.size(); ++i) {
                char c = expression[i];
                if(c == '+' || c == '-' || c == '*') {
                    vector<int> lefts = diffWaysToCompute(expression.substr(0, i));
                    vector<int> rights = diffWaysToCompute(expression.substr(i + 1));
                    for(const auto& left : lefts) {
                        for(const auto& right : rights) {
                            if(c == '+') {
                                ways.emplace_back(std::move(left + right));
                            } else if(c == '-') {
                                ways.emplace_back(std::move(left - right));
                            } else {
                                ways.emplace_back(std::move(left * right));
                            }
                        }
                    }
                }
            }
            if(ways.empty()) {
                ways.emplace_back(stoi(expression));
            }
            return ways;
        }
    };

数据结构

数组

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ans;
        // 将出现数应该在的位置设置为相反数
        for(const auto& num : nums) {
            int pos = abs(num) - 1;
            if(nums[pos] > 0) {
                nums[pos] = -nums[pos];
            }
        }
        // 统计仍为正数的位置
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] > 0) {
                ans.emplace_back(std::move(i+1));
            }
        }
        return ans;
    }
};

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

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 rotate(vector<vector<int>>& matrix) {
        // 先转置，后对称交换
        // 转置
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j =i; j < matrix.size(); ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 左右对称交换
        for(int i = 0; i < matrix.size(); ++i) {
            int left = 0, right = matrix.size() - 1;
            while(left < right) {
                swap(matrix[i][left], matrix[i][right]);
                ++left; --right;
            }
        }
    }
};
// 1 2 3  转置  1 4 7      7 4 1
// 4 5 6  =>   2 5 8  =>  8 5 2
// 7 8 9       3 6 9      9 6 3

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size(), n = matrix[0].size();
            int x = 0, y = n - 1;
            while(x < m && y < n && x >= 0 && y >= 0) {
                if(matrix[x][y] == target) {
                    return true;
                } else if(matrix[x][y] < target) {
                    ++x;
                } else if(matrix[x][y] > target) {
                    --y;
                }
            }
            return false;
        }
    };

769. 最多能完成排序的块

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0, cur_max = 0;;
        for(int i = 0; i < arr.size(); ++i) {
            cur_max = max(cur_max, arr[i]);
            if(cur_max == i) {
                ++ans;
            }
        }
        return ans;
    }
};
// 4 0 1 2 3

栈和队列

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    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
    class MyQueue {
    public:
        stack<int> stk1, stk2;
        MyQueue() {

        }
        
        void push(int x) {
            stk1.push(x);
        }
        
        int pop() {
            if(stk2.empty()) {
                while(!stk1.empty()) {
                    int x = stk1.top();
                    stk1.pop();
                    stk2.push(x);
                }
            }
            int ans = stk2.top();
            stk2.pop();
            return ans;
        }
        
        int peek() {
            if(stk2.empty()) {
                while(!stk1.empty()) {
                    int x = stk1.top();
                    stk1.pop();
                    stk2.push(x);
                }
            }
            return stk2.top();
        }
        
        bool empty() {
            return stk1.empty() && stk2.empty();
        }
    };

    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */

    155. 最小栈

    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    实现 MinStack 类:
  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。
    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
    class MinStack {
    public:
        stack<int> stk, min;
        MinStack() {

        }
        
        void push(int val) {
            stk.push(val);
            if(min.empty() || min.top() >= val) {
                min.push(val);
            }
        }
        
        void pop() {
            if(!min.empty() && min.top() == stk.top()) {
                min.pop();
            }
            stk.pop();
        }
        
        int top() {
            return stk.top();
        }
        
        int getMin() {
            return min.top();
        }
    };

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack* obj = new MinStack();
     * obj->push(val);
     * obj->pop();
     * int param_3 = obj->top();
     * int param_4 = obj->getMin();
     */

    20. 有效的括号

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
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:
    bool isValid(string s) {
        stack<int> stk;
        for(const auto& c : s) {
            int v = value(c);
            if(v > 0) {
                stk.push(v);
            } else {
                if(stk.empty() || stk.top() + v != 0) {
                    return false;
                }
                stk.pop();
            }
        }
        if(!stk.empty()) return false;
        return true;
    }

    int value(char c) {
        switch(c) {
            case '(':
                return 1;
            case ')':
                return -1;
            case '[':
                return 2;
            case ']':
                return -2;
            case '{':
                return 3;
            case '}':
                return -3;
        }
        return 0;
    }
};

单调栈

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> dates;
        
        for(int i = 0; i < n; ++i) {
            while(!dates.empty()) {
                int date = dates.top();
                if(temperatures[date] < temperatures[i]) {
                    ans[date] = i - date;
                    dates.pop();
                } else {
                    break;
                }
            }
            dates.push(i);
        }
        return ans;
    }
};

优先队列

23. 合并 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct Comp {
    bool operator()(ListNode* n1, ListNode* n2) {
        return n1->val > n2->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 优先队列默认是大顶堆，这里自定义为小顶堆
        // 小顶堆
        priority_queue<ListNode*, vector<ListNode*>, Comp> que;
        for(auto node : lists) {
            if(node) {
                que.push(node);
            }
        }

        ListNode* head = new ListNode();
        ListNode* p = head;
        while(!que.empty()) {
            p->next = que.top();
            p = p->next;
            que.pop();
            if(p->next) {
                que.push(p->next);
            }
        }
        return head->next;
    }
};

双端队列

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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
class Solution {
public:
    // 优先队列解法
    // vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    //     // 创建优先队列，保存节点的数值和索引，优先根据数值排序，然后再根据索引排序
    //     priority_queue<pair<int, int>> que;
    //     for(int i = 0; i < k; ++i) {
    //         que.push({nums[i], i});
    //     }
    //     vector<int> ans;
    //     ans.push_back(que.top().first);
    //     for(int i = k; i < nums.size(); ++i) {
    //         que.push({nums[i], i});
    //         // 从队首去除优先队列中的无效数据，也即需要移出窗口的值
    //         while(!que.empty() && que.top().second < i - k + 1) {
    //             que.pop();
    //         }
    //         ans.push_back(que.top().first);
    //     }
    //     return ans;
    // }

    // 双端队列解法
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq; // 双端队列存储索引
        vector<int> ans;
        for(int i = 0; i < nums.size(); ++i) {
            if(!dq.empty() &&  dq.front() <= i - k) {
                dq.pop_front(); // 移出超出窗口的数值索引
            }

            while(!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back(); // 将比当前数小的索引都删掉，保证队首是最大数值的索引
            }
            dq.push_back(i);
            if(i >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};

哈希表

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); ++i) {
            if(!mp.empty() && mp.count(target - nums[i]) != 0) {
                return {mp[target-nums[i]], i};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

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
class Solution {
public:
    // int longestConsecutive(vector<int>& nums) {
    //     sort(nums.begin(), nums.end());
    //     int rst = 0;
    //     int cursor = 0;
    //     while(cursor < nums.size()) {
    //         int len = 1;
    //         while(cursor + 1 < nums.size()) {
    //             if(nums[cursor] + 1 == nums[cursor+1]) {
    //                 ++len;
    //                 ++cursor;
    //             } else if(nums[cursor] == nums[cursor+1]) {
    //                 ++cursor;
    //             } else {
    //                 break;
    //             }
                
    //         }
    //         ++cursor;
    //         rst = max(rst, len);
    //     }
    //     return rst;
    // }
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numsSet;
        int rst = 0;
        for(const auto& num : nums) {
            numsSet.insert(num);
        }
        for(const auto& num : numsSet) {
            // previous num which not in set is that we need to test 
            if(numsSet.find(num-1) == numsSet.end()) {
                int len = 0;
                int cursor = num;
                while(numsSet.find(cursor) != numsSet.end()) {
                    ++len;
                    ++cursor;
                }
                rst = max(rst, len);
            }
        }
        return rst;
    }
};

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

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<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ans;
        if(tickets.empty()) {
            return ans;
        }
        unordered_map<string, multiset<string>> mp;
        for(auto ticket : tickets) {
            mp[ticket[0]].insert(ticket[1]);
        }
        stack<string> stk;
        stk.push("JFK");
        while(!stk.empty()) {
            string start = stk.top();
            if(mp[start].empty()) {
                // 到达终点
                ans.push_back(start);
                stk.pop();
            } else {
                stk.push(*mp[start].begin());
                mp[start].erase(mp[start].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

前缀和和积分图

303. 区域和检索 - 数组不可变

给定一个整数数组  nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumArray {
public:
    vector<int> presum;
    NumArray(vector<int>& nums) {
        if(!nums.empty()) {
            presum.push_back(nums[0]);
        }
        for(int i = 1; i < nums.size(); ++i) {
            presum.push_back(presum.back() + nums[i]);
        }
    }
    
    int sumRange(int left, int right) {
        return left > 0 ? presum[right] - presum[left-1] : presum[right];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
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 NumMatrix {
public:
    vector<vector<int>> sum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        sum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1] + sum[row1][col1] - 
               sum[row2+1][col1] - sum[row1][col2+1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int sum = 0;
        int ans = 0;
        for(const auto& num : nums) {
            sum += num;
            if(sum == k) {
                ++ans;
            }
            if(mp.find(sum - k) != mp.end()) {
                ans += mp[sum-k];
            }
            mp[sum]++;
        }
        return ans;
    }
};

并查集

684. 冗余连接树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

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
class UF {
private:
    vector<int> parent;
public:
    UF(int n) : parent(n + 1) {
        for(int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
    }
    int findParent(int x) {
        if(parent[x] == x) {
            return x;
        }
        return findParent(parent[x]);
    }

    bool merge(int x, int y) {
        int px = findParent(x);
        int py = findParent(y);
        if(px == py) return false;
        parent[px] = py;
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UF uf(n);
        vector<int> ans;
        for(const auto& edge : edges) {
            bool flag = uf.merge(edge[0], edge[1]);
            if(!flag) ans = edge;
        }
        return ans;
    }
};

字符串

字符串比较

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()) return false;

        vector<int> count(26, 0);
        for(int i = 0; i < s.size(); ++i) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }

        for(int i = 0; i < 26; ++i) {
            if(count[i] != 0) {
                return false;
            }
        }

        return true;
    }
};

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;

        unordered_map<char, char> mp;
        for(int i = 0; i < s.size(); ++i) {
            if(mp.find(t[i]) == mp.end()) {
                for(const auto& it : mp) {
                    // s[i]已经被其他字符映射过
                    if(it.second == s[i]) {
                        return false;
                    }
                }
                mp[t[i]] = s[i];
            } else if(mp[t[i]] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        for(int i = 0; i < s.size(); ++i) {
            // 单中心扩展搜索
            int left = i, right = i;
            while(left >= 0 && right < s.size() && s[left] == s[right]) {
                ++ans;
                --left; ++right;
            }
            // 双中心扩展搜索
            left = i, right = i + 1;
            while(left >= 0 && right < s.size() && s[left] == s[right]) {
                ++ans;
                --left; ++right;
            }
        }
        return ans;
    }
};

696. 计数二进制子串

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
重复出现（不同位置）的子串也要统计它们出现的次数。

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
// 快速解法
class Solution {
public:
    int countBinarySubstrings(string s) {
        int ans = 0;
        int pre = 0, now = 1; // 分别记录前面和当前连续相同字符的长度
        for(int i = 1; i < s.size(); ++i) {
            if(s[i] == s[i-1]) {
                ++now;
            } else {
                pre = now;
                now = 1;
            }
            if(pre >= now) {
                ++ans;
            }
        }
        return ans;
    }
};

// 普通解法
class Solution {
public:
    int countBinarySubstrings(string s) {
        int ans = 0;
        for(int i = 0; i < s.size() - 1; ++i) {
            if(s[i] - '0' + s[i+1] - '0' == 1) {
                ++ans;
                int left = i - 1, right = i + 2;
                while(left >= 0 && s[left] == s[left+1] && right < s.size() && s[right] == s[right-1]) {
                    ++ans;
                    --left; ++right;
                }
            }
        }
        return ans;
    }
};

字符串理解

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

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
class Solution {
public:
    int calculate(string s) {
        stack<int> nums;
        stack<char> ops;
        int i = 0, n = s.size();
        while(i < n) {
            while(i < n && s[i] == ' ') {
                ++i;
            }
            if(i >= n) break;
            
            if(s[i] >= '0' && s[i] <= '9') {
                string num;
                while(i < n && s[i] >= '0' && s[i] <= '9') {
                    num.append(1, s[i]);
                    ++i;
                }
                nums.push(stoi(num));
            } else {
                while(!ops.empty() && priority(ops.top()) >= priority(s[i])) {
                    char op = ops.top(); ops.pop();
                    int num2 = nums.top(); nums.pop(); 
                    int num1 = nums.top(); nums.pop();
                    nums.push(alu(num1, num2, op));
                }
                ops.push(s[i++]);
            }
        }
        while(!ops.empty()) {
            char op = ops.top(); ops.pop();
            int num2 = nums.top(); nums.pop(); 
            int num1 = nums.top(); nums.pop();
            nums.push(alu(num1, num2, op));
        }
        return nums.top();
    }

    int priority(char c) {
        switch(c) {
            case '+':
            case '-':
                return 1;
            case '/':
            case '*':
                return 2;
        }
        return 0;
    }

    int alu(int num1, int num2, char op) {
        switch(op) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
        }
        return 0;
    }
};

字符串匹配

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

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
class Solution {
public:
	// KMP算法
    // 计算模式串的next数组(获取每个位置的最长前后缀匹配长度)
    void getNext(int* next, string pattern) {
        int j = 0;
        next[j] = 0;
        for(int i = 1; i < pattern.size(); ++i) {
            while(j > 0 && pattern[j] != pattern[i]) {
                j = next[j-1];
            }
            if(pattern[j] == pattern[i]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        int n = needle.size();
        int next[n];
        getNext(next, needle);
        int j = 0;
        for(int i = 0; i < haystack.size(); ++i) {
            while(j > 0 && needle[j] != haystack[i]) {
                j = next[j-1];
            }
            if(needle[j] == haystack[i]) {
                ++j;
            }
            if(j == n) {
                return i + 1 - n;
            }
        }
        return -1;
    }
};

链表

链表的基本操作

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* nhead = new ListNode();
        while(head) {
            ListNode* p = head->next;
            head->next = nhead->next;
            nhead->next = head;
            head = p;
        }
        return nhead->next;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* p = head;
        while(list1 && list2) {
            if(list1->val <= list2->val) {
                p->next = list1;
                list1 = list1->next;
            } else {
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }
        if(list1) p->next = list1;
        if(list2) p->next = list2;
        return head->next;
    }
};

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNode(ListNode* node1, ListNode* node2) {
        if(!node2) return node1;
        if(node2->next) {
            node1->next = swapNode(node2->next, node2->next->next);
        } else {
            node1->next = node2->next;
        }
        node2->next = node1;
        return node2;
    }
    ListNode* swapPairs(ListNode* head) {
        if(!head) return head;
        return swapNode(head, head->next);
    }
};

其他链表技巧

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        // 必须要保证p1和p2能同时移动到空节点
        while(p1 != p2) {
            p1 = p1 ? p1->next : headB;
            p2 = p2 ? p2->next : headA;
        }
        return p1;
    }
};

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) {
            return true;
        }

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        slow->next = reverseList(slow->next);
        slow = slow->next;
        ListNode* p = head;
        while(slow) {
            if(slow->val != p->val) {
                return false;
            }
            slow = slow->next;
            p = p->next;
        }
        return true;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* nhead = new ListNode();
        while(head) {
            ListNode* t = head->next;
            head->next = nhead->next;
            nhead->next = head;
            head = t;
        }
        return nhead->next;
    }
};

树

树的递归

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

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
/**
 * 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:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int ans = 0;
        if(root) que.push(root);
        while(!que.empty()) {
            ++ans;
            int size = que.size();
            while(size--) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            } 
        }
        return ans;
    }
};

// 递归解法
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return depth(root);
    }
    int depth(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int left = 1 + depth(root->left);
        int right = 1 + depth(root->right);
        return left >= right ? left : right;
    }
};

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：

一个二叉树_每个节点_ 的左右两个子树的高度差的绝对值不超过 1 。

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
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        return depth(root) != -1;
    }
    int depth(TreeNode* node) {
        if(!node) return 0;
        int left = depth(node->left);
        int right = depth(node->right);
        if(left == -1 || right == -1 || abs(left - right) > 1) {
            return -1;
        }
        return 1 + max(left, right);
    }
};

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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
/**
 * 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:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        depth(root, ans);
        return ans;
    }

    int depth(TreeNode* node, int& ans) {
        if(!node) return 0;
        int left = depth(node->left, ans);
        int right = depth(node->right, ans);
        ans = max(ans, left + right);
        return 1 + max(left, right);
    }
};

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

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
// 解法1
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int rst = 0;
        map<long long, int> mp = {{0, 1}};
        long long sum = 0;
        solve(root, mp, rst, sum, targetSum);
        return rst;
    }
    void solve(TreeNode* node, map<long long, int>& mp, int& rst, long long& sum, int targetSum) {
        if(!node) return ;
        sum += node->val;
        rst += mp[sum - targetSum];
        mp[sum]++;
        solve(node->left, mp, rst, sum, targetSum);
        solve(node->right, mp, rst, sum, targetSum);
        mp[sum]--;
        sum -= node->val;
    }
};

// 解法2
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        return pathSumOfStart(root, targetSum) +
               pathSum(root->left, targetSum) +
               pathSum(root->right, targetSum);
    }

    // 以root为起点的路径和为sum的路径数量
    long long int pathSumOfStart(TreeNode* root, long long int sum) {
        if(!root) return 0;
        long long int count = sum == root->val ? 1 : 0;
        count += pathSumOfStart(root->left, sum - root->val);
        count += pathSumOfStart(root->right, sum - root->val);
        return count;
    }
};

101. 对称二叉树

给你一个二叉树的根节点 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
/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }

    bool check(TreeNode* node1, TreeNode* node2) {
        if(!node1 && !node2) {
            return true;
        }
        if(!node1 || !node2 || node1->val != node2->val) {
            return false;
        }

        return check(node1->left, node2->right) && check(node1->right, node2->left);
    }
};

1110. 删点成林

给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。

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
/**
 * 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:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        map<int, bool> mp;
        vector<TreeNode*> ans;
        for(const auto& num : to_delete) {
            mp[num] = true;
        }
        root = solve(root, mp, ans);
        if(root) ans.push_back(root);
        return ans;
    }

    TreeNode* solve(TreeNode* root, map<int, bool>& mp, vector<TreeNode*>& ans) {
        if(!root) return root;
        root->left = solve(root->left, mp, ans);
        root->right = solve(root->right, mp, ans);
        if(mp[root->val]) {
            if(root->left) {
                ans.push_back(root->left);
            }
            if(root->right) {
                ans.push_back(root->right);
            }
            root = nullptr;
        }
        return root;
    }
};

层次遍历

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

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
/**
 * 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:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        if(!root) return ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            double sum = 0;
            for(int i = 0; i < size; ++i) {
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.emplace_back(std::move(sum / size));
        }
        return ans;
    }
};

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

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
/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int l1 = 0, l2 = 0;
        int r1 = preorder.size() - 1;
        int r2 = inorder.size() - 1;
        return build(preorder, l1, r1, inorder, l2, r2);
    }

    TreeNode* build(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2) {
        if(l1 > r1 || l2 > r2) {
            return nullptr;
        } else if(l1 == r1 && l2 == r2) {
            return new TreeNode(preorder[l1]);
        }
        int mid = l2;
        while(mid <= r2 && inorder[mid] != preorder[l1]) ++mid;
        int ln = mid - l2;
        TreeNode* root = new TreeNode(preorder[l1]);
        root->left = build(preorder, l1+1, l1+ln, inorder, l2, mid-1);
        root->right = build(preorder, l1+ln+1, r1, inorder, mid+1, r2);
        return root;
    }
};
// 空间换时间
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> mp;
        for(int i = 0; i < inorder.size(); ++i) {
            mp[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1, mp);
    }

    TreeNode* build(vector<int>& preorder, int l1, int r1, int l2, int r2, unordered_map<int, int>& mp) {
        if(l1 > r1 || l2 > r2) return nullptr;
        TreeNode* node = new TreeNode(preorder[l1]);
        int mid = mp[preorder[l1]];
        int ln = mid - l2;
        node->left = build(preorder, l1+1, l1+ln, l2, mid-1, mp);
        node->right = build(preorder, l1+ln+1, r1, mid+1, r2, mp);
        return node;
    }
};

144. 二叉树的前序遍历

给你二叉树的根节点 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
/**
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()) {
            TreeNode* t = stk.top();
            stk.pop();
            ans.push_back(t->val);
            if(t->right) stk.push(t->right);
            if(t->left) stk.push(t->left);
        }
        return ans;
    }
};

二叉查找树

99. 恢复二叉搜索树

给你二叉搜索树的根节点 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
/**
 * 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:
    void recoverTree(TreeNode* root) {
        TreeNode *error1 = nullptr, *error2 = nullptr;
        TreeNode* prev = nullptr;
        recover(root, prev, error1, error2);
        int t = error1->val;
        error1->val = error2->val;
        error2->val = t;
    }
    void recover(TreeNode* node, TreeNode*& pre, TreeNode*& error1, TreeNode*& error2) {
        if(!node) return ;
        recover(node->left, pre, error1, error2);
        if(pre && pre->val > node->val) {
            if(!error1) {
                error1 = pre;
                error2 = node;
            } else {
                error2 = node;
            }
        }
        pre = node;
        recover(node->right, pre, error1, error2);
    }
};

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

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
/**
 * 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* trimBST(TreeNode* root, int low, int high) {
        if(!root) return root;
        if(root->val < low) {
            return trimBST(root->right, low, high);
        } else if(root->val > high) {
            return trimBST(root->left, low, high);
        } else {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
        }
        return root;
    }
};

字典树（前缀树）

208. 实现 Trie (前缀树)

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
    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
    class Trie {
    public:
        Trie* children[26];
        bool word;
    public:
        Trie() {
            for(int i = 0; i < 26; ++i) {
                children[i] = nullptr;
            }
            word = false;
        }
        
        void insert(string word) {
            Trie* t = this;
            for(const auto& c : word) {
                int child = c - 'a';
                if(!t->children[child]) {
                    t->children[child] = new Trie();
                }
                t = t->children[child];
            }
            t->word = true;
        }
        
        bool search(string word) {
            Trie* t = this;
            for(const auto& c : word) {
                int child = c - 'a';
                if(!t->children[child]) {
                    return false;
                }
                t = t->children[child];
            }
            return t->word;
        }
        
        bool startsWith(string prefix) {
            Trie* t = this;
            for(const auto& c : prefix) {
                int child = c - 'a';
                if(!t->children[child]) {
                    return false;
                }
                t = t->children[child];
            }
            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);
     */

    图

    二分图

    785. 判断二分图

    存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。

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
class Solution {
public:
	// 染色 + 广度搜索
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> color(graph.size(), 0);
        queue<int> que;
        for(int i = 0; i < graph.size(); ++i) {
            if(color[i] == 0) {
                color[i] = 1;
                que.push(i);
            }
            while(!que.empty()) {
                int v = que.front();
                que.pop();
                for(const auto& nv : graph[v]) {
                    if(color[nv] == 0) {
                        color[nv] = color[v] == 1 ? 2 : 1;
                        que.push(nv);
                    } else if(color[nv] == color[v]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

拓扑排序

210. 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0); // 每个节点的入度
        vector<vector<int>> graph(numCourses); // 图的邻接表示
        // 生成邻接图和入度表
        for(const auto& pair : prerequisites) {
            indegree[pair[0]]++;
            graph[pair[1]].push_back(pair[0]);
        }

        queue<int> zero_indegree;
        vector<int> ans;
        // 计算入度为0的节点
        for(int i = 0; i < numCourses; ++i) {
            if(indegree[i] == 0) {
                zero_indegree.push(i);
            }
        }

        while(!zero_indegree.empty()) {
            int course = zero_indegree.front();
            zero_indegree.pop();
            ans.push_back(course);
            // 更新入度
            for(const auto& next : graph[course]) {
                indegree[next]--;
                if(indegree[next] == 0) {
                    zero_indegree.push(next);
                }
            }
        }

        // 检查是不是还有课程没学
        for(int i = 0; i < numCourses; ++i) {
            if(indegree[i]) {
                return {};
            }
        }

        return ans;
    }
};
上一页
2024-01-05 16:19:44 # 技术 # CS基础 #算法和数据结构
下一页