一、前缀和：
1）模板：
    一维：
        int[] sum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) sum[i] = sum[i - 1] + nums[i - 1];
    二维：
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        // 1 暴力枚举所有大小的矩形区域的面积
        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = i; p <= n; p++) {
                    for (int q = j; q <= m; q++) {
                        int area = sum[p][q] - sum[p][j - 1] - sum[i - 1][q] + sum[i - 1][j - 1];
                        if (area <= k) res = Math.max(res, area);
                    }
                }
            }
        }       
2）应用场景：
    一维：o(1)求区间和 [i, j]段 区间和为 sum[j + 1] - sum[i] ; 求子数组、子串问题，如560和为k的子数组的数量
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i <= nums.length; i++) { // 注意从0开始，单个元素也可以看成一个区间
            res += map.getOrDefault(sum[i] - k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        return res;
    二维：求不超过K的最大矩阵面积 ：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
          1292. 元素和小于等于阈值的正方形的最大边长  https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
二、差分
1）模板：
    一维：b[0] = a[0]; for (int i = 1; i < n; i++) b[i] = a[i] - a[i - 1];  // 将[l,r]区间增加某个数 b[l] + c， b[r + 1] - c, 然后再求前缀和
    二维：将(x1,y1) (x2,y2)矩阵所有点加到c， b[x1,y1] +=c b[x1,y2 + 1] -=c b[x2 + 1,y1] -=c b[x2 + 1,y2 + 1] +=c
2）场景：将区间加上某个数，区间的最大重叠数，
    一维：413. 等差数列划分  https://leetcode-cn.com/problems/arithmetic-slices/   
    1094. 拼车  https://leetcode-cn.com/problems/car-pooling/  构造差分数组，区间内增加值（乘客数），然后求前缀和和最大值比较，类同的有 1109. 航班预订统计
    731. 我的日程安排表 II https://leetcode-cn.com/problems/my-calendar-ii/ 732. 我的日程安排表 III  https://leetcode-cn.com/problems/my-calendar-iii/  使用扫描线方式，并非构造差分数组。因为数据量太大。

三、Trie树
1）模板：
    Trie trie = new Trie();
    class Trie {
        Trie[] node = new Trie[26];
        boolean end;
        String w;

        void insert(String word) {
            Trie tmp = trie;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (tmp.node[ch - 'a'] == null)  tmp.node[ch - 'a'] = new Trie();
                tmp = tmp.node[ch - 'a'];
            }
            tmp.end = true;
            tmp.w = word;
        }
        boolean search(String word) {
            Trie tmp = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (tmp.trie[ch - 'a'] == null) return false;
                tmp = tmp.trie[ch - 'a'];
            }
            return tmp.end;
        }       
    }
    // dfs遍历 trie树找匹配的单词
    boolean dfs(WordDictionary trie, String word, int i) {
        if (i == word.length() && trie.end) return true;
        for (int j = i; j < word.length(); j++) {
            char ch = word.charAt(j);
            if (ch != '.') {
                if (trie.node[ch - 'a'] == null) return false;
                return dfs(trie.node[ch - 'a'], word, i + 1);
            } else {
                // 为.则当前层满足，遍历树的所有子节点
                for (int k = 0; k < 26; k++) {
                    if (trie.node[k] != null && dfs(trie.node[k], word, i + 1)) return true; 
                }
            }   
        }

        return false;
    }   
2）应用场景：单词快速匹配，字符串前后缀处理
    211. 添加与搜索单词 - 数据结构设计 dfs遍历 trie树找匹配单词典型题
    212. 单词搜索 II  https://leetcode-cn.com/problems/word-search-ii/  将单词先加到trie中，然后dfs遍历矩阵，并在trie中找到匹配的单词。
    421. 数组中两个数的最大异或值  trie树存储数值对应的二进制码，每个节点存储一位。树根存储最高位。
            for (int i = 30; i >= 0; i--) {
                int bit = n >> i & 1;
                if (tmp.node[bit] == null) {
                    tmp.node[bit] = new Trie();
                }
                tmp = tmp.node[bit];
            }
    648. 单词替换  在trie中找最小匹配的前缀。
    820. 单词的压缩编码  trie树处理字符串后缀场景，这里有个技巧先排序插入最长的单词，插入时是从后向前插入for (int i = word.length() - 1; i >= 0; i--)，插入过程中判断是否满足后缀匹配
    1023. 驼峰式匹配  处理大小写字母的场景  Trie[] node = new Trie[58];
