Skip to content

Latest commit

 

History

History
415 lines (273 loc) · 16.5 KB

Roadmap.md

File metadata and controls

415 lines (273 loc) · 16.5 KB
Raw

Rickey's Roadmap

数据结构

0. 常见操作

https://github.com/RickeyBoy/LeetCodeGists/blob/master/dataStructure/Basic.md

1. 链表

https://github.com/RickeyBoy/LeetCodeGists/blob/master/dataStructure/ListNode.md

2. 二叉树

https://github.com/RickeyBoy/LeetCodeGists/blob/master/dataStructure/BinaryTree.md

3. 二叉堆

https://github.com/RickeyBoy/LeetCodeGists/blob/master/dataStructure/BinaryHeap.md

4. 并查集

https://github.com/RickeyBoy/LeetCodeGists/blob/master/dataStructure/UnionFind.md

基础类型

1. Sliding window，滑动窗口类型

分类
  • 固定窗口大小
  • 可变窗口，求解最大or最小的满足条件的窗口
求解
  • 固定窗口：同时移动左右指针，保证窗口宽度一定
  • 可变窗口：分别移动左右指针
  • 移动后需要及时更新状态位、最优解等
关键字

“连续子串 xxxx”、“连续子数组 xxxx”

模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window; // 有时可以直接用 vector 替代
  	int left = 0, right = 0;
    int sameCount = 0; 
  	// 初始化
    for (char c : t) need[c]++;
    while (right < s.size()) {
        // 右移窗口
        right++;
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
      
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // 左移窗口
            left++;
            ...
        }
    }
}
例题
参考资料

2. Two points 双指针类型

分类
  • （同向）快慢指针：链表、环形数组
  • （反向）双向指针：线性数组字符串等
  • （同向）滑动窗口：独立章节分析
  • （反向）二分查找：独立章节分析
例题

3. Binary Search 二分查找

注意点
  • 注意二分的边界条件
模板
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while (right >= left) {
            int mid = (right - left) / 2 + left;
            if (nums[mid]==target) {
                return mid;
            } else if (nums[mid]<target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};
例题

4. 深度优先搜索 DFS

求解
  • 定义通用 dfs 函数，函数需要拼上每一步需要的参数
  • 递归调用
关键字

“输出所有可能结果”

例题

5. 宽度优先搜索 BFS

求解：
  • 定义通用 bfs 函数，函数需要拼上每一步需要的参数
  • 递归调用，每一次递归都需要探索当前的所有可能
  • 通常可以转化为二叉树 or 图的问题
关键字
  • "二叉树"、"区域（图）"
例题：

6. 回溯

求解
  • 标准回溯：递归 + 回溯
  • 广义回溯：递归，全排列
  • 维护当前进行的步骤情况
关键字
  • “全排列”、“全部组合”
例题

动态规划

0. Fibonacci Numbers 斐波那契数列

求解
  • 一维线性递推公式
  • 可以使用特征根
例题

1. 0/1 Knapsack, 0/1背包 & Unbounded Knapsack, 无限背包

求解
  • 状态转移数组：dp[背包容量][可选择的物品]
  • 状态转移方程：dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], dp[i - 1][w]);
  • 是否可以状态压缩？
模板
/* 01背包算法框架 */
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // base case 已初始化
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                               dp[i - 1][w]);
            }
        }
    }
    return dp[N][W];
}
例题

2. Subsequence 子序列问题

求解
  • 一维的 dp 数组（二维的压缩版）
  • 二维的 dp 数组
模板：一维dp（二维 dp 压缩）
int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] = 最值(dp[i], dp[j] + ...)
    }
}
模板：二维dp
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    }
}
例题

3. State Machine 状态机

求解：
  • dp[x][y][z] 的含义就是：今天是第 x 天，至今最多进行 y 次交易，我现在z(持有or未持有)着股票
模板：一维dp（二维 dp 压缩）
// base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
// 状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
例题

高级类型

1. 字典树Trie

Todo

模板：Trie 字典树

TODO

2. 最短路算法

  1. LeetCode 743. 网络延迟时间

3. 最小生成树

  1. 1584. 连接所有点的最小费用

4. 拓扑排序

  1. LeetCode 207. 课程表

5. 二叉搜索树

  1. 面试题 04.06. 后继者 - medium

系列题目

1. 排序

https://github.com/RickeyBoy/LeetCodeGists/blob/master/series/sort.md

2. 回文子系列

https://zhuanlan.zhihu.com/p/61166108

Longest Palindromic Subsequence，最长回文子序列Longest Palindromic Substring，最长回文子字符串Count of Palindromic Substrings，最长子字符串的个数问题Minimum Deletions in a String to make it a Palindrome，怎么删掉最少字符构成回文Palindromic Partitioning，怎么分配字符，形成回文

3. TwoSum 系列

4. N 皇后问题

5. 股票手续费问题

特殊算法

参考资料

LeetCode按照怎样的顺序来刷题比较好？ - 知乎

ACM金牌选手整理的【LeetCode刷题顺序】 - 编程熊的文章 - 知乎

数据结构参考 - labuladong