四：并查集
1）模板：
    int[] p;
    for (int i = 0; i < n; i++) p[i] = i; // 初始化并查集
    int find(int x) {// 找父节点
        if (p[x] != x) p[x] = find(p[x]); // 路径压缩
        return p[x];
    }
    void union(int x, int y) { // 合并
        p[find(x)] = find(y);
    }
2）应用场景：求连通性，求连通块的数量（如朋友圈，岛屿数量）
    839. 相似字符串组  将具有相似性的字符串放到一个集合中，使用并查集，最后返回连通块的数量。
    886. 可能的二分法  不同于普通并查集，这里只给两两不能连通的点。使用两倍的并查集。
        father = new int[N*2+5];    //开两倍的数组
        for(int i = 1; i < N*2+5; i++) //初始化并查集
            father[i] = i;
        for(int i = 0; i < dl.length; i++){
            int x = find(dl[i][0]); //查找自己的根节点
            int y = find(dl[i][1]);
            int a = find(dl[i][0] + N); //查找自己不喜欢的人的根节点
            int b = find(dl[i][1] + N); 
            if(x == y) return false; //发现这俩人已经在一组
            else{
                father[a] = y;  //将不喜欢的人合并
                father[b] = x;
            }
        }   
    924. 尽量减少恶意软件的传播  使用额外的s数组存储连续块的节点数量。
    947. 移除最多的同行或同列石头   计算连通块的数量，技巧在于转换构造并查集，每个石头和其它石头对比判断在同一行或同一列则合并
    1722. 执行交换操作后的最小汉明距离  使用map存储连通块的节点
五：二分
1）模板：
    while (l < r) { // 求最左侧满足的
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    while (l < r) { // 求最右侧满足的
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
2）应用场景：在具有二段性的场景下快速查找满足条件的 最右侧或最左侧的值，一般可以二分索引，二分值，求最值问题一般可以用二分
    410. 分割数组的最大值 求最大值最小类问题，一般可以用二分，这里枚举每段区间的和 mid, 判断若每段和不超过mid的情况下能否分为m分。求最小，所以r=mid
    436. 寻找右区间  索引二分查找最右侧满足条件的区间的索引。需要先排序保证二段性, map存储区间及对应索引
    778. 水位上升的泳池中游泳 其中一个解法是二分法，二分找t,看能否从起点dfs到终点。找最左侧即最小的t ，类同的有1631. 最小体力消耗路径
    875. 爱吃香蕉的珂珂  二分枚举速度mid 判断在mid速度下能否在t的时间限制内吃完所有香蕉，这里有个技巧： a/b上取整 = (a+b-1)/b下取整
    1011. 在 D 天内送达包裹的能力  二分枚举运载能力 mid, 判断能否在mid运载量下能否在指定天数完成所有货运载。
        boolean check(int[] weights, int mid, int D) {
        // 检查D天内能否在运载能力不超过mid的前提下，运送完成
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] > mid) return false;
            sum += weights[i];
            if (sum > mid) {
                cnt++;
                sum = weights[i];
            }
        }
        return cnt + 1 <= D;
    }
    1898. 可移除字符的最大数目  二分求最大的k，具有二段性。判断子序列使用双指针，若相同则都向后移动，否则原串向后移动，最终判断模式串是否到尾部

六：单调栈
1）模板：
        Stack<Integer> st = new Stack<>();
        int n = arr.length;
        int[] left = new int[n]; // 左侧比自己小的，将st中>=自己的元素全部弹出
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] > = arr[i]) {
                st.pop();
            }
            if (st.isEmpty()) left[i] = -1; // 若没有比自己小的数，则置为-1，可以认为是0前面的位置
            else left[i] = st.peek();
            st.push(i);
        }
        st.clear();
        int[] right = new int[n];  // 右侧比自己小的
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[st.peek()] >= arr[i]) {
                st.pop();
            }
            if (st.isEmpty()) right[i] = n;
            else right[i] = st.peek();
            st.push(i);
        }
2）应用场景：找左右第一个比自己大或小的数或其位置
    84. 柱状图中最大的矩形  对每个点找到左，右第一个比自己小的位置l,r 则可组成的最大面积是 h * (r - l - 1) 
    503. 下一个更大元素 II 求右侧第一个比自己大的元素的值（从后向前枚举），所以将站中<=自己的全部弹出。这里有个技巧：数组成环，可以将原数组拷贝一份接在后面，对新数组求。记录答案时只记录前一半。
    739. 每日温度  求右侧第一个比自己大的位置（从后向前枚举），然后求出位置差。
    901. 股票价格跨度  求左侧第一个比自己大的位置。
七：单调队列
1）模板：
        Deque<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (q.size() > 0 && i - q.peekFirst() + 1 > k) q.pollFirst();
            while (q.size() > 0 && a[q.peekLast()] >= a[i]) q.pollLast();  // 这里求最小值，最大值更新为<=a[i]

            q.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
2）应用场景：滑动窗口求最值一般用单调队列，求最大值则需要单调递减队列，每次取队头。 求最小值是递增，每次取队头。
    239. 滑动窗口最大值 
八：双指针 & 滑动窗口
1）模板：
        // 双指针1，前后指针
        for (int i = 0; i < nums.length; i++) { // 前后指针一般用于找到一段连续的区间（如字符串中的连续数字，满足某个条件的区间）
            int j = i;
            while (j + 1 < nums.length && nums[j] + 1 == nums[j + 1]) j++;
            if (j == i) res.add(String.valueOf(nums[i]));
            else res.add(nums[i] + "->" + nums[j]);
            i = j; 
        }
        // 双指针 单调向右移动
        int j = 0;
        int res = 0;
        int pMax = 0; // 缓存当前最大的利润
        for (int i = 0; i < worker.length; i++) {
            // 找到该工人最能接受的最大难度
            while (j < tasks.size() && worker[i] >= tasks.get(j).difficult) {
                pMax = Math.max(pMax, tasks.get(j).profit);
                j++;
            }
            res += pMax;
        }       
        // 滑窗 求最小满足条件的
        int l = 0;
        int[] win = new int[58];
        for (int i = 0; i < arr.length; i++) {
            // l固定，i向右移动直到窗口中包含所有t的字符，记录答案，然后调整l向左移动直到窗口不能满足包含所有t的字符
            win[arr[i] - 'A']++;
            // 检查窗口中的元素是否全部包含cnt中的元素
            while (check(win, cnt)) {
                // 更新答案
                if (i - l + 1 < minLen) {
                    minLen = i - l + 1;
                    res = s.substring(l, i + 1);
                }

                // 调整l指针向左移动，并更新窗口的计数
                win[s.charAt(l) - 'A']--;
                l++;
            }
        }   
        // 滑窗 求最大满足条件的，或满足条件的子串，子数组数量   
        int m = 1;
        for (int r = 0, l = 0; r < nums.length; r++) {
            m *= nums[r];
            while (l <= r && m >= k) { // 注意：l可以等于r 
                m /= nums[l];
                l++;
            }
            res += r - l + 1;
        }
2）应用场景：双指针滑动窗口使用场景一般是要求满足单调性，简单来说一个指针向右移动，另外一个指针也要单调向右移动。双指针可以是左右指针，或前后指针。滑动窗口一般和子串子数组结合。
    76. 最小覆盖子串 滑动窗口典型问题，使用数组来维护窗口，若窗口满足条件则更新答案，并缩小窗口直到不满足为止。
    228. 汇总区间  使用前后指针找到满足条件的区间，然后再从区间后继续处理。
    395. 至少有 K 个重复字符的最长子串  窗口不满足单调性，枚举窗口中不同字符数量，再使用滑窗
    633. 平方数之和  双指针处理，这里用左右指针l=0,r=sqrt(c)，然后向中间并拢 找到满足条件的l,r
    713. 乘积小于K的子数组  都是正数满足单调性，可以用滑窗, 这里求满足条件的子数组个数。
    826. 安排工作以达到最大收益  这里隐式使用双指针，将工人排序后，后面的工人就不需要从头遍历每个难度了。从前面工人找到的难度i后继续扫描。
    849. 到最近的人的最大距离  找到连续的0区间[i, j]，将位置安排在区间中点(j - i + 1) /2
    1004. 最大连续1的个数 III  转换为最多包含k个0的最大区间。使用滑窗找。这里直接用一个变量zero来维护窗口中0的数量，不需要使用map或数组来维护。
    1838. 最高频元素的频数  贪心+前缀和+滑窗，枚举每个右端点，在前面找到l使得l,r区间满足条件。这里求最大的区间
        int l = 1; 
        int sum = 0;
        int res = 0;
        for (int r = 1; r <= nums.length; r++) {
            while ((r - l + 1) * nums[r - 1] - (s[r] - s[l - 1]) > k) l++;
            res = Math.max(res, r - l + 1);
        }   
九：HASH表
1）模板：
    map.computeIfAbsent(key, elm -> new ArrayList<>()).add(str); // 根据key 查找，若找不到则创建值（list），若存在则在值中加入str。

2）应用场景：主要是为了快速查找，存储。
    49. 字母异位词分组  map存储，key:单词排序后的串，值：排序后相同的原串list
    211. 添加与搜索单词 - 数据结构设计  map存储， key:串的长度，值：相同长度串的list
    336. 回文对  map先存储所有 串反转后的结果，key: 反转后的串，value:原串下标索引。 然后枚举原串的所有前缀子串，看能否在map中找到对应的索引。
    648. 单词替换 可以用trie，也可以用map来处理一些前缀的问题。先将所有单词按长度从小到大排序，然后存入map中,key:首字符，value:以首字符开头的所有串（长度从小到大放在list中）
        然后遍历要处理的sentence，对每个单词首字符先找到list，然后对每个list的元素，在单词中找是否有对应 长度的前缀，若有则满足，使用该list元素
    720. 词典中最长的单词  将单词加到hash中，然后排序单词，对单词的每个前缀在hash中找是否存在。
    763. 划分字母区间  map存储每个字符的最后出现的位置（注意），然后遍历串对每个字符找到并更新最大的位置，若当前点出现最后位置和最大位置相同，则满足。
    916. 单词子集  这里用int[26]数组缓存通用字符，值是字符出现的最大次数。然后遍历原串，对比出现次数。


十：DFS & 回溯
1）模板：
    // dfs+回溯 先判断条件将满足的加入答案，然后每层做选择（选择时一般会有条件限制如长度，值，是否被使用过等），更新参数继续处理。
    public void dfs(String digits, int idx, String[] dirt, String track) {
        if (idx == digits.length()) {
            res.add(track);
            return;
        }

        // 每次可选择的字符
        String str = dirt[digits.charAt(idx) - '0'];
        for (int i = 0; i < str.length(); i++) {
            dfs(digits, idx + 1, dirt, track + str.charAt(i));
        }
    }
    // dfs搜索 一般用visit数组记录是否被用过，最后再回溯回来
    boolean dfs(char[][] board, String word, int x, int y, int idx) {
        if (word.charAt(idx) != board[x][y]) return false;
        if (idx == word.length() -1) return true; //已经搜索到最后一个字符，则返回true

        visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && !visit[nx][ny]) {
                if (dfs(board, word, nx, ny, idx + 1)) return true;
            }
        }
        visit[x][y] = false;
        return false;
    }
2）应用场景：一般应用在数据范围不大，最大不超过1000，然后求连通问题，搜索问题都可以用dfs , 求具体方案的问题一般是dfs+回溯 
    17. 电话号码的字母组合  在给定的数字串中，搜索合法的组合。求方案问题，dfs+回溯：使用map缓存数字对应的字符串，然后dfs枚举每个数字，每层选择上可以选择数字对应的所有字符
    22. 括号生成  在n对括号中搜索合法的括号匹配。求方案问题，dfs+回溯，每次可选择(或）,这里选择时要条件限制 ：
    public void dfs(int n, int lc, int rc, String track) {
        if (lc == n && rc == n) res.add(track);
        else {
            if (lc < n) dfs(n, lc + 1, rc, track + "(") ;
            if (rc < n && rc < lc) dfs(n, lc, rc + 1, track + ")") ;
        }
    }   
    51. N 皇后  典型的dfs+回溯，在n*n矩阵中搜索满足条件的方案。使用hash缓存每列，两对角线是否被占用，使用初始化n*n 矩阵，对每一行进行处理，每行都可以对行中所有字符变换为q，然后回溯处理 。
    78. 子集  典型的dfs+回溯  在1-n 构造的集合中搜索所有子集。只要path不超过n就加入答案，并继续后面的选择。
    void dfs(int[] nums, int idx, int n, List<Integer> path) {
        if (path.size() > n) return ;

        res.add(new ArrayList<>(path));  // 加入后继续处理。不reutrn
        for (int i = idx; i < n; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1, n, path);
            path.remove(path.size() - 1);
        }
    }
    79. 单词搜索  dfs搜索经典题。在二维数组中搜索满足条件的路径。
    93. 复原 IP 地址  在给定的串中搜索合法的ip方案，典型的dfs+回溯求方案问题：需要额外的参数k标识当前有几个满足的ip，每层可以选择[i,i+3]这一段子串，因为ip最大255.若不满足则退出当前层搜索。
    类似的题：剑指 Offer 46. 把数字翻译成字符串，这里每层选择只有两个自身或自身后的一个数字（若满足数字>=9）
    void dfs (String s, int idx, int k, String path) {
        if (idx == s.length() && k == 4) {
            res.add(path.substring(0, path.length() - 1)); // 去除最后的.
            return;
        }

        if (k == 4) return;  // 若已经找到四段ip，但串还有多余 字符直接返回
        for (int i = idx; i < s.length() && i < idx + 3; i++) {
            String sub = s.substring(idx, i + 1); 
            if (sub.length() > 1 && sub.charAt(0) == '0') break;
            if (Integer.parseInt(sub) > 255) break;
            dfs(s, i + 1, k + 1, path + sub + ".");
        }
    }   
    113. 路径总和 II  在二叉树中搜索路径，dfs+回溯：和上面模板不一样的是，遍历 处理时先将根加到path中，然后再判断条件是否满足。若满足则加到res中。每层只有左右子树两种选择。最后再将root从path中回溯移除。处理方式和 一样。
    类同：797. 所有可能的路径，对图（树）进行遍历
    void dfs(TreeNode root, int sum, List<Integer> path) {
        if (root == null) return;
        path.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            res.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
            return;
        }

        dfs(root.left, sum, path);
        dfs(root.right, sum, path);
        path.remove(path.size() - 1);
    }   
    131. 分割回文串  在串中搜索子串，子串要求是回文串，所以dfs+回溯。每层可以选择i,及后面所有的字符构成子串，判断子串是否为回文串，若满足则加到path中。
        这里有个技巧，用dp预处理每个子串区间。则可以 做到o1时间判断子串是否 为回文串。
        dp = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) dp[i][j] = true;
                else { // 只有两个字符，或中间段已是回文串，则i,j段也是
                    if (s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || dp[i + 1][j - 1])) dp[i][j] = true;
                }
            }
        }
    174. 地下城游戏  dfs搜索类问题，
    473. 火柴拼正方形 经典回溯问题，大量剪枝。先对火柴从大到小排序，每层可选择后面所有的，若找到一条合法的边需要从头选，需要用visit数组来配合哪些已经使用过。
    // idx 火柴索引，len当前边长，拼装边长为len的边数
    void dfs (int[] nums, int idx, int len, int num) {
        if (idx < nums.length && num == 3) {
            res = true;
            return;
        }
        if (len == sum / 4) {
            dfs(nums, 0, 0, num + 1); // 找到一条边后后面继续从第0个索引开始遍历
            return;
        }

        // 构造一条边
        for (int i = idx; i < nums.length; i++) {
            if (visit[i]) continue; // 已使用
            if (len + nums[i] > sum / 4) continue;

            visit[i] = true;
            dfs (nums, i + 1, len + nums[i], num);
            visit[i] = false;
        } 
    }   
    417. 太平洋大西洋水流问题  dfs搜索问题，从边界开始搜索，搜索继续下去的条件是四个方向的点>=当前点，最后求两个visit都为true即重合的点。注意不需要回溯，只需要计访问标记
    491. 递增子序列  dfs+回溯求子序列问题，找到满足条件的所有子序列，使用set去重处理保证不重复
    1239. 串联字符串的最大长度  dfs+回溯求最值问题，在给定的集合中搜索满足条件的子序列
    1593. 拆分字符串使唯一子字符串的数目最大, dfs+回溯求子串问题，找到原串的所有子串，然后剪枝，最终取最大的结果。
    void dfs(String s, int idx) {
        if (idx == s.length()) {
            res = Math.max(res, set.size());
            return;
        }

        for (int i = idx; i < s.length(); i++) {
            String sub = s.substring(idx, i + 1);
            if (set.contains(sub)) continue;
            set.add(sub);
            dfs(s, i + 1);
            set.remove(sub); 
        }
    }
    1631. 最小体力消耗路径  二分+dfs遍历， 二分每个高度看能否dfs遍历走到终点，即Math.abs(heights[newRow][newCol]-heights[row][col])<=mid

十一：BFS
1）模板：一般使用队列先缓存起点，然后将起点出队处理，然后再将其关联的点加到队列中。

2）应用场景：求最短路，搜索遍历，结合优先队列可以解决最优化问题。
    127. 单词接龙 BFS求最短路，从beginword每次变换一个字符能否走到endword，求最小次数。出队后对单词的每一位枚举26个字符，组成一个新的单词判断是否在列表中且未计算距离。若满足则加到path中。 加到队列中，同时更新距离。直到找到endword。
    126. 单词接龙 II  BFS求最短路， 相对上一题，多了求方案，从终点求到得起点的所有有效方案。
    void dfs (String w) {
        if (w.equals(begin)) {
            List<String> tmp = new ArrayList(path);
            Collections.reverse(tmp);
            res.add(tmp);
            return;
        }

        // 检举当前点可以变换的所有单词，
        for (int i = 0; i < w.length(); i++) {
            char[] chArray = w.toCharArray();
            for (char ch = 'a'; ch <= 'z'; ch++) {
                chArray[i] = ch;
                String tmp = new String(chArray);
                if (dist.containsKey(tmp) && dist.get(tmp) + 1 == dist.get(w)) {
                    path.add(tmp);
                    dfs(tmp);
                    path.remove(path.size() - 1);
                }
            }
        }
    }   
    207. 课程表 ： 有向无环图判断是否有环，bfs遍历求是否成环。拓扑排序：统计节点的入度，点的邻接点使用map存，key:点，value：邻接点list, 先将所有入度为0的加到队列中，
        然后出队加到答案中，并将邻接点的入度减1，若为0则加到队列中。直到队空，判断答案个数和点的个数是否相同。
    752. 打开转盘锁  BFS求最短路，思路和单词接龙题一样。这里是黑名单，不在黑名单中的可以 加到dist中。注意数字可以+1，0，-1，数字为负需要+10再对10取模处理。
    773. 滑动谜题 和上题思路类似，关键是要将二维数组转换为字符串后方便后面处理，涉及一二维互转的场景。出列时先找到一维串中0的位置idx,然后转换为二维x=idx/m, y=idx%m，然后求四个方向
        nx, ny使用dx,dy数。再将nx,ny转换为一维坐标nx*m+ny, 将该坐标和idx位置的0交换（将串转换为字符数组）。 然后求得新的字符数组转换为对应的新串。若新串没有计算过dist，则加到队列中。
        直到所有队列元素为空为止
    934. 最短的桥 多源BFS问题，先将一个岛中所有点加到队列中（dfs遍历），然后再bfs遍历，将队列中所有点出队，并将四个方向的点加入，直到找到另一个岛中的节点为止。这里dist中key为坐标,
        使用list来存，value为距离。 最后返回距离-1
十二：贪心
1）模板：
    无固定模板，一般要先排序，或假定某种方案最优（如零钱找零问题 ）
2）应用场景：
    354. 俄罗斯套娃信封问题  贪心+dp，先根据第一维宽度从小到大排序，然后求最长上升子序列长度 
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }   
    402. 移掉K位数字 贪心思想对于当前位i 可以删也可以不删，若i+1位置比其小，则删除i，所以可以用类似单调站的思想，将i前面大于其的位删除。
    860. 柠檬水找零 经典贪心问题，若顾客给的5元则不用找。 若给10元则只有一种方案看是否有5元,若收到20元，若有10元优先选择，再选择5元，若无10元则用三个五元

十三：DP
1）模板：

2）应用场景：

十四：平衡树
1）模板：

2）应用场景：

十五：区间问题
1）模板：

2）应用场景：

十六：背包问题
1）模板：

2）应用场景：