LeetCode Solutions

Dynamic Programming

debug

private static void printDp(int[] dp, int i) {
    System.out.print(i + ": ");
    for (int maxValue : dp){
        System.out.print(maxValue + "   ");
    }
    System.out.println();
}

509. 斐波那契数

方法一：DP

class Solution {
    public int fib(int n) {
        if (n == 0)
            return 0;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

方法二：DP + 滚动数组

class Solution {
    public int fib(int n) {
        if (n == 0)
            return 0;
        int[] dp = new int[3];
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i % 3] = dp[(i - 2) % 3] + dp[(i - 1) % 3];
        }
        return dp[n % 3];
    }
}

70. 爬楼梯

方法一：DP + 滚动数组

class Solution {
    public int climbStairs(int n) {
        // 1.dp[i]:爬上第i层楼梯的方法数
        // 2.状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]
        // 3.初始化：爬上第0层楼梯的方法数是1，dp[0] = 1,如果是0，那么dp[2] = 1！
        // 爬上第一层楼梯的方法数是1,dp[1] = 1
        int[] dp = new int[3];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3];
        }
        return dp[n % 3];
    }
}

746. 使用最小花费爬楼梯

注意：最后一个阶梯之后才是楼顶

方法一：DP + 滚动数组

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // dp[i]:爬到第i层的最小花费
        // 状态转移方程：dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
        // 初始化：dp[0] = 0, dp[1] = 0
        int n = cost.length;
        int[] dp = new int[3];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; ++i) {
            dp[i % 3] = Math.min(dp[(i - 2) % 3] + cost[i - 2], dp[(i - 1) % 3] + cost[i - 1]);
        }
        return dp[n % 3];
    }
}

剑指Offer 95

最优子结构：求最长公共子序列，求问题最优解，适合使用dp解决。
重叠子问题：求第一个字符串中位置0~\(i\)构成的子序列与第二个字符串中0~\(j\)构成的子序列的最大公共子序列\(f(i,j)\)，需要多次使用\(f(i-1, j-1), f(i-1,j),f(i,j-1)\)，拥有重叠子问题
状态转移方程： \[ f(i,j) = \begin{cases} f(i-1,j-1)+1, & ch[i]==ch[j] \\ max(f(i-1,j),f(i,j-1)), & else \\ \end{cases} \]
边界条件：dp[0][:] == 0, dp[:][] == 0

令两个字符串长度分别为\(m,n\)，

时间复杂度：双重for循环，\(O(mn)\)

空间复杂度：需要建立大小为(m+1)(n+1)的数组，因此空间复杂度为\(O(mn)\)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

如何优化空间复杂度？

剑指Offer 101 分割等和子集

分析：只要在数组中找到任意数等于数组累加和的一半，该数组就是等和子集，可抽象为经典0-1背包问题。

dp[i][j]:从编号0-i的物品中任选物品(可以都不选)，容量为j的背包能否正好装满
递归公式:dp[i][j] = dp[i-1][j] || j >= num[i] : dp[i-1][j-nums[i]] : false
初始化:
1. 当j==0时，即背包容量为0，不管有多少物品，只要什么都不选就能使背包总重量为0，所以f(i,0)=true
2. 当i==0 && j!= 0时，即物品数量为0，怎样都不能放满容量大于0的背包，所以f(0,i)=false
遍历顺序：先遍历物品再嵌套从头到尾遍历容量
打印dp数组验证与手写稿是否一致

空间复杂度优化：由于求第i行dp数组只需要用到第i-1行dp数组的信息，所以可以使用一维滑动dp数组代替二维dp数组。

剑指Offer 1049 最后一块石头的重量 II

从 stones数组中选择，凑成总和不超过 \(sum/2\) 的最大价值

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        // dp[j]:容量为j的背包能装下不超过target的最大价值
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; ++i) {
            for (int j = target; j >= stones[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }
}

一和零

背包问题中，weight里的数据不一定要升序！比如weights=[4,1,3]

方法一：DP

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j]:最多有i个0，j个1，最多能选的字符数量
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int k = 1; k <= strs.length; ++k) {
            String str = strs[k - 1];
            int num0 = 0, num1 = 0;
            for (int x = 0; x < str.length(); ++x) {
                if (str.charAt(x) == '0')
                    ++num0;
                else 
                    ++num1;
            }
            for (int i = 0; i <= m; ++i) {
                for (int j = 0; j <= n; ++j) {
                    if (i < num0 || j < num1)
                        dp[k][i][j] = dp[k - 1][i][j];
                    else 
                        dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - num0][j - num1] + 1);
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

方法二：DP+滚动数组

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j]:最多有i个0，j个1，最多能选的字符数量
        int[][] dp = new int[m + 1][n + 1];
        for (int k = 1; k <= strs.length; ++k) {
            String str = strs[k - 1];
            int num0 = 0, num1 = 0;
            for (int x = 0; x < str.length(); ++x) {
                if (str.charAt(x) == '0')
                    ++num0;
                else 
                    ++num1;
            }
            for (int i = m; i >= num0; --i) {
                for (int j = n; j >= num1; --j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - num0][j - num1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

518. 零钱兑换 II

经典完全背包问题，解题步骤如下：

dp[j]：背包容量为j时，放满背包的组合方法数
状态转移公式：dp[j] = dp[j] + dp[j - coins[i]]
初始化dp[0]：背包容量为0时，有一种方法放满背包（什么都不放）
遍历顺序：求组合数，先便利物品，再遍历容量
遍历dp数组

关于组合和排列的理解：先遍历物品后遍历背包是这样，比如，外层循环固定coins[1]，在内层循环遍历背包时，随着背包不断增加，coins[1]可以重复被添加进来，而由于外层循环固定了，因此coins[2]只能在下一次外层循环添加进不同大小的背包中，这么看的话，coins[i + 1]只能在coins[i]之后了；如果先遍历背包后遍历物品，那么外层循环先固定背包大小j，然后在大小为j的背包中循环遍历添加物品，然后在下次外层循环背包大小变为j+1，此时仍要执行内层循环遍历添加物品，也就会出现在上一轮外层循环中添加coins[2]的基础上还能再添加coins[1]的情况，那么就有了coins[1]在coins[2]之后的情况了(逆序)。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

377. 组合总和 Ⅳ

先举个例子，nums = [1, 2, 3]，target = 35.
假设用1，2，3拼凑出35的总组合个数为y。我们可以考虑三种情况：
（1）有效组合的末尾数字为1，这类组合的个数为 x1。我们把所有该类组合的末尾1去掉，那么不难发现，我们找到了一个子问题，x1即为在[1，2，3]中凑出35 - 1 = 34的总组合个数。因为我如果得到了和为34的所有组合，我只要在所有组合的最后面，拼接一个1，就得到了和为35且最后一个数字为1的组合个数了。
（2）有效组合的末尾数字为2，这类组合的个数为 x2。我们把所有该类组合的末尾2去掉，那么不难发现，我们找到了一个子问题，x2即为在[1，2，3]中凑出35 - 2 = 33的总组合个数。因为我如果得到了和为33的所有组合，我只要在所有组合的最后面，拼接一个2，就得到了和为35且最后一个数字为2的组合个数了。
（3）有效组合的末尾数字为3，这类组合的个数为 x3。我们把所有该类组合的末尾3去掉，那么不难发现，我们找到了一个子问题，x3即为在[1，2，3]中凑出35 - 3 = 32的总组合个数。因为我如果得到了和为32的所有组合，我只要在所有组合的最后面，拼接一个3，就得到了和为35且最后一个数字为3的组合个数了。
这样就简单了，y = x1 + x2 + x3。而x1，x2，x3又可以用同样的办法从子问题得到。状态转移方程get！

全排列问题，转化为完全背包问题

dp[j]：在背包容量为j时，放满背包的排列数
状态转移公式：dp[j] = dp[j] + dp[j - nums[i]]
初始化dp[0]：在背包容量为0时，放满背包的排列数量为1（什么都不放）
遍历顺序，排列问题，先遍历背包容量(物品可以逆序放入dp[j - nums[i]])，再遍历物品
打印dp数组

70. 爬楼梯

完全背包 + 全排列问题，可以重复选择放入物品1与物品2，求放满容量为n的背包的排列数

dp[j]：在背包容量为j时，放满背包的排列数
状态转移公式：dp[j] = dp[j] + dp[j - nums[i]]
初始化dp[0]：在背包容量为0时，放满背包的排列数量为1（什么都不放）
遍历顺序，排列问题，先遍历背包容量(物品可以逆序放入dp[j - nums[i]])，再遍历物品
打印dp数组

322. 零钱兑换

完全背包问题

dp[j]：背包容量为j时，凑满背包容量所需的最少硬币数
状态转移公式：dp[j] = min(dp[j], dp[j - coins[i]] + 1)
初始化dp[0]：背包容量为0时，凑满背包容量所需的最少硬币数时0,其他初始化为Integer.MAX_VALUE
遍历顺序，无所谓
打印dp数组

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[j]: 凑成整数j所需的最少的硬币书
        // 状态转移方程：dp[j] = min(dp[j], dp[j - nums[i] + 1])
        // 初始化：dp[0] = 0,其他初始化为1
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < coins.length; ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE)
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

279. 完全平方数

dp[j]：装满容量为j的背包，至少要放多少个物品
状态转移公式：dp[j] = min(dp[j], dp[j - weights[i]] + 1)
初始化dp[0]:装满容量为0的背包，至少放0个物品；其他设为Integet.MAX_VALUE
遍历顺序：无所谓
打印dp数组

class Solution {
    public int numSquares(int n) {
        // 完全背包问题
        // 定义物品的weights数组，先找到小于等于n的最大完全平方数
        int max_weight = (int)(Math.sqrt(n));  
        int[] weights = new int[max_weight];
        for(int i = 1; i <= max_weight; i++)
            weights[i-1] = i*i;    
        // 1.dp[j]：装满容量为j的背包，至少要放多少个物品
        int[] dp = new int[n + 1];
        // 2.状态转移公式：dp[j] = min(dp[j], dp[j - weights[i]] + 1)
        // 3.初始化dp[0]:装满容量为0的背包，至少放0个物品；其他设为Integet.MAX_VALUE
        for(int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // 4.遍历顺序：无所谓
        for(int i = 0; i < weights.length; i++) {
            for(int j = weights[i]; j <= n; j++) {
                if(dp[j - weights[i]] != Integer.MAX_VALUE)
                    dp[j] = Math.min(dp[j], dp[j - weights[i]] + 1);
            }
           // printDp(dp, i);
        }
        return dp[n];
        // 5.打印dp数组
    }

    private static void printDp(int[] dp, int i) {
        System.out.print(i + ": ");
        for (int maxValue : dp){
            System.out.print(maxValue + "   ");
        }
        System.out.println();
    }

}

139. 单词拆分

背包问题 + 排列(“leetcode”由“leet”与“code”组成但不能反过来由“code”与“leet”组成 )的变种，建议不要完全抽象成背包问题，便于理解

dp[j]：长度为j的字符串，可以被字典中的单词拆分。
状态转移公式：if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true，其中j<i。
初始化dp[0]:dp[i]依赖于前面的dp[j]，所以dp[0]要初始化为true，不然全为false
遍历顺序：先遍历背包容量，再嵌套遍历物品
打印dp数组

198. 打家劫舍

dp[j]：偷窃从标号为0到j的房屋所能获得的最大价值
状态转移公式：dp[j] = max(dp[j - 1], dp[j - 2] + nums[j])
初始化：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
遍历顺序：单序列问题,dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！
遍历dp数组

优化空间复杂度

根据状态转移公式dp[j] = max(dp[j - 1], dp[j - 2] + nums[j])，dp[j]只需要dp[j-1]以及dp[j-2]两个变量即可，可以把数组大小压缩到2。

213. 打家劫舍 II

416. 分割等和子集

dp[j]：背包容量为j时，是否能用物品装满
状态转移方程：dp[j] = dp[j] || dp[j - nums[i]]
初始化：背包容量为0时，不把物品装进去即可装满，dp[0] = true
遍历顺序：一维滑动数组，零一背包，先遍历物品后遍历背包容量

337. 打家劫舍 III

方法一：HashMap

f：偷当前房屋能获得的最大价值；g：不偷当前房屋能获得的最大价值

偷当前房屋f(cur) = cur.val + g(cur.left) + g(cur.right)
不偷当前房屋g(cur) = max(f(cur.left), g(cur.left)) + max(f(cur.right), g(cur.right))

方法二：Morris + HashMap

当作是练习题了！！

注意事项：在访问的时候，此时需要cur.right，而这个时候已经是逆序过的，cur.right实际上指向的是自己的父节点，所以再用一个hashmap存储cur真正的右节点（或者再逆序一遍）。

class Solution {

    Map<TreeNode, Integer> f = new HashMap<>();
    Map<TreeNode, Integer> g = new HashMap<>();
    Map<TreeNode, TreeNode> right = new HashMap<>();

    public int rob(TreeNode root) {
        // f:偷当前节点能获得的最大价值
        // g:不偷当前节点能获得的最大价值
       //  f(cur) = cur.val + g(cur.left) + g(cur.right)
       //  g(cur) = max(f(cur.left), g(cur.left)) + max(f(cur.right), g(cur.right))
       TreeNode cur = root, mostRight = null;
       while (cur != null) {
           mostRight = cur.left;
           if (mostRight != null) {
               while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else { // mostRight.right = cur
                    mostRight.right = null;
                    visit(cur.left);
                }
           }
           cur = cur.right;
       }
       visit(root);
       return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    private void visit(TreeNode cur) {
        TreeNode tail = reverse(cur);
        cur = tail;
        while (cur != null) {
            f.put(cur, cur.val + g.getOrDefault(cur.left, 0) + g.getOrDefault(right.get(cur), 0));
            int maxLeft = Math.max(f.getOrDefault(cur.left, 0), g.getOrDefault(cur.left, 0));
            int maxRight = Math.max(f.getOrDefault(right.get(cur), 0), g.getOrDefault(right.get(cur), 0));
            g.put(cur, maxLeft + maxRight);
            if (cur.right != null) 
                right.put(cur.right, cur);
            cur = cur.right;
        }
        reverse(tail);
    }

    private TreeNode reverse(TreeNode cur) {
        TreeNode pre = null;
        while (cur != null) {
            TreeNode next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

121. 买卖股票的最佳时机

你根本没在dp！

方法一：暴力迭代

超时咯

方法二：贪心

从前往后遍历，使用minPrice记录最小值，使用maxProfit记录最大收益

方法三：DP

DP数组的定义十分重要！

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0 || prices == null)
            return 0;
        // 1.dp[0][j]:第j天持有股票(之前买入或者当前买入)所拥有的最大价值，dp[1][j]：第j天不持有股票(之前卖出或者当前卖出)所拥有的最大价值
        int[][] dp = new int[2][len];
        // 2.状态转移方程：dp[0][j] = max(dp[0][j-1], -price[j]); dp[1][j] = max(dp[1][j-1], price[j] + dp[0][j - 1])
        // 3.初始化：dp[0][0]必须买入，初始化为-price[0]；dp[1][0]不能卖出任何股票，初始化为0
        dp[0][0] = -prices[0];
        // 4.遍历顺序：dp[j]由dp[j-1]决定，所以从前往后遍历
        for (int j = 1; j < len; ++j) {
            dp[0][j] = Math.max(dp[0][j - 1], -prices[j]);
            dp[1][j] = Math.max(dp[1][j - 1], prices[j] + dp[0][j - 1]); // 不能当天买入当天卖出所以是dp[0][j - 1]
        }
        return dp[1][len - 1];
        // 5.打印dp数组
    }
}

122. 买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        // 1.dp[0][j]:在第j天持有(之前买入，当前买入)股票时拥有的最大现金;dp[1][j]在第j天不持有(之前卖出，当前卖出)股票拥有的最大现金
        int len = prices.length;
        int[][] dp = new int[2][len];
        // 2.状态转移方程：dp[0][j] = max(dp[0][j - 1], dp[1][j - 1] - price[j]); dp[1][j] = max(dp[1][j - 1], dp[0][j - 1] + price[j])
        // 3.初始化：dp[0][0] = -price[0];dp[1][0] = 0;可以当天出售
        dp[0][0] = -prices[0];
        // 4.遍历顺序
        for (int j = 1; j < len; ++j) {
            dp[0][j] = Math.max(dp[0][j - 1], dp[1][j - 1] - prices[j]);
            dp[1][j] = Math.max(dp[1][j - 1], dp[0][j - 1] + prices[j]);
        }
        return dp[1][len - 1];
        // 5.打印dp数组
    }
}

96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

优化空间..

123. 买卖股票的最佳时机 III

1372. 二叉树中的最长交错路径

class Solution {
        // f(cur)：以cur结尾，且cur是左子树的最大长度
        // g(cur)：以cur结尾，且cur是右子树的最大长度
        Map<TreeNode, Integer> f = new HashMap<>();
        Map<TreeNode, Integer> g = new HashMap<>();
        Queue<TreeNode[]> queue = new LinkedList<>();
    public int longestZigZag(TreeNode root) {
        // f.put(root, 0);
        // g.put(root, 0);
        queue.offer(new TreeNode[]{root, null});
        while (!queue.isEmpty()) {
            TreeNode[] sonFather = queue.poll();
            f.put(sonFather[0], 0);
            g.put(sonFather[0], 0);
            if(sonFather[1] != null) {
                if (sonFather[1].left == sonFather[0])
                    f.put(sonFather[0], g.get(sonFather[1]) + 1);
                if (sonFather[1].right == sonFather[0])
                    g.put(sonFather[0], f.get(sonFather[1]) + 1);
            }
            if (sonFather[0].left != null) 
                queue.offer(new TreeNode[]{sonFather[0].left, sonFather[0]});
            if (sonFather[0].right != null) 
                queue.offer(new TreeNode[]{sonFather[0].right, sonFather[0]});
        }
        int max = Integer.MIN_VALUE;
        for (TreeNode node : f.keySet()) {
            max = Math.max(max, Math.max(f.get(node), g.get(node)));
        }
        return max;
    }
}

300. 最长递增子序列

dp[i]：以nums[i]结尾的最长递增子序列的长度
从前往后，在i的左开区间进行比较所有的j(j < i)，如果nums[j]<nums[i]，那么dp[i] = max(dp[i], dp[j] + 1)
初始化：令dp数组所有元素为1，最短序列是本身
遍历顺序：第二层从前往后，从后往前都可以，只要把i之前的元素全部遍历了就行
要注意的是，要输出的答案不是dp[dp.length-1]，而是dp数组中的最大值，比如序列为01234512，输出的是结果是dp[5]；所以可以用一个全局变量记录dp数组中的最大值
时间复杂度：\(O(n^2)\)
空间复杂度：\(O(n)\)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLenOfSubsequence = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLenOfSubsequence = Math.max(maxLenOfSubsequence, dp[i]);
        }
        return maxLenOfSubsequence;
    }
}

674. 最长连续递增序列

方法一：DP

dp[i]：以nums[i]结尾的最长连续递增子序列的长度
当当前数字nums[i]大于nums[i-1]，令dp[i] = dp[i - 1] + 1
初始化：令dp数组所有元素为1，最短序列是本身
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLength = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        // for (int i = 0; i < dp.length; ++i) {
        //     System.out.print(dp[i] + " ");
        // }
        return maxLength;
    }
}

方法二：DP + 滑动数组

注意：当nums[i] <= nums[i - 1]时，需要把dp[i%2]重置为1

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return 1;
        int[] dp = new int[2];
        Arrays.fill(dp, 1);
        int maxLength = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i % 2] = dp[(i - 1) % 2] + 1;
            }
            else {
                dp[i % 2] = 1;
            }
            maxLength = Math.max(maxLength, dp[i % 2]);
        }
        return maxLength;
    }
}

718. 最长重复子数组:warning:

方法一：暴力

时间复杂度：\(O(m^2n)\)
空间复杂度：\(O(1)\)

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        for (int i = 0; i < nums1.length; ++i) {
            for (int j = 0; j < nums2.length; ++j) {
                int count1 = i, count2 = j;
                int counter = 0;
                while (count1 < nums1.length && count2 < nums2.length && nums1[count1] == nums2[count2]) {
                    ++counter;
                    ++count1;
                    ++count2;
                }
                res = Math.max(res, counter);
            }
        }
        return res;
    }
}

方法二：DP

dp[i][j]:以nums1[i - 1]结尾与以nums2[j - 1]结尾时的最长重复子数组
状态转移公式：当nums1[i - 1] == nums2[j - 1]时，dp[i][j] = dp[i - 1][j - 1] + 1
初始化：m为nums1的长度，n为nums2的长度，初始化(m + 1) * (n + 1)的二维数组，第一行第一列初始化为0，因为任一数组为空，就不会有重复子数组
注意事项：输出结果是dp数组中的最大值，因为最长的重复子数组不一定是在两数组的结尾处，可以在循环内比较
时间复杂度：\(O(mn)\)
空间复杂度：\(O(mn)\)

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }
}

滚动数组缩减空间复杂度

dp数组为第二个数组的长度加一
不相等时要把dp[j]赋0，不然之后会出错
此时遍历第二个数组的时候，就要从后向前遍历，这样避免重复覆盖。

比如nums1 = [1, 2, 3, 1],nums2 = [1,6,8,1,3,1,2,3]

i = 1时候，dp数组为[1,0,0,1,0,1,0,0]

i = 2时候，dp数组为[0,0,0,0,0,0,1,0]

i = 3时候，dp数组为[0,0,0,0,1,0,0,2]

i=3时，如果第二层for循环j从前往后遍历，那么dp倒数第二个位置会因为3!=2，被赋0，进而导致dp最后一个位置是1而不是2

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = nums2.length; j > 0; --j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                }
                else {
                    dp[j] = 0;
                }
                res = Math.max(res, dp[j]);
            }
        }
        return res;
    }
}

方法三：滑动窗口

62. 不同路径

方法一：DP O(mn)

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j]:走到i,j位置的路径数
        // 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        } 
        return dp[m - 1][n - 1];
    }
}

方法二：DP+滚动数组 O(n) 2行

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j]:走到i,j位置的路径数
        // 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        int[][] dp = new int[2][n];
        for (int i = 0; i < 2; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1];
            }
        } 
        return dp[(m - 1) % 2][n - 1];
    }
}

方法三：DP+滚动数组 O(n) 1行

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j]:走到i,j位置的路径数
        // 状态转移方程：dp[j] = dp[j] + dp[j - 1]
        // 初始化：全部初始化为1
        // 遍历顺序：dp[j]依赖dp[j - 1]，所以从左往右遍历
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] += dp[j - 1];
            }
        } 
        return dp[n - 1];
    }
}

63. 不同路径 II

方法一：DP

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j)  {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

343. 整数拆分:warning:

方法一：DP

class Solution {
    public int integerBreak(int n) {
        // dp[j]:j拆分为多个数的最大乘积
    
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                int k = i - j;
                dp[i] = Math.max(dp[i], Math.max(k * j, dp[k] * j));
            }        
        }
        return dp[n];
    }
}

96. 不同的二叉搜索树:warning:

剑指 Offer II 102. 加减的目标值

方法一：DP

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int diff = sum - target;
        if (diff % 2 == 1 || diff < 0)
            return 0;
        target = diff / 2;
        // dp[j]:装满容量为j的方法数
        // dp[0] = 1,装满容量为0的背包有一种
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

树形DP

左神shi'p

树形DP题目

Binary Tree

144. 二叉树的前序遍历

方法一：递归

假设树上一共有n 个节点。

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和递归使用的栈大小相关，递归层数不超过n(一叉树)，\(O(n)\)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        dfs(root, result);
        return result;
    }
    public void dfs(TreeNode root, List<Integer> result) {
        if (root == null)
            return;
        result.add(root.val);
        dfs(root.left, result);
        dfs(root.right, result);
    }
}

方法二：非递归

假设树上一共有n 个节点。

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和递归使用的栈大小相关，递归层数不超过n(一叉树)，\(O(n)\)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                result.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return result;
    }
}

方法三：Morris前序遍历

morris遍历利用树的大量空闲指针，实现空间开销的极限缩减。

时间复杂度：\(O(n)\)，其中n是二叉树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次

空间复杂度：\(O(1)\)，只操作已存在的指针（树的空闲指针），因此只需要常数的额外空间

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        TreeNode cur = root, mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) 
                    mostRight = mostRight.right;
                if (mostRight.right == null) {
                    result.add(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else { // mostRight.right == cur
                    mostRight.right = null;
                }
            }
            else { // cur.left == null
                result.add(cur.val);
            }
            cur = cur.right;
        }
        return result;
    }
}

94. 二叉树的中序遍历

方法一：递归

时间复杂度：\(O(n)\)，其中n为树的节点数

空间复杂度：\(O(n)\)，和递归使用的栈大小相关，递归层数不超过n(一叉树)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        dfs(root, result);
        return result;
    }

    public void dfs(TreeNode root, List<Integer> result) {
        if (root != null) {
            dfs(root.left, result);
            result.add(root.val);
            dfs(root.right, result);
        }
    }
}

方法二：非递归

时间复杂度：\(O(n)\)，其中n为树的节点数

空间复杂度：\(O(n)\)，和递归使用的栈大小相关，递归层数不超过n(一叉树)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

方法三：Morris中序遍历

morris遍历利用树的大量空闲指针，实现空间开销的极限缩减。

时间复杂度：\(O(n)\)，其中n是二叉树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次

空间复杂度：\(O(1)\)，只操作已存在的指针（树的空闲指针），因此只需要常数的额外空间

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        TreeNode cur = root, mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else { // mostRight == cur
                    mostRight.right = null;
                }
            }
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

145. 二叉树的后序遍历

方法一：递归

方法二：非递归

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right != null && cur.right != pre) {
                cur = cur.right;
            }
            else {
                stack.pop();
                res.add(cur.val);
                pre = cur;
                cur = null;
            }
        }
        return res;
    }
}

方法三：Morris后序遍历

时间复杂度：\(O(n)\)，其中n为树的节点数

空间复杂度：\(O(n)\)，和递归使用的栈大小相关，递归层数不超过n(一叉树)

如果可以到达一个节点两次(有左子树)，第二次逆序打印左子树上的右边界
最后走出循环后，逆序打印根节点的右边界

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        TreeNode cur = root, mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else { // mostRight.right = cur
                    mostRight.right = null;
                    visit(cur.left, res);
                }
            }
            cur = cur.right;
        }
        visit(root, res);
        return res;
    }
    private void visit(TreeNode cur, List<Integer> res) {
        TreeNode tail = reverse(cur);
        cur = tail;
        while (cur != null) {
            res.add(cur.val);
            cur = cur.right;
        }
        reverse(tail);
    }
    private TreeNode reverse(TreeNode cur) {
        TreeNode pre = null;
        while (cur != null) {
            TreeNode next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

102. 二叉树的层序遍历

借助队列实现，关键在于通过queue.size来判断下一层的节点数！

Queue.offer(null)的话，size为1！

226. 翻转二叉树

这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。（真假不做判断，权当一个乐子哈）

要求：左右子树交换位置

方法一：bfs层级遍历

时间复杂度：所有节点都需要入队，出队一次，所以是\(O(n)\)

空间复杂度：在最坏的情况下，给定的树是满二叉树，所有叶节点(\(n/2 + 1\))都要入队，所以是\(O(n)\)

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            reverse(cur);   
            if (cur.left != null)
                queue.offer(cur.left);
            if (cur.right != null)
                queue.offer(cur.right); 
        }
        return root;
    }
    private void reverse(TreeNode cur) {
        TreeNode temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;
    }
}

方法二：dfs

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 反转所有左子树和右子树，对这棵树的所有节点
        dfs(root);
        return root;
    } 
    private void dfs(TreeNode root) {
        if (root == null)
            return;
        dfs(root.left);
        dfs(root.right);
        reverse(root);
    }
    private void reverse(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

101. 对称二叉树

方法一：拷贝+翻转+判断(高情商：刷一道，解三道！低情商：只会笨方法？还是看看远方的复杂度吧)

写了80行，一题三解！不分析复杂度了。。

方法二：BFS

假设树上一共有n 个节点。

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和使用的队列大小相关，在最坏的情况下，给定的树是满二叉树，所有叶节点(\(n/2 + 1\))都要入队，所以是\(O(n)\)

注意：如果p,q都为空，continue！而不是return truel！！！

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        TreeNode p, q;
        while (!queue.isEmpty()) {
            p = queue.poll();
            q = queue.poll();
            if (p == null && q == null)
                continue;
            if (p == null || q == null)
                return false;
            if (p.val != q.val) 
                return false;
            queue.offer(p.left);
            queue.offer(q.right);
            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }
}

方法三：DFS

YYDS

假设树上一共有n 个节点。

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和递归使用的栈大小相关，递归层数不超过n(一叉树)，\(O(n)\)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left, root.right);
    }
    private boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left == null || right == null)
            return false;
        return (left.val == right.val) && dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}

100. 相同的树

对称二叉树方法一中用到了这个笨方法，顺手做了吧。

方法一：DFS

假设树上一共有\(n\)个节点

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和递归使用的栈大小相关，递归层数不超过n，\(O(n)\)

方法二：BFS

只是和对称二叉树BFS解法中的入队顺序改变一点。

假设树上一共有n 个节点。

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和使用的队列大小相关，在最坏的情况下，给定的树是满二叉树，所有叶节点(\(n/2 + 1\))都要入队，所以是\(O(n)\)

104. 二叉树的最大深度

方法一：BFS

时间复杂度：遍历整棵树，\(O(n)\)
空间复杂度：和使用的队列大小相关，在最坏情况下，给定的二叉树是满二叉树，\(n/2 + 1\)个叶节点要入队，所以是\(O(n)\)

方法二：DFS

假设树上一共有\(n\)个节点

时间复杂度：遍历了整棵树，\(O(n)\)

空间复杂度：和递归使用的栈大小相关，递归层数不超过n，\(O(n)\)

559. N 叉树的最大深度

同上题二叉树的最大深度，只是在遍历子节点的时候不同。

for (int i = 0; i < cur.children.size(); i++) {
    if (cur.children.get(i) != null)
        queue.offer(cur.children.get(i));
}

111. 二叉树的最小深度

最小深度是从根节点到最近叶子节点的最短路径上的节点数量

方法一：DFS

首先递归左子树和右子树
如果左子树为空，那么返回右子树的高度 + 1；如果右子树为空，那么返回左子树的高度 + 1
如果左右子树都不为空，那么返回他们最小高度 + 1

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null)
            return rightDepth + 1;
        if (root.right == null)
            return leftDepth + 1;
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

方法二：BFS

通过队列的size知道这是第几层，上一层加入队列节点的个数就是队列的size，在得到size的同时，将记录最小深度的变量minDepth加一
遍历到第一个叶子节点的当前层数就是二叉树的最小深度
时间复杂度：遍历整棵树，\(O(n)\)
空间复杂度：和使用的队列大小相关，在最坏情况下，给定的二叉树是满二叉树，\(n/2 + 1\)个叶节点要入队，所以是\(O(n)\)

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        int minDepth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ++minDepth;
            while (size-- > 0) {
                cur = queue.poll();
                if (cur.left == null && cur.right == null)
                    return minDepth;
                if (cur.left != null) 
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        return minDepth;
    }
}

222. 完全二叉树的节点个数

方法一：BFS

在每层开始遍历时，记录节点个数的变量加上队列里元素个数

方法二：DFS

边界：如果是空节点，返回0
递归左子树和右子树+1(当前节点)

class Solution {
    public int countNodes(TreeNode root) {
        return dfs(root);
    }
    public int dfs(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + dfs(root.left) + dfs(root.right);
    }
}

110. 平衡二叉树

方法一：先序DFS

终止条件：如果root为空，返回true
首先求当前节点左右子树高度是否<=1，再判断递归左子树和右子树
时间复杂度：\(O(n^2)\)
空间复杂度：\(O(n)\)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
}

方法二：后序DFS:warning:

只需遍历所有节点一次
时间复杂度\(O(n)\)
空间复杂度\((n)\)

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

257. 二叉树的所有路径:warning:

方法一：BFS

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<>();
        Queue<Object> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(String.valueOf(root.val));
        TreeNode cur;
        String path = "";
        while (!queue.isEmpty()) {
            cur = (TreeNode)queue.poll();
            path = (String)queue.poll();
            if (cur.left == null && cur.right == null) {
                result.add(path);
            }
            if (cur.left != null) {
                queue.offer(cur.left);
                queue.offer(path + "->" + String.valueOf(cur.left.val));
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queue.offer(path + "->" + String.valueOf(cur.right.val));
            }
        }
        return result;
    }
}

方法二：DFS

class Solution {
    List<String> result = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, "");
        return result;
    }
    public void dfs(TreeNode root, String path) {
        if (root == null)
            return;
        path += String.valueOf(root.val);
        if (root.left == null && root.right == null) {
            result.add(path);
        }
        else {
            path += "->";
            dfs(root.left, path);
            dfs(root.right, path);
        }
    }
 }

404. 左叶子之和

:warning:方法一：DFS

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root.left == null && root.right == null)
            return 0;
        return dfs(root);
    }
    private int dfs(TreeNode root) {
        if (root == null)
            return 0;
        int sum = 0;
        if (root.left != null) {
            sum += isLeaf(root.left) ? root.left.val : dfs(root.left);
        }
        if (root.right != null) {
            sum += dfs(root.right);
        }
        return sum;
    }
    private boolean isLeaf(TreeNode root) {
        return root.left == null && root.right == null;
    }
}

513. 找树左下角的值

:warning:方法一：DFS

class Solution {
    int curHeight = 0;
    int curValue = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return curValue;
    }
    private void dfs(TreeNode root, int height) {
        if (root == null)
            return;
        ++height;
        dfs(root.left, height);
        dfs(root.right, height);
        if (height > curHeight) {
            curHeight = height;
            curValue = root.val;
        }
    }
}

方法二：BFS

从右往左层次遍历，最后一个访问的节点就是树左下角的值！

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        TreeNode cur;
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur.right != null) {
                queue.offer(cur.right);
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            res = cur.val;
        }   
        return res;
    }
}

112. 路径总和

方法一：BFS

初始化一个Object类型队列，用于存放节点与节点的值，首先把根节点和根节点的值offer进队列
开始while循环，循环的执行条件是队列不为空
1. 首先按顺序取出节点和节点的值，注意这里需要强转
2. 判断当前节点是否为根节点且节点的值是否为目标值，如果满足，直接return true
3. 如果左子树不为空，先将左子树节点offer进队列，再将左子树的值加上poll出的当前节点的值offer进队列
4. 如果右子树不为空，先将右子树节点offer进队列，再将右子树的值加上poll出的当前节点的值offer进队列
如果有这么一条路径，那么在while循环中就会return true，不会执行到这；如果没有满足条件的路径，则返回false

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        Queue<Object> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root.val);
        TreeNode cur;
        while (!queue.isEmpty()) {
            cur = (TreeNode)queue.poll();
            int val = (int)queue.poll();
            if (cur.left == null && cur.right == null && val == targetSum) {
                return true;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
                queue.offer(val + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queue.offer(val + cur.right.val);
            }
        }
        return false;
    }
}

|:warning::warning:方法二：DFS

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null) 
            return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

113. 路径总和 II

方法一：BFS

使用队列存放当前节点和累加节点值
使用HashMap记录每个节点的父节点
当节点满足是叶节点且累加值等于targetSum时，通过HashMap，从该叶子节点遍历到根节点记录到list中，最后把list反转

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) 
            return res;
        Queue<Object> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root.val);
        TreeNode cur;
        Map<TreeNode, TreeNode> sonFather = new HashMap<>();
        while (!queue.isEmpty()) {
            cur = (TreeNode)queue.poll();
            int val = (Integer)queue.poll();
            if (cur.left == null && cur.right == null && val == targetSum) {
                res.add(getPath(cur, sonFather));
            }
            if (cur.left != null) {
                queue.offer(cur.left);
                queue.offer(val + cur.left.val);
                sonFather.put(cur.left, cur);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
                queue.offer(val + cur.right.val);
                sonFather.put(cur.right, cur);
            }
        }
        return res;
    }
    private List<Integer> getPath(TreeNode node, Map<TreeNode, TreeNode> sonFather) {
        List<Integer> path = new LinkedList<>();
        path.add(node.val);
        while (node != null) {
            node = sonFather.get(node);
            path.add(node.val);
        }
        Collections.reverse(path);
        return path;
    }

:warning:方法二：DFS

使用双端队列，每次dfs将当前节点值放入双端队列队尾，并让targetSum减去当前节点元素
如果当前节点是叶子节点且targetSum等于0，那么说明这条路径满足条件，将path加入结果
每次dfs完左右，再将双端队列最后一个元素移除！！！

class Solution {
    Deque<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
    private void dfs(TreeNode root, int targetSum) {
        if (root == null) 
            return;
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            res.add(new LinkedList<>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
}

:star:方法三：回溯(其实方法二也是回溯)

递归终止条件是：节点为空

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return res;
        dfs(root, targetSum);
        return res;
    }
    private void dfs(TreeNode root, int targetSum) {
        if (root == null)
            return;
        path.add(root.val);
        if (root.left == null && root.right == null && targetSum == root.val) {
            res.add(new LinkedList(path));
        }
        dfs(root.left, targetSum - root.val);
        dfs(root.right, targetSum - root.val);
        path.removeLast();
    }
}

:star:106. 从中序与后序遍历序列构造二叉树

草稿构造一棵二叉树，写出中序和后序序列
确定好边界条件：左闭右闭
后序序列最后一个元素是根，通过HashMap找到根节点下标
根节点左边的长度为lenOfLeft，那么先序序列和后序序列的前lenOfLeft为根节点的左子树

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null)
            return null;
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        // [start, end - 1]左闭右闭
        return dfs(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    private TreeNode dfs(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) 
            return null;
        // 找到postorder最后一个元素的下标，也就是根节点
        int rootValue = postorder[postEnd];
        // 找到inorder中根节点的位置
        int rootIdx = map.get(rootValue);
        // 构造树节点
        TreeNode root = new TreeNode(rootValue);
        // 根据inorder切割左子树的大小，那么剩下的就是右子树
        int lenOfLeft = rootIdx - inStart;
        // 按照根节点切割成左子树和右子树
        root.left = dfs(inorder, inStart, rootIdx - 1, postorder, postStart, postStart + lenOfLeft - 1);
        root.right = dfs(inorder, rootIdx + 1, inEnd, postorder, postStart + lenOfLeft, postEnd - 1);
        return root;
    }
}

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

注意：int lenOfLeft = rootIdx - inStart; ！！！！！！！！

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int length = inorder.length;
        for (int i = 0; i < length; ++i)
            map.put(inorder[i], i);
        // [)左闭右开
        return dfs(inorder, 0, length, preorder, 0, length);
    }
    private TreeNode dfs(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        if (inStart >= inEnd || preStart >= preEnd)
            return null;
        // 找到根节点
        int rootVal = preorder[preStart];
        int rootIdx = map.get(rootVal);
        // 中序遍历中根节点左边的长度
        int lenOfLeft = rootIdx - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = dfs(inorder, inStart, rootIdx, preorder, preStart + 1, preStart + 1 + lenOfLeft);
        root.right = dfs(inorder, rootIdx + 1, inEnd, preorder, preStart + 1 + lenOfLeft, preEnd);
        return root;
    }
}

:star:654. 最大二叉树

方法一：DFS

思路同106. 从中序与后序遍历序列构造二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(0, nums.length, nums);
    }
    private TreeNode dfs(int start, int end, int[] nums) {
        if (start >= end)
            return null;
        int index = start;
        int maxValue = nums[start];
        for (int i = start; i < end; ++i) {
            if (maxValue < nums[i]) {
                maxValue = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(maxValue);
        root.left = dfs(start, index, nums);
        root.right = dfs(index + 1, end, nums);
        return root;
    }
}

617. 合并二叉树

解题思路：当树1当前节点的左子树或右子树为空，而树2当前节点左子树或右子树不为空时：使用parentQueue存储树1树2的当前节点parent1，parent2，在遍历到下一层时，使用parent1来指向parent2的左子树或者右子树。

Debug：如果cur1左子树为空，cur2左子树不为空，将cur1,cur2加入trashQueue；同理右子树。如果cur1左右子树都为空，cur2左右子树都不为空，将cur1,cur2加入parentQueue两次！！不然之后poll的时候空指针！！

:warning:方法二：DFS

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null)
            return root2;
        if (root2 == null)
            return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

700. 二叉搜索树中的搜索

方法一：DFS

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            }
            else if (cur.val < val) {
                cur = cur.right;
            }
            else {
                cur = cur.left;
            }
        }
        return null;
    }
}

:star:98. 验证二叉搜索树

方法一：中序遍历

中序遍历二叉搜索树应该是升序的，只需要一个记录上一个节点的值的遍历preVal，并与当前节点比较，如果当前节点的值小于等于preVal(cur.val应该严格>preVal不能等于)，则返回false;否则，遍历完所有节点返回true。

假设树有n个节点

时间复杂度：遍历所有节点，\(O(n)\)

空间复杂度：和使用的栈相关，在最坏情况(每个节点都只有一个子节点)下，树的高度为n，都需要压栈，所以为\(O(n)\)

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        long preVal = Long.MIN_VALUE;
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur.val <= preVal)
                return false;
            preVal = cur.val;
            cur = cur.right; 
        }
        return true;
    }
}

:war:方法二：递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        return dfs(TreeNode root, long.MIN_VALUE, long.MAX_VALUE)
    }

    public boolean dfs(TreeNode root, long pre, long post) {
        if (root == null)
            return true;
        if (root.val <= pre || root.val >= post)
            return false;

        return dfs(root.left, pre, root.val) && dfs(root.right, root.val, post);
    }

}

方法三：Morris中序遍历

Morris遍历利用叶子节点的左右空指针，实现空间开销的极限缩减。

morris遍历的实现原则

记作当前节点为cur。

如果cur无左孩子，cur向右移动（cur=cur.right）
如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

实现以上的原则，即实现了morris遍历。

morris遍历的实质

建立一种机制，对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次

Morris中序遍历

如果可以到达一个节点两次(有左子树)，第二次访问
如果可以到达一个节点一次(无左子树)，直接访问

举个例子

从根节点5开始遍历，令cur = 根节点5，找到mostRight为节点1
节点1的右子树为空，将节点1的右子树指向节点5，并让cur移动到左子树(节点1)
开始遍历节点1，由于节点一无左子树，直接访问，比较节点一与preValue(初始化为最小值)，

1 < Long.MIN_VALUE，将节点1的val赋值给preValue
将cur(1)移动到右子树，此时cur为之前访问过的根节点5，继续找到cur(5)左子树的最右节点1，发现节点1的右子树为当前节点cur(5)，将节点1的右子树还原为空
此时是第二次到达节点5，比较节点5与preValue(1)，并将5赋值给preValue，cur向右子树移动，此时cur到达节点4
找到cur(4)左子树的最右节点3，将节点3的右子树指向cur(4)，cur向左子树移动，此时cur到达节点3
由于节点3无左子树，直接比较节点3与preValue(5)的值，3<5，返回false。

可以发现中序遍历的顺序是：15346

Morris中序遍历到达的节点顺序是：5154346，其中5和4有左子树，在到底5和4的第二次时作比较。

class Solution {
    public boolean isValidBST(TreeNode root) {
        TreeNode cur = root, mostRight = null;
        long preValue = Long.MIN_VALUE;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) 
                    mostRight = mostRight.right;
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else if (mostRight.right == cur) {
                    mostRight.right = null;
                }
            }
            if (cur.val <= preValue) 
                return false;
            preValue = cur.val;
            cur = cur.right;
        }
        return true;
    }
}

时间复杂度：遍历所有节点，\(O(n)\)

空间复杂度：Morris遍历利用叶子节点的左右空指针，实现空间开销的极限缩减，\(O(1)\)

530. 二叉搜索树的最小绝对差

方法一：中序遍历

使用中序遍历二叉搜索树得到的结果是升序的。

:star::warning:方法二：双指针

双指针的思想真的很重要！！！

初始化全局变量：pre节点初始化为空；diff存储相邻节点差值，初始化为整型最大值
中序遍历过程：第一次遍历，pre是空的，还没遇到第二个节点也就没有相邻节点之间的差值；
把当前节点(root)赋给pre，那么下一个root就是中序遍历顺序pre的下一个节点

class Solution {
    TreeNode pre;
    int diff = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return diff;
    }
    private void dfs(TreeNode root) {
        if (root == null)
            return;
        dfs(root.left);
        if (pre != null)
            diff = Math.min(diff, root.val - pre.val);
        pre = root; 
        dfs(root.right);
    }
}

501. 二叉搜索树中的众数

老样子，中序遍历

遍历的过程

if (preVal == cur.val) {
	++counter;
}
else {
	counter = 1;
}
if (!modes.contains(cur.val) && counter == maxCounter) {
	modes.add(cur.val);
}

if (counter > maxCounter) {
    maxCounter = counter;
    modes.removeAll(modes);
    modes.add(cur.val);
}
preVal = cur.val;
cur = cur.right;

236. 二叉树的最近公共祖先

方法一：用HashMap存储所有父节点，用HashSet标记是否访问过；从p开始向上遍历，并标记访问过的父节点，再从q开始向上遍历，如果当前节点被访问过，那么这个节点就是最近公共祖先。

注意：对于p，先设置visisted，再向上移；对于q，先判断当前节点是不是已经被visited，再向上移。如果p,q任意一者先向上移再操作，都会导致在，p或q是最近公共节点时，返回的却是p或q的父节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        Set<TreeNode> visited = new HashSet<>();
        dfs(root, map);
        while (p != null) {
            visited.add(p);
            p = map.get(p);
        }
        while (q != null) {
            if (visited.contains(q)) {
                return q;
            }
            q = map.get(q);
        }
        return root;
    }
    public void dfs(TreeNode root, Map<TreeNode, TreeNode> map) {
        if (root == null)
            return;
        if (root.left != null) {
            map.put(root.left, root);
        }
        if (root.right != null) {
            map.put(root.right, root);
        }
        dfs(root.left, map);
        dfs(root.right, map);
    }
}

:warning:方法二：DFS

题解

可以不判断非p,q的叶节点

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }
    public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q)
            return root;
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if (left == null)
            return right;
        if (right == null) 
            return left;
        return root;
    }
}

235. 二叉搜索树的最近公共祖先

递归：考虑三种情况

p,q是root：return root
p,q在root两侧，(p.val < root.val && q.val > root.val) || (p.val > root.val && q.val < root.val)， return root
p,q在root同一侧 (p.val < root && q.val < root.val) || (p.val > root.val && q.val > root.val)
1. p.val < root && q.val < root.val: return dfs(left, p, q)
2. p.val > root.val && q.val > root.val: return dfs(right, p, q)

方法一：DFS

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root.val > p.val && root.val > q.val) 
            return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);        
        return root;
    }
}

701. 二叉搜索树中的插入操作

要点是：如何记录要插入节点的父节点

方法一：栈

从根节点开始遍历，用栈存储每个遍历过的节点，大于向右小于向左；循环结束，判断插入最后一个被遍历的节点(栈中最顶层节点)，判断大于小于，插入，结束。
遍历过程把所有元素放进栈，空节点跳出循环后，栈顶元素就是要插入节点的父节点

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            if (val < cur.val) {
                cur = cur.left;
            }
            else {
                cur = cur.right;
            }
        }
        cur = stack.pop();
        TreeNode newNode = new TreeNode(val);
        if (cur.val > val) {
            cur.left =  newNode;
        } 
        else {
            cur.right = newNode;
        }
        return root;
    }
}

方法二：双指针

用pre指针指向上一个节点，有两个要注意的地方

初始化pre指针时，不能初始化为null，如果根节点没有左子树，而要插入的节点小于根节点，要插入的节点会成为根节点的左子树，这种情况判断一次就会跳出while循环，此时pre还是null，所以要把pre初始化为根节点
在while循环中，用pre=cur记录cur的上一个节点，但是，最后cur等于空的时候，pre再记录cur就没有意义了，所以加上if (cur != null)判断条件

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode res = new TreeNode(val);
        if (root == null)
            return res;
        TreeNode cur = root, pre = root;
        while (cur != null) {
            if (cur.val > val)
                cur = cur.left;
            else if (cur.val < val)
                cur= cur.right;
            if (cur != null)
                pre = cur;
        }
        if (val > pre.val)
            pre.right = res;
        else  
            pre.left = res;
        return root;
    }
}

方法三：DFS

当时想出来了，但是卡在怎么插入这个点上，其实这里已经用root.left或者root.right来接收 new TreeNode(val)了。==构造树==！！！

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

x450. 删除二叉搜索树中的节点

解题思路：

如果目标节点大于当前节点值，则去右子树中删除；
如果目标节点小于当前节点值，则去左子树中删除；
如果目标节点就是当前节点，分为以下三种情况：
1. 其无左子：其右子顶替其位置，删除了该节点；
2. 其无右子：其左子顶替其位置，删除了该节点；
3. 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。

写了快100行，重构一下代码。。

方法一：迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;
        TreeNode cur = root, pre = root;
        while (cur != null) {
            if (cur.val == key) {
                if (cur.left == null && cur.right == null) { // 叶子节点
                    if (pre.val < key) 
                        pre.right = null;
                    else 
                        pre.left = null;
                }
                else {
                    if (cur.left !=  null && cur.right != null) {
                     // 找到要删除节点右子树上的最左节点，再把要删除节点左子树挂上去
                        TreeNode left = cur.left, right = cur.right;
                        cur = cur.right;
                        while (cur.left != null) 
                            cur = cur.left;
                        cur.left = left;
                        if (pre.val < key) 
                            pre.right = right;
                        else 
                            pre.left = right;                        
                    }
                    else if (cur.left == null && cur.right != null) {
                        TreeNode right = cur.right;
                        if (pre.val < key)
                            pre.right = right;
                        else 
                            pre.left = right;
                    }
                    else if (cur.left != null && cur.right == null) {
                        TreeNode left = cur.left;
                        if (pre.val < key)
                            pre.right = left;
                        else 
                            pre.left = left;
                    }
                }
                break;
            }
            else if (cur.val < key) {
                pre = cur;
                cur = cur.right;
            }
            else {
                pre = cur;
                cur = cur.left;
            }
        }
        if (root.val == key) {
            return root.left == null ? root.right : root.left;            
        }
        return root;
    }
}

:star:方法二：DFS

注意代码注释部分是完全冗余的！

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;
        if (key < root.val)
            root.left = deleteNode(root.left, key);
        else if (key > root.val)
            root.right = deleteNode(root.right, key);
        else { //(key == root.val) {
            if (root.left == null && root.right == null) {
                return null;
            }
            else if (root.left == null && root.right != null) {
                return root.right;
            }
            else if (root.left != null && root.right == null) {
                return root.left;
            }
            else {
                TreeNode cur = root.right;
                while (cur.left != null) 
                    cur = cur.left;
                cur.left = root.left;
                return root.right;
            }
        }
        // if (root.val == key) {
        //     if (root.left == null && root.right == null)
        //         return null;
        //     else {
        //         return root.left == null ? root.right : root.left;
        //     }
        // }
        return root;
    }
}

:warning:669. 修剪二叉搜索树

借上一题的思路直接速通了

108. 将有序数组转换为二叉搜索树

方法一：二分DFS[左闭右闭]

方法二：DFS[左闭右开)]，开区间元素在record的数值要--，闭区间元素在record的位置要++，开区间元素和闭区间元素都为‘a’，所以s的下标1以‘b’开始的子串“ba”也是变位词！

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> index = new LinkedList<>();
        if (s.length() < p.length())
            return index;
        int[] record = new int[26];
        for (int i = 0; i < p.length(); ++i) {
            ++record[p.charAt(i) - 'a'];
            --record[s.charAt(i) - 'a'];
        }
        if (areZeros(record)) {
            index.add(0);
        }
        for (int i = p.length(); i < s.length(); ++i) {
            ++record[s.charAt(i - p.length()) - 'a'];
            --record[s.charAt(i) - 'a'];
            if (areZeros(record)) {
                index.add(i - p.length() + 1);
            }
        }
        return index;
    }
    private boolean areZeros(int[] record) {
        for (int element : record)
            if (element != 0)
                return false;
        return true;
    }
}

1208. 尽可能使字符串相等:warning:

方法一：滑动窗口

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int[] diff = new int[n];
        for (int i = 0; i < n; ++i) {
            diff[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int res = 0, start = 0, sum = 0;
        for (int end = 0; end < n; ++end) {
            sum += diff[end];
            while (maxCost < sum) {
                sum -= diff[start++];
            }
            res = Math.max(res, end - start + 1);
        }
        return res;
    }
}

String补充知识

String与char数组，StringBuilder之间相互转换

将String转换为char数组：

1 2	`codeString str = "hello"; char[] charArray = str.toCharArray();`

将char数组转换为String：

1 2	`codechar[] charArray = {'h', 'e', 'l', 'l', 'o'}; String str = new String(charArray);`

将String转换为StringBuilder：

//1.
codeString str = "hello";
StringBuilder sb = new StringBuilder(str);
//2.
StringBuilder sb = new StringBuilder();
sb.append(str);

将StringBuilder转换为String：

1
2
3

codeStringBuilder sb = new StringBuilder();
sb.append("hello");
String str = sb.toString();

将char数组转换为StringBuilder：

1
2
3

codechar[] charArray = {'h', 'e', 'l', 'l', 'o'};
StringBuilder sb = new StringBuilder();
sb.append(charArray);

将StringBuilder转换为char数组：

1
2
3

codeStringBuilder sb = new StringBuilder("hello");
char[] charArray = new char[sb.length()];
sb.getChars(0, sb.length(), charArray, 0);

需要注意的是，在将String转换为char数组或char时，如果字符串为空，或者字符串中的字符数量为0，则可能会导致越界异常或其他异常。因此，在进行这些转换操作时，需要进行有效性检查和异常处理。

单个字符char转换为String

在Java中，将单个字符（char）转换为字符串（String）有以下两种方法：

1.使用字符串连接符

您可以使用字符串连接符"+"来连接一个空字符串和单个字符，从而将其转换为字符串。例如：

1 2	`arduinoCopy codechar c = 'a'; String s = "" + c;`

在上面的代码中，首先创建一个空字符串，然后使用字符串连接符将其与字符"c"连接起来，从而将字符"c"转换为字符串。现在，字符串s将包含字符"c"的字符串。

2.使用String.valueOf()方法

另一种将单个字符转换为字符串的方法是使用String类的valueOf()方法。例如：

1 2	`arduinoCopy codechar c = 'a'; String s = String.valueOf(c);`

在上面的代码中，将字符"c"传递给valueOf()方法，并将返回的字符串分配给变量s。

无论使用哪种方法，您都可以将单个字符转换为字符串，从而可以对其进行各种字符串操作。

StringBuilder的append可以是char或者String

StringBuilder的append()方法可以接受char类型和String类型的参数。append()方法的作用是在StringBuilder对象的末尾追加指定的字符序列，这可以是char、String、StringBuilder或其他CharSequence实例。

以下是使用StringBuilder的append()方法追加char和String类型参数的示例代码：

追加char类型参数：

1
2
3

codeStringBuilder sb = new StringBuilder();
char c = 'a';
sb.append(c);

追加String类型参数：

1
2
3

codeStringBuilder sb = new StringBuilder();
String str = "hello";
sb.append(str);

需要注意的是，使用append()方法追加char类型参数时，会自动将char类型转换为String类型。因此，如果需要在StringBuilder中追加一个char类型的字符，可以直接使用append()方法，而不需要先将其转换为String类型。

KMP算法

生成next数组讲得很透彻

Array

704. 二分查找

方法一：左闭右开

区间：[left, right)
初始化：right = nums.length
while循环终止条件应为left < right（右开，right不能等于left）
当nums[mid] < target时，nums[0]~nums[mid]都小于target，此时有效的有边界是mid - 1，又因为右边界是开区间，所以另right = mid
时间复杂度：\(O(logn)\)，由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是\(O(logn)\)，其中 n 是数组的长度
空间复杂度：\(O(1)\)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        // [left, right)
        while(left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else 
                right = mid;
        }
        return -1;
    }
}

方法二：左闭右闭

区间：[left, right]
初始化：right = nums.length - 1
while循环终止条件应为left <= right
当nums[mid] < target时，nums[0]~nums[mid]都小于target，另right = mid - 1
时间复杂度：\(O(logn)\)，由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是\(O(logn)\)，其中 n 是数组的长度
空间复杂度：\(O(1)\)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (nums[mid] > target) 
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else 
                return mid;
        }
        return -1;
    }
}

27. 移除元素

方法一：暴力

每当发现一个数相等，那么从当前数组的下一个数开始，全部往前移一位。
注意：因为移位后，下一个要访问的数组元素j会到当前i的位置，然后for循环结束i自增，会错过访j，所以移位后要--i。
时间复杂度：\(O(n^2)\)
空间复杂度：\(O(1)\)

class Solution {
    public int removeElement(int[] nums, int val) {
        int newLen = nums.length;
        if (newLen == 0)
            return 0;
        for (int i = 0; i < newLen; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < newLen; j++) {
                    nums[j - 1] = nums[j];
                }
                --newLen;
                --i;
            }
         }

        return newLen;

    }
}

方法二：双指针

初始化慢指针为0
for循环遍历快指针，当nums[fast] != val时，令nums[slow] = nums[fast]，slow指针往后移。也就是说，如果快指针找到了val，那么慢指针停在val位置，之后快指针遍历到非val的位置时，将该非val数据覆盖到慢指针的指向数组位置的数据。
最后返回慢指针(慢指针大小代表新数组的大小)
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; ++fast) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                ++slow;
            }
        }
        return slow;
    }
}

方法三：相向双指针

避免了需要保留的元素的重复赋值操作。

初始化：left=0, right=nums.length-1，左闭右闭区间，所以while语句的执行条件是

left <= right(如果没有等于，left会少后移一次)
循环：当nums[left]不等于val时，left指针后移；当nums[left]等于val时，将nums[right]赋值给nums[left]，right指针前移；如果赋值过来的元素恰好也等于val，可以继续把右指针 right指向的元素的值赋值过来，直到左指针指向的元素的值不等于 val为止。
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        // [left, right]
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                --right;
            }
            else {
                ++left;
            }
        }
        return left;
    }
}

977. 有序数组的平方

双指针

left,right指针指向数组两端，将较大的平方数放入result数组里。

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

209. 长度最小的子数组

nums[++i]先执行自增操作还是数组寻址操作?

在Java中，表达式nums[++i]中的++i是先自增还是先寻址是有规定的。按照Java的运算符优先级规定，前置自增运算符++i的优先级高于数组下标运算符[]，因此在执行这个表达式时，先进行++i自增运算，然后再进行数组下标运算，即先自增再寻址。

因此，nums[++i]相当于先将变量i自增1，然后使用自增后的i作为数组下标去访问nums数组中的元素。如果i的初始值为0，那么nums[++i]将访问nums[1]位置上的元素，而不是nums[0]。如果数组nums越界，将会抛出ArrayIndexOutOfBoundsException异常。

nums[i++]先执行自增操作还是数组寻址操作?

在这种情况下，nums[i++]实际上会先执行数组寻址操作，然后再对i进行自增操作。这是因为数组寻址操作的优先级比自增操作的优先级高。

具体来说，这个表达式会先使用i的当前值来计算nums数组中第i个元素的地址，然后将地址作为结果返回，接着才会将i的值加1。

int a = ++i 是先赋值还是先自增

这行代码会先自增变量 i 的值，然后将自增后的结果赋值给变量 a。所以，变量 a 的值等于自增后的变量 i 的值。这个过程中，变量 i 的值会被修改，而变量 a 的值则是这个修改后的值。

可以将这行代码拆分成两步：

i = i + 1； // 自增 i 的值
a = i； // 将自增后的 i 的值赋值给 a

所以，最终变量 a 的值等于自增后的变量 i 的值。

int a = i++ 是先赋值还是先自增

这行代码会先将变量 i 的值赋值给变量 a，然后再将变量 i 的值自增。所以，变量 a 的值等于变量 i 的值，而变量 i 的值会被自增。

可以将这行代码拆分成两步：

a = i； // 将 i 的值赋值给 a
i = i + 1； // 自增 i 的值

所以，最终变量 a 的值等于变量 i 的初始值，而变量 i 的值则是初始值加一。

while(--index) 先-- 后比较index>0

int index = 2;
while (--index > 0) {
    System.out.print(index);
}

stdout

while(index--) 先比较后--

int index = 2;
while (index-- > 0) {
    System.out.print(index);
}

stdout

System.out.print(--index) 先-- 后打印

int index = 2;
while (index > 0) {
    System.out.print(--index);
}

stdout

滑动窗口

注意：为了确保有些案例，sum一直小于target，最后输出判断：如果

result == Integer.MAX_VALUE，就输出0。
result记录最小的长度
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int counter = 0, result = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            ++counter;
            sum += nums[i];
            while (sum >= target) {
                result = Math.min(result, counter);
                sum -= nums[i - (--counter)];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

59. 螺旋矩阵 II

遍历顺序：从左到右(左闭右开)，从上到下(上闭下开)，从右到左(右闭左开)，从下到上(下闭上开)
思路见代码注释部分
时间复杂度：\(O(n^2)\)
空间复杂度：\(O(1)\)

class Solution {
    public int[][] generateMatrix(int n) {
        // 用笔画一个n=5的矩阵作为例子
        // 遍历顺序：从左到右(左闭右开)，从上到下(上闭下开)，从右到左(右闭左开)，从下到上(下闭上开)
        // 建立n行n列的矩阵
        int[][] matrix = new int[n][n];
        // 遍历次数
        int traverseTime = n / 2;
        int i, j;
        // 写入数组的数
        int data = 1;
        // cur:当前遍历伦茨
        for (int cur = 0; cur < traverseTime; ++cur) {
            // 从左到右(左闭右开)
            for (j = cur; j < n - cur - 1; ++j) {
                matrix[cur][j] = data++;
            }
            // 从上到下(上闭下开)
            for (i = cur; i < n - cur - 1; ++i) {
                matrix[i][j] = data++;
            }
            // 从右到左(右闭左开)
            for (; j > cur; --j) {
                matrix[i][j] = data++;
            }
            // 从下到上(下闭上开)
            for (; i > cur; --i) {
                matrix[i][j] = data++;
            }
            // debug
            // for (int a = 0; a < n; ++a) {
            //     for (int b = 0; b < n; ++b) {
            //         System.out.print(matrix[a][b]);
            //     }
            // }
        }
        if (n % 2 == 1)
            matrix[traverseTime][traverseTime] = n * n;
        return matrix;
    }
}

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

方法一：暴力

class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; ++i) {
            sum += nums[i];
        }
        return sum;
    }
}

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

方法二：前缀和

建立一个长度为n+1的数组preSum
初始化preSum[0] = 0;
preSum[i]表示数组nums从下标0到下标i-1的和
区间[left,right]的和为preSum[right + 1] - preSum[left];

preSum[right + 1]表示数组从下标0到right的和，preSum[left]表示数组从下标0到left-1的和
将前缀和数组preSum的长度设为n+1的目标是为了方便计算sumRange(left, right)时，不需要对left=0的情况做特殊处理

class NumArray {
    private int[] preSum;
    public NumArray(int[] nums) {
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; ++i) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

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

前缀和：前缀和数组为n，需要对left=0时做特殊处理

class NumArray {
    private int[] preSum;
    public NumArray(int[] nums) {
        preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < preSum.length; ++i) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        if (left == 0) {
            return preSum[right];
        }
        return preSum[right] - preSum[left - 1];
    }
}

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

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

方法一：前缀和:warning:

需要重刷！

题解

class NumMatrix {
    int[][] preSum;
    public NumMatrix(int[][] matrix) {
        preSum = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 1; i <= matrix.length; ++i) {
            for (int j = 1; j <= matrix[0].length; ++j) {
                preSum[i][j] = matrix[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
            }
        }        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
    }
}

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

1109. 航班预订统计

LinkedList

203. 移除链表元素

解题思路：在面对链表、树有关创建、删除操作，使用dummyHead！能省去不少边界判定的功夫。

初始化：dummyHead指向head，dummyHead赋值给pre，head赋值给cur
当cur的值等于所求val，pre指向cur的下一个节点
当cur的值不等于val，pre移动到cur，cur往后移一位
返回dummyHead的下一个节点。

707. 设计链表

注意事项：DummyHead + size

206. 反转链表

用笔模拟一下指针pre，cur，next的过程

时间复杂度：\(O(n^2)\)
空间复杂度：\(O(1)\)

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

注意要点：用纸和笔模拟一下指针pre，cur，next的过程，记得创建dummyHead

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

19. 删除链表的倒数第 N 个结点

使用dummyHead，从dummyHead，找到倒数第N个节点的前一个节点node，需要走链表长度size - N步，即可把node指向下一个节点的下一个节点即可完成删除操作。
但是链表的长度是未知的，可以先遍历一遍链表的长度，求出size，再走size-N步完成删除操作。
也可以使用快慢指针，fast与slow的起始点都为dummyHead，fast先走N步，再让fast与slow一起右移，当fast走到最后一个节点时(fast.next == null时)，slow右移了size - N步，到达倒数第N个节点的上一个节点，即可完成删除操作。
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

面试题 02.07. 链表相交

方法一：HashSet

用指针A,B分别指向两个链表头
开始循环，循环的终止条件为A,B都为空，每次循环先将A,B指向的节点放入HashSet，再向后移
当遍历到某个已经存入HashSet的节点时，这个节点就是相交节点；否则没有相交节点
时间复杂度：\(O(m + n)\)，其中m，n分别为两个链表的长度
空间复杂度：\(O(m + n)\)

方法二：双指针

解题思路：A,B分别指向headA,headB，如果有公共节点，设公共节点长度为c，链表A和B长度分别为a,b。向右遍历，如何为空，则指向另一个链表的头。如果两个链表相交，则A向右移动了a+c+b步，B向右移动了b+c+a时相交，返回A；如果两个链表不相交，则A向右移动了a+b步，B向右移动了b+a步，都为空，退出循环返回null。

用指针A,B分别指向两个链表头headA,headB
开始循环，循环的条件是A和B不都为空，如果A为空，则A指向headB，否则向后移；如果B为空，则B指向headA，否则向后移
开始循环，循环的终止条件为A,B都为空，每次循环先将A,B指向的节点放入HashSet，再向后移
当遍历到某个已经存入HashSet的节点时，这个节点就是相交节点；否则没有相交节点
时间复杂度：\(O(m + n)\)，其中m，n分别为两个链表的长度
空间复杂度：\(O(m + n)\)

一个错误代码实例

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA, pB = headB;
        while (pA != null || pB != null) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
            if (pA == pB)
                return pA;
        }
        return null;
    }
}

错误如下，当两个链表只有公共部分节点1时，上述代码没有先判断，先向右移，结果指向A,B都为空，返回空。

所以解决方案是把判断AB相等的语句放在指针移动上面

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA, pB = headB;
        while (pA != null || pB != null) {
            if (pA == pB)
                return pA;
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return null;
    }

成功

优化

当A,B只有公共部分时，直接返回结果
当A,B有自己的部分也相交时
1. 当A,B公共部分前面节点数量相同时，遍历到相交节点直接返回结果
2. 当A,B公共部分前面节点数量不同时，遍历a+b+c步也会相交，返回结果
当A,B不相交时，遍历完a+ 1(null) + b + 1(null) 步后，A和B都为null，返回的A为null，表示不相交

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

142. 环形链表 II

解题思路：快慢指针，慢指针走一步，快指针走两步，如果有环，快指针总能在环中追上慢指针。当快指针和慢指针指向同一节点时，把快节点指向头节点，慢节点不动，快慢指针一起走，再次相遇时，指向的节点就是入环的第一个节点。

时间复杂度：\(O(m + n)\)，其中m，n分别为两个链表的长度
空间复杂度：\(O(m + n)\)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) 
            return null;
        ListNode fast = head.next.next, slow = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
            return fast;
            }
        }
        return null;
    }
}

剑指 Offer II 026. 重排链表

方法一：翻转合并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode cur = head, fast = head.next;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            cur = cur.next;
        }
        ListNode mid = cur;
        fast = mid.next;
        mid.next = null;
        fast = reverse(fast);
        cur = head;
        while (fast != null) {
            ListNode next1 = cur.next, next2 = fast.next;
            cur.next = fast;
            fast.next = next1;
            cur = next1;
            fast = next2;
        }
    }

    private ListNode reverse(ListNode cur) {
        ListNode pre = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

剑指 Offer II 025. 链表中的两数相加

方法一：翻转三次

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode res = addReversedList(l1, l2);
        return reverse(res);

    }

    private ListNode addReversedList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0, sum = 0;
        while (l1 != null || l2 != null) {
            l1 = l1 == null ? null : l1;
            l2 = l2 == null ? null : l2;
            sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            ListNode newNode = new ListNode(sum);
            cur.next = newNode;
            cur = cur.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (carry == 1) {
            ListNode newNode = new ListNode(1);
            cur.next = newNode;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode cur) {
        ListNode pre = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

方法二：翻转两次(最后一次不需要翻转)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode res = addReversedList(l1, l2);
        return res;
    }

    private ListNode addReversedList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0, sum = 0;
        while (l1 != null || l2 != null) {
            l1 = l1 == null ? null : l1;
            l2 = l2 == null ? null : l2;
            sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            ListNode newNode = new ListNode(sum);
            cur = dummy.next;
            dummy.next = newNode;
            newNode.next = cur;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (carry == 1) {
            cur = dummy.next;
            ListNode newNode = new ListNode(1);
            dummy.next = newNode;
            newNode.next = cur;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode cur) {
        ListNode pre = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

Hash Table

242. 有效的字母异位词

方法一：双HashMap记录词频

判断s与t的长度，若不相等，则一定不是字母异位词
建立两个HashMap<Character, Integer>
遍历字符串，将每个字符存入map中，并将值+1
如果map1与map2的size不相等，则一定不是字母异位词
遍历map1(我遍历的是字符串)，get字符串s，t的每一个字符出现了的次数，判断是否相同，如果不同，则一定不是字母异位词。
时间复杂度：\(O(n)\)，其中n为第一个字符串的长度
空间复杂度：\(O(1)\)

class Solution {
    public boolean isAnagram(String s, String t) {
        int len = s.length();
        if (len != t.length())
            return false; 
        Map<Character, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            map1.put(sChar, map1.getOrDefault(sChar, 0) + 1);
            map2.put(tChar, map2.getOrDefault(tChar, 0) + 1);
        }

        for (int i = 0; i < len; ++i) {
            int sSize = map1.get(s.charAt(i));
            int tSize = map2.getOrDefault(s.charAt(i), 0);
            if (sSize != tSize) {
                return false;
            }
        }
        return true;
    }
}

方法二：数组

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。
定一个数组record，大小为26 ，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。
遍历第一个字符串s时，只需要将s.charAt(i) - ‘a’所在的元素+1，这样统计了字符串s中每个字符出现的次数。
同样，遍历第二个字符串t时，只需要将t.charAt(i) - ‘a’所在的元素-1。
如果record全部元素为0，那么s和t是字母异位词；否则不是。
时间复杂度：\(O(n)\)，其中n为第一个字符串的长度
空间复杂度：\(O(1)\)，只使用了常数大小的辅助数组。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        int[] record = new int[26];
        for (int i = 0; i < s.length(); ++i)  {
            ++record[s.charAt(i) - 'a'];
            --record[t.charAt(i) - 'a'];
        }
        for (int i = 0; i < 26; ++i) 
            if (record[i] != 0)
                return false;
        return true;
    }
}

349. 两个数组的交集

解题思路：双HashSet

首先使用一个HashSet命名为set，记录第一个数组中不包含重复的所有元素
再用一个HashSet命名为intersection，遍历第二个数组，如果第二个数组中的元素在set中，则加入intersection中
最后将intersection转换为数组，并返回

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> intersection = new HashSet<>();
        for (int i = 0; i < nums1.length; ++i)
            set.add(nums1[i]);
        for (int i = 0; i < nums2.length; ++i) 
            if (set.contains(nums2[i]))
                intersection.add(nums2[i]);
        int[] result  = new int[intersection.size()];
        int i = 0;
        for (int element : intersection) {
            result[i++] = element;
        }
        return result;
    }
}

202. 快乐数

求和的过程中，sum会重复出现，用HashSet记录每一次求和，如果有重复，那么必定不是快乐数。

注意：sum += (n % 10) * (n % 10);+=的优先级高于%。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = getSum(n);
        }
        return n == 1;
    }

    private int getSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
}

1. 两数之和

方法一：暴力

注意初始化int数组：new int[]{i, j};

时间复杂度：\(O(n^2)\)，其中n为第一个字符串的长度
空间复杂度：\(O(1)\)，只使用了常数大小的辅助数组。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j  < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return result;
    }
}

方法二：HashMap

解题思路：

建立一个HashMap，key为数组的值，value为数组索引
遍历一遍，每次遍历判断哈希表中是否存在key为target-nums[i]，如果有，则这个key对应的value与i即为所求
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i])) 
                return new int[]{map.get(target - nums[i]), i};
            map.put(nums[i], i);
        }
        return new int[2];
    }
}

454. 四数相加 II

解题思路：

用HashMap用两层循环记录前两个数组每个元素之和为key，和出现的次数为value
再两次循环后两个数组，如果map.containsKey(- i - j)，那么- i - j与当前i + j之和为0，即为本题所求，则把result加上和为- i - j的数量
时间复杂度：\(O(n^2)\)，两层循环
空间复杂度：\(O(n^2)\)，在最坏情况下，前两个数组的元素各不相同，map占n * n

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int result = 0;
        int n = nums1.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                map.put(nums1[i] + nums2[j], map.getOrDefault(nums1[i] + nums2[j], 0) + 1);
            }
        }
        for (int i : nums3) {
            for (int j : nums4) {
                if (map.containsKey(- i - j))
                    result += map.get(- i - j);
            }
        }
        return result;
    }
}

383. 赎金信

解题思路：字母表

如果ransomNote的长度大于magazine的长度，直接返回false
新建一个长度为26的字母表，以及一个HashMap，key为字母-‘a’，value为字母出现的次数，将magazine中的每个字符put进map
遍历ransomNote的所有字符i，如果map中key为字符i的value大于0，那么把这个value减一；如果map中key为字符i的value小于等于0，说明magazine不存在字符i或者字符i的个数小于ransomNote中字符i的个数，那么 ransomNote 能不能由 magazine 里面的字符构成，返回false
时间复杂度：\(O(n)\)，两层循环
空间复杂度：\(O(1)\)，只需要常数大小的辅助空间

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length())
            return false;
        char[] record = new char[26];
        Map< Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < magazine.length(); ++i) {
            int index = magazine.charAt(i) - 'a';
            map.put(index, map.getOrDefault(index, 0) + 1);
        } 
           
        for (int i = 0; i < ransomNote.length(); ++i) {
            int index = ransomNote.charAt(i) - 'a';
            if (map.getOrDefault(index, 0) > 0) {
                map.put(index, map.get(index) - 1);
            }
            else 
                return false;
        }
        return true;
    }
}

x15. 三数之和

题目要求：

nums[i],nums[j],nums[k]中i,j,k各不相同
输出的nums[i],nums[j],nums[k]不能重复，如果结果集合中有{1,2,3}了，就不能再加入一个{1,2,3}
不能有重复的三元组，但三元组内的元素是可以重复的！{0,0,0},{-1,-1,2}是允许的

方法一：暴力

注意：{1，2，3}和{3， 2， 1}是不同的元素！

set.add(Arrays.asList(1, 2, 3));
set.add(Arrays.asList(3, 1, 2));
[1, 2, 3]
[3, 1, 2]

找到符合的元素先排序，如何hashset中不存在再加入list中。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();
        List<List<Integer>> list = new LinkedList<>();
        for (int i = 0; i < nums.length - 2; ++i) {
            for (int j = i + 1; j  <nums.length - 1; ++j) {
                for (int k = j + 1; k < nums.length; ++k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(temp);
                        if (!set.contains(temp)) {
                            set.add(temp);
                            list.add(temp);
                        }
                    }
                }
            }
        }
        return list;
    }
}

超时

方法二：排序 + 双指针

去重思路
边界判断
时间复杂度：\(O(n^2)\)，两层循环
空间复杂度：\(O(1)\)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);
        // window: [nums[i], left, right]
        for (int i = 0; i < nums.length - 2; ++i) {
            if (nums[i] > 0)
                break;
            // 去重
            // 为什么不是nums[i] = nums[i + 1]?
            // 比如{-1，-1，2}
            // 如果是nums[i] = nums[i + 1]，那么{-1，-1，2}这个结果不会被选中
            if (i > 0 && nums[i] == nums[i - 1]) 
                continue;
            int left = i + 1, right = nums.length - 1;
            // 只能选取数组中不同下标的三个数，所以left == right时会使用同一个数，不执行
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0)
                    ++left;
                else if (sum > 0)
                    --right;
                else { // sum == 0
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重
                    // 必须在添加完结果后去重，不然第一次的结果可能无法添加
                    while (right > left && nums[right] == nums[right - 1])
                        --right;
                    while (right > left && nums[left] == nums[left + 1])
                        ++left;
                    // 为什么两个指针都移动？去重之后，只移动一个，结果必定不等于0
                    --right;
                    ++left;
                } 

            }
        }
        return result;

    }
}

18. 四数之和

注意事项：nums[i]的范围，如果4个数都等于\(10^9\)，

那么将大于\(2^{31} - 1= 2147483648 < 2.15 * 10^9\)(int最大的正数)，所以要用long记录四数之和
在三数之和的基础上，再增加一层循环，

区间为[nums[i], nums[left], nums[right], nums[j]]
时间复杂度：\(O(n^3)\)，三层循环
空间复杂度：\(O(n)\)，排序使用了额外的数组存储数组nums的副本

剪枝

第一层循环中，如果最小的四数之和大于target，那么后面的数更大，break

1
2
3

\\ 第一层循环
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 1] > target)
    break;

第二层循环中，如果最大的四数之和小于target，那么前面的数更小，break

1
2
3

\\ 第二层循环
if ((long) nums[i] + nums[j] + nums[j - 1] + nums[j - 2] < target)
    break;

完整代码如下

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new LinkedList<>();
        int length = nums.length;
        if (length < 4)
            return result;
        Arrays.sort(nums);
        // window: [nums[i], nums[left], nums[right], nums[j]]
        for (int i = 0; i < length - 3; ++i) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 1] > target)
                break;
            // 第4个数从尾开始遍历，举例{-1, -1, 0, 2}来确定j > 2这个边界条件
            for (int j = length - 1; j > 2; --j) {
                // 去重，如果使用nums[j] == nums[j - 1]判断，nums[j - 1]属于right的范围
                // 那么{-1，-1，1, 1}这个结果不会被选中
                if (j < length - 1 && nums[j] == nums[j + 1])
                    continue;
                if ((long) nums[i] + nums[j] + nums[j - 1] + nums[j - 2] < target)
                    break;
                int left = i + 1, right = j - 1;
                // 只能选取数组中不同下标的三个数，所以left == right时会使用同一个数，不执行
                while (left < right) {
                    long sum = (long) nums[i] + nums[left] + nums[right] + nums[j];
                    if (sum < target)
                        ++left;
                    else if (sum > target)
                        --right;
                    else { // sum == target
                        result.add(Arrays.asList(nums[i], nums[left], nums[right], nums[j]));
                        while (left < right && nums[left] == nums[left + 1])
                            ++left;
                        while (left < right && nums[right] == nums[right - 1])
                            --right;
                        ++left;
                        --right;
                    }
                }
            }
        }
        return result;
    }
}

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

class RandomizedSet {

    List<Integer> list;
    Map<Integer, Integer> map;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new LinkedList<>();
        map = new HashMap<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val))
            return false;
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val))
            return false;
        int index = map.get(val);
        int lastVal = list.get(list.size() - 1);
        list.set(index, lastVal);
        list.remove(list.size() - 1);
        map.put(lastVal ,index);
        map.remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

剑指 Offer II 031. 最近最少使用缓存

class LRUCache {
    class ListNode {
        int key;
        int val;
        ListNode pre;
        ListNode next;
        public ListNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }
    ListNode head, tail;
    private int capacity;
    Map<Integer, ListNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        moveToTail(key);
        return map.get(key).val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = value;
            map.put(key, node);
            moveToTail(key);
        }
        else { // do not exist
            ListNode node = new ListNode(key, value);
            if (this.capacity != map.size()) { // not full
                insertAtTail(node);
                map.put(key, node);
            }
            else { // full
                ListNode toDelete = head.next;
                delete(toDelete);
                map.remove(toDelete.key);
                insertAtTail(node);
                map.put(key, node);
            }
        }
    }
    public void moveToTail(int key) {
        ListNode node = map.get(key);
        if (node.next == tail)
            return;
        delete(node);
        insertAtTail(node);
    }
    public void delete(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    public void insertAtTail(ListNode node) {
        node.pre = tail.pre;
        node.next = tail;
        node.pre.next = node;
        tail.pre = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Stack and Queue

232. 用栈实现队列

解题思路：使用两个栈，inStack,outStack来实现队列。

push：直接将元素push进inStack

pop：如果outStack不为空，则弹出outStack顶部元素；如果outStack为空，则将inStack中的元素全部弹入inStack，再弹出outStack顶部元素

class MyQueue {
    
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
           pushIntoOut();
        }
        return outStack.pop();

    }
    
    public int peek() {
        if (outStack.isEmpty()) 
            pushIntoOut();
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    public void pushIntoOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

/**
 * 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();
 * boolean param_4 = obj.empty();
 */

225. 用队列实现栈

方法一：单队列

push：直接将元素加入queue

pop()：首先将队列元素移除并重新加入queue.size() - 1次，这样底部的元素就在队列首部了，poll出来即可

peek()：首先将队列元素移除并重新加入queue.size() - 1次，这样底部的元素就在队列首部了，先用result接收queue.peek()，再将这个元素移除并重新加入，最后返回result，peek()操作是不能改变内部数据的！！

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
    }
    
    public int pop() {
        catchBottom();
        return queue.poll();
    }
    
    public int top() {
        catchBottom();
        int result = queue.peek();
        queue.offer(queue.poll());
        return result;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    public void catchBottom() {
        for (int i = 0; i < queue.size() - 1; ++i) {
            queue.offer(queue.poll());
        }
    }
}

优化

在面对大量需要查看顶部元素业务的时候，每次都要重新出队入队n次，不如在push的时候就排好序，

public void push(int x) {
    queue.offer(x);
    for (int i = 0; i < queue.size() - 1; ++i) {
        queue.offer(queue.poll());
    }
}
public int pop() {
    return queue.poll();
}
public int top() {
    return queue.peek();
}

方法二：双队列

push：先在辅助队列supportQueue中加入目标数据，再将主队列queue中的数据全部弹出并加入到supportQueue中，这个时候supportQueue就是先进后出的排列顺序，最后将queue和support交换

class MyStack {

    Queue<Integer> queue, supportQueue;

    public MyStack() {
        queue = new LinkedList<>();
        supportQueue = new LinkedList<>();
    }
    
    public void push(int x) {
        supportQueue.offer(x);
        while (!queue.isEmpty()) {
            supportQueue.offer(queue.poll());
        }
        Queue<Integer> temp = queue;
        queue = supportQueue;
        supportQueue = temp;
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

20. 有效的括号

方法一：HashMap + Stack

注意事项：如果是左括号，直接push进栈

如果是右括号，如果栈为空那么匹配不了；如果右括号和栈顶部的左括号不匹配，也不满足

最后如果栈空，则是有效的括号；否则不是

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put('{', '}');
        map.put('(', ')');
        map.put('[', ']');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (map.containsKey(c))
                stack.push(c);
            else {    
                if (stack.isEmpty() || map.get(stack.pop()) != c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

方法一：StringBuilder

如果当前字符和前一个字符相等，则删除当前字符；否则加入当前字符

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        int index = -1;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (sb.length() == 0 || c != sb.charAt(index)) {
                sb.append(c);
                ++index;
            }
            else {
                sb.deleteCharAt(index);
                --index;
            }
        }
        return sb.toString();
    }
}

150. 逆波兰表达式求值

解题思路：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; ++i) {
            String token = tokens[i];
            if (isNumber(token)) 
                stack.push(Integer.parseInt(token));
            else {
                int b = stack.pop(), a = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a - b);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String s) {
        return !(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));
    }
}

注意事项：

在Java中，==和.equals()都是用于比较两个对象是否相等的操作符。但是它们之间存在着不同的用法和含义。

==用于比较两个对象的引用是否相等，也就是判断这两个对象是否是同一个对象。当比较两个基本数据类型的值时，它们的值相等时返回true；当比较两个引用类型的对象时，如果它们所指向的内存地址相同，也就是它们是同一个对象时，返回true；否则返回false。

.equals()方法用于比较两个对象的内容是否相等。默认情况下，.equals()方法比较的是两个对象的引用是否相等，也就是使用==比较，但是我们可以通过重写.equals()方法来自定义比较规则，比如根据对象的属性值来比较是否相等。

对于字符串类型的变量来说，==和.equals()方法的区别如下：

==比较的是字符串对象的引用是否相等，也就是它们是否指向同一个内存地址。
.equals()方法比较的是字符串对象的内容是否相等，也就是它们包含的字符序列是否相同。

因为Java中字符串是一个特殊的对象类型，为了方便字符串的比较操作，Java中提供了一种特殊的机制，也就是"字符串常量池"，它可以缓存字符串对象，使得多个字符串对象可以共享同一个对象，也就是它们的引用相等。在这种情况下，==操作符会返回true。但是在其他情况下，如果不是使用相同的字符串字面量来创建字符串对象，==操作符会返回false，此时需要使用.equals()方法来进行字符串的内容比较。

239. 滑动窗口最大值

方法一：暴力（超时）

时间复杂度：\(O(kn)\)
空间复杂度：\(O(n)\)，存储结果的数组

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        if (k > n)
            return result;
        // [i, i + k)
        for (int i = 0; i < result.length; ++i) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; ++j) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

方法二：单调队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        int[] result = new int[n];
        result[0] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; ++i) {
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 如果i的左区间在队首元素右边，则要移除队首元素; 用if就可以了(while也行)
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }
}

347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (count > queue.peek()[1]) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            }
            else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; ++i) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}

优先级队列（大根堆、小根堆）

Java中可以使用PriorityQueue类来创建优先级队列，它实现了一个基于优先级堆的无界优先级队列。

要创建一个大根堆，需要使用Comparator.reverseOrder()方法来创建一个反转自然顺序的比较器，示例如下：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(10);
System.out.println(maxHeap.poll()); // 输出10

要创建一个小根堆，只需要使用默认的比较器即可，示例如下：

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
minHeap.add(10);
System.out.println(minHeap.poll()); // 输出1

在上述示例中，我们首先创建了一个空的优先级队列，然后使用add()方法向其中添加元素，使用poll()方法从队列中取出元素并删除。由于大根堆和小根堆的比较器不同，它们会按照不同的顺序取出元素。

除了示例中用到的add()和poll()方法之外，PriorityQueue类还提供了一些其他常用的方法，下面对一些常用方法进行补充说明：

offer(E e): 添加元素到队列中，如果队列已满则抛出异常。

1 2	`arduinoCopy codePriorityQueue<Integer> queue = new PriorityQueue<>(); queue.offer(1);`

peek(): 获取但不删除队列的头部元素，如果队列为空则返回null。

arduinoCopy codePriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.peek()); // 输出1

remove(Object o): 从队列中删除指定的元素，如果队列中不存在该元素则返回false。

arduinoCopy codePriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.remove(2)); // 输出true
System.out.println(queue.remove(4)); // 输出false
System.out.println(queue); // 输出[3, 1]

size(): 返回队列中元素的数量。

arduinoCopy codePriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.size()); // 输出3

clear(): 删除队列中的所有元素。

arduinoCopy codePriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.clear();
System.out.println(queue); // 输出[]

还有一些其他的方法，如toArray()、contains()、addAll()等，可以参考Java官方文档进行学习。

Greedy

455. 分发饼干

方法一：从小胃口开始喂小饼干

先把两个数组都升序排序，从左往右遍历
如果孩子满足度小于等于饼干满足度，那么++res，并让两个指针都往后移动一位
如果孩子满足度大于饼干满足度，使饼干的指针向后移动一位
直到任意一个指针超出数组范围为止

class Solution {
    public int findContentChildren(int[] children, int[] cookies) {
        int res = 0;
        Arrays.sort(children);
        Arrays.sort(cookies);
        int i = 0, j = 0;
        while (i < children.length && j < cookies.length) {
                if (children[i] <= cookies[j]) {
                    ++res;
                    ++i;
                    ++j;
                }
                else {
                    ++j;                    
                }
        }
        return res;
    }
}

方法二：从大胃口开始喂大饼干

class Solution {
    public int findContentChildren(int[] children, int[] cookies) {
        int res = 0;
        Arrays.sort(children);
        Arrays.sort(cookies);
        int i = children.length - 1, j = cookies.length - 1;
        while (i >= 0 && j >= 0) {
            if (children[i] <= cookies[j]) {
                ++res;
                --i;
                --j;
            }
            else {
                --i;                    
            }   
        }
        return res;
    }
}

376. 摆动序列

方法一：排序+删除连续重复元素+dp(不推荐)

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return 1;
        // 1.dp[i]:以nums[i]为结尾，最长的摆动序列
        List<Integer> list = new LinkedList<>();
        list.add(nums[0]);
        for (int i = 1; i < n; ++i) {
            if (nums[i] != nums[i - 1])
                list.add(nums[i]);
        }
        Integer[] dummy = list.toArray(new Integer[0]);

        if (dummy.length == 1)
            return 1;
        if (dummy.length == 2)
            return 2;
        int[] dp = new int[dummy.length];
        dp[0] = 1;
        dp[1] = 2;
        // 2.状态转移方程：
        // 1)nums[i] - nums[i - 1]与nums[i - 1] - nums[i- 2]异号：dp[i] = dp[i - 1] + 1
        // 2)nums[i] - nums[i - 1]与nums[i - 1] - nums[i- 2]同号：dp[i] = dp[i - 1]

        int res = 1;
        for (int i = 2; i < dummy.length; ++i) {
            if ((dummy[i] - dummy[i - 1]) * (dummy[i - 1] - dummy[i - 2]) < 0) {
                dp[i] = dp[i - 1] + 1;
            }
            else if ((dummy[i] - dummy[i - 1]) * (dummy[i - 1] - dummy[i - 2]) > 0) {
                dp[i] = dp[i - 1];
            }

            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

方法二：贪心

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int preDiff = 0, postDiff = 0;
        int result = 1;
        for (int i = 0; i < nums.length - 1; ++i) {
            postDiff = nums[i + 1] - nums[i];
            if ((preDiff <= 0 && postDiff > 0) || (preDiff >= 0 && postDiff < 0)) {
                ++result;
                preDiff = postDiff;
            }
        }
        return result;
    }
}

方法三：DP

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2)
            return n;
        int[] up = new int[n], down = new int[n];
        up[0] = 1;
        down[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up[i] = Math.max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            }
            else if (nums[i] < nums[i - 1]) {
                up[i] = up[i - 1];
                down[i] = Math.max(down[i - 1], up[i - 1] + 1);
            }
            else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return Math.max(up[n - 1], down[n - 1]);
    }
}

53. 最大子数组和

方法一：DP

dp[i]：以nums[i]结尾的子数组的最大数组和
状态转移方程：
1. 当dp[i - 1] >= 0 时候，dp[i] = dp[i - 1] + nums[i]
2. 当dp[i - 1] < 0时候， dp[i] = nums[i]
初始化：dp[0] = nums[0]
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        // dp[i]：以nums[i]结尾的子数组的最数组和
        int[] dp = new int[n];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < n; ++i) {
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i];
            }
            else { // dp[i - 1] < 0
                dp[i] = nums[i];
            }
            res = Math.max(res, dp[i]);
        }  
        return res;
        
    }
}

方法二：优化空间的DP

由于dp[i]只依赖dp[i - 1]，所以可以用一个长度为2的数组记录dp

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        // dp[i]：以nums[i]结尾的子数组的最数组和
        int[] dp = new int[2];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; ++i) {
            if (dp[(i - 1) % 2] >= 0) {
                dp[i % 2] = dp[(i - 1) % 2] + nums[i];
            }
            else { // dp[i - 1] < 0
                dp[i % 2] = nums[i];
            }
            res = Math.max(res, dp[i % 2]);
        }  
        return res;
    }
}

贪心

首先把记录结果的result初始化为最小值，以及count=0
遍历数组，count加上当前元素，如果count大于result，讲count值赋给result
如果count等于负数了，令count等于0，从下一个数开始重新计算

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            count += nums[i];
            if (count > result) 
                result = count;
            if (count < 0)
                count = 0;
        }
        return result;
    }
}

122. 买卖股票的最佳时机 II

只要下一天股票价格高于当天，那么就买入当前股票并在下一天卖出

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.length - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            if (diff > 0) {
                res += diff;
            }
        }
        return res;
    }
}

55. 跳跃游戏

方法一：贪心

初始化一个available数组，available[i]表示是否可以到底数组元素i
如果当前节点是可到达的，令i=0前往后遍历，把available数组从i+1开始，后nums[i]个元素都赋true
初始化：第一个元素是肯定能到达的，初始化为true
时间复杂度：\(O(n^2)\)，最坏情况下，所有节点都刚好能到达数组倒数第二个元素，且倒数第二个元素的值为0，如[n - 2, n - 3, ..., 1, 0, 1]，需要遍历\(\frac{(n-1)(n-2)}{2}\)次
空间复杂度：\(O(n)\)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] available = new boolean[n];
        available[0] = true;
        for (int i = 0; i < n - 1; ++i) {
            if (available[i]) {
                for (int j = i + 1; j < nums[i] + i + 1; ++j) {
                    if (j == n - 1)
                        return true;
                    available[j] = true;
                }
            }
        }
        return available[n - 1];
    }
}

方法二：贪心（优化空间复杂度）

不必要用一个boolean数组来表示是否可以到达当前数组元素，可以用一个整数rightmost来判断

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1)
                    return true;
            }                
        }
        return false;
    }
}

45. 跳跃游戏 II

方法一：dp

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        // 1.dp[i]：到达i的最小跳数
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < i + 1 + nums[i]; ++j) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
                if (j == n - 1)
                    break;
            }  
        }
        return dp[n - 1];
    }
}

方法二：贪心

class Solution {
    public int jump(int[] nums) {
        int result = 0;
        int n = nums.length;
        int maxDistance = 0, end = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxDistance = Math.max(maxDistance, i + nums[i]);
            if (i == end) {
                end = maxDistance;
                ++result;
            }
        }
        return result;
    }
}

1005. K 次取反后最大化的数组和

先创建一个小根堆，把数组所有元素都放进去
取反小根堆堆顶元素再放回小根堆，循环k次
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

如果小根堆堆顶是负数\(x\)，那么一定是最小的负数，取反后会是比较大的正数\(-x\)；

如果小根堆堆顶是正数\(x\)，那么是最小的正数，取反后是负数\(-x\)，由于此时只有这一个负数，所以\(-x\)是最小值，再放入堆顶，再取反又是最小的正数，循环到k为0为止。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 先创建一个小根堆，把数组所有元素都放进去
        // 取反小根堆堆顶元素再放回小根堆，循环k次
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int n : nums)
            queue.offer(n);
        while (!queue.isEmpty() && k > 0) {
            int cur = queue.poll();
            queue.offer(-1 * cur);
            --k;
        }
        int sum = 0;
        while (!queue.isEmpty()) {
            sum += queue.poll();
        }
        return sum;
    }
}

方法二：优化方法一

先创建一个小根堆，把数组所有元素都放进去
首先小根堆弹出的元素\(x\)如果是负数，就取反(最小的负数取反是比较大的正数),再放回小根堆
小根堆弹出的元素\(x\)如果是是正数：此时\(k\)值如果能被2整除，那么重复取反堆顶元素\(x\)，最终\(x\)不变，直接将\(x\)加入堆中；如果\(k\)值如果不能被2整除，那么将-x加入堆中

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 先创建一个小根堆，把数组所有元素都放进去
        // 要取反k次，首先小根堆弹出的元素x如果是负数，就取反(最小的负数取反是比较大的正数),再放回小根堆
        // 小根堆弹出的元素x如果是是正数：此时k值如果能被2整除，那么重复取反堆顶元素x，最终x不变，直接将x加入堆中；如果k值如果不能被2整除，那么将-x加入堆中
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int n : nums)
            queue.offer(n);
        while (!queue.isEmpty() && k > 0) {
            int cur = queue.poll();
            if (cur < 0) {
                queue.offer(-1 * cur);
                --k;
            }
            else { // cur >= 0
            int negPart = k % 2 == 0 ? 1	 : -1;
                queue.offer(cur * negPart);
                break;
            }
        }
        int sum = 0;
        while (!queue.isEmpty()) {
            sum += queue.poll();
        }
        return sum;
    }
}

方法三：贪心(二刷)

首先将数组升序排序
进入for循环，注意循环的条件有两个，i < nums.length || k > 0
当k==0时，说明已经翻转了k次，不需要继续执行程序了，break即可
if (i == nums.length)留到最后讲解
如果，nums[i] <= 0，直接翻转即可；如果nums[i] > 0，那么说明此时数组里已经没有负数了，那么需要找到最小的正数，并且将剩余需要翻转的次数都对这个数使用：最小的正数只可能是当前的数或者前一个位置的数，比如数组[-5, -4, -3, 2, 3, 5]，需要翻转四次，翻转四次后数组为[5, 4, 3, 2, 3, 5]，即负数部分翻转后是降序。如果k能被2整除，那么翻转k次后这个数还是保持不变；如果不能被2整除，翻转一次即可。最后break退出for循环
如果i == nums.length，但是k的次数还没用完，这种情况只可能是数组元素全为负的情况，如果有一个正数，k都会在

if (nums[i] >= 0 && i > 0) 语句下被消化。这种情况下，一定是最后一个数最小，如果k不能被2整除，就nums[i - 1]翻转即可。比如数组为[-4, -3, -2]，需要翻转4次，翻转3次后数组为

[4, 3, 2]，此时i == nums.length，翻转2即可

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length || k > 0; ++i) {
            if (k == 0)
                break;
            if (i == nums.length)
                 i--;
            if (nums[i] >= 0 && i > 0) {
                i = nums[i] > nums[i - 1] ? i - 1 : i;
                if (k % 2 == 1) {
                    nums[i] *= -1;
                }
                break;
            }
            nums[i] *= -1;
            --k;
        }
        return Arrays.stream(nums).sum();
    }
}

134. 加油站:warning:

方法一：贪心

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                index = (i + 1) % gas.length ; 
                curSum = 0;
            }
        }
        return (totalSum < 0) ? -1 : index;
    }
}

方法二：最小累计值的下一站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int rest = 0;
        int minDiff = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < gas.length; ++i) {
            rest += gas[i] - cost[i];
            if (rest < minDiff) {
                minDiff = rest;
                minIndex = i;
            }
        }
        return rest < 0 ? -1 : (minIndex + 1) % gas.length;
    }
}

135. 分发糖果

先从左往右，再从右往左

class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
        for (int i = 1; i < candy.length; ++i) {
            if (ratings[i] > ratings[i - 1]) 
                candy[i] += candy[i - 1];
        }
        for (int i = candy.length - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i]) {
                candy[i - 1] = Math.max(candy[i - 1], candy[i] + 1);
            }
        }
        return Arrays.stream(candy).sum();
    }
}

860. 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if (bills[0] != 5)
            return false;
        int five = 0, ten = 0;
        for (int i = 0; i < bills.length; ++i) {
            if (bills[i] == 5) {
                ++five;
            }
            else if (bills[i] == 10) {
                if (five > 0) {
                    --five;
                    ++ten;
                }
                else {
                    return false;
                }
            }
            else {
                if (five > 0 && ten > 0) {
                    --five;
                    --ten;
                }
                else if (five >= 3) {
                    five -= 3;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
}

406. 根据身高重建队列 :warning:

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 先按照身高进行降序排序，再按照k进行升序排序
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                }
                else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> list = new LinkedList<>();
        for (int[] person : people) {
            list.add(person[1], person);
        }
        return list.toArray(new int[list.size()][]);
    }
}

452. 用最少数量的箭引爆气球

注意事项：

compare方法用return p1[0] - p2[0]会越界！
从左往右遍历，如果左边气球的右边界大于等于右边气球的左边界，那么可以一箭双球，此时有可能有第三个气球和前面两个气球有重合，但是把第一个气球的右边界设置为重合气球右边界的最小值

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                return Integer.compare(point1[0], point2[0]);
            }
        });
        int arrow = 1;
        for (int i = 0, j = 1; j < points.length; ++j) {
            if (points[i][1] >= points[j][0]) {
                points[i][1] = Math.min(points[i][1], points[j][1]);
            }
            else {
                ++arrow;
                i = j;
            }
        }
        return arrow;
    }
}

435. 无重叠区间

方法一：

比较器按以下方法来，不然容易出错！！

Arrays.sort(intervals, new Comparator<int[]>() {
    public int compare(int[] p1, int[] p2) {
        if (p1[0] == p2[0]) {
            return Integer.compare(p1[1], p2[1]);
        }
        else {
            return Integer.compare(p1[0], p2[0]);
        }
    }
});

先定义比较器，如果p1, p2第一个元素不相等，则按照第一个元素升序排序；如果第一个元素相等，则按照第二个元素升序排序
双指针从前往后遍历，初始i=0，j=1
当intervals[i]与intervals[j]的第一个元素相等，那么必定要移除其中一个，由于比较器的排序，intervals[j]的区间更大，那么选择移除intervals[j]，答案只需要返回最少移除了多少个数，所以将表示删除元素个数的变量erase加一，让j后移即可
当intervals[i]与intervals[j]的第一个元素不相等时候，分两种情况讨论
1. 如果intervals[i]的第二个元素 > intervals[j]的第一个元素，此时区间重合，删除第二个元素即可，将表示删除元素个数的变量erase加一；如果此时intervals[i]的第二个元素 > intervals[j]的第二个元素，说明intervals[i]包含 intervals[j]，那么此时必定删除 intervals[i]，将i指向j表示删除 intervals[i]这个元素
2. 如果intervals[i]的第二个元素 <= intervals[j]的第一个元素，那么i与j之间的元素都不重复，将i移动到j的位置

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[0] == p2[0]) {
                    return Integer.compare(p1[1], p2[1]);
                }
                else {
                    return Integer.compare(p1[0], p2[0]);
                }
            }
        });
        int erase = 0, n = intervals.length;
        for (int i = 0, j = 1; j < n; ++j) {
            if (intervals[i][0] == intervals[j][0]) {
                ++erase;
            }
            else {
                if (intervals[i][1] > intervals[j][0]) {
                    ++erase;
                    if (intervals[i][1] >= intervals[j][1]) {
                        i = j;
                    }
                }
                else { // intervals[i][1] <= intervals[j][0]
                    i = j;
                }
            }
        }
        return erase;
    }
}

方法二：右边界取最小的

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)-> {
            return Integer.compare(a[0],b[0]);
        });
        int count = 0;
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0] < intervals[i-1][1]){
                ++count;
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        for (int[] is : intervals) {
            for (int i : is) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
        return count;
    }
}

二刷：左边界升序排序

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0])
                    return Integer.compare(a[1], b[1]);
                else 
                    return Integer.compare(a[0], b[0]);
            }
        });
        int res = 0;
        for (int i = 0, j = 1; j < intervals.length; ++j) {
            if (intervals[i][1] > intervals[j][0]) {
                intervals[i][1] = Math.min(intervals[i][1], intervals[j][1]);
                ++res;
            }
            else {
                i = j;
            }
        }
        return res;
    }
}

763. 划分字母区间 :warning:

方法一：贪心

首先创建一个长度为26的整型数组，统计每次字符出现的最远位置
遍历字符串，不断更新右边界的值
当当前下标i与右边界相等时，那么就将right-i+1记录

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] ch = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ch[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new LinkedList<>();
        int left = 0, right = -1;
        for (int i = 0; i < s.length(); ++i) {
            right = Math.max(right, ch[s.charAt(i) - 'a']);
            if (i == right) {
                res.add(right - left + 1);
                left = i + 1;
            }
        }
        return res;
    }   
}

56. 合并区间

方法一：

遍历数组，如果后一个元素的左边界大于等于前一个元素的右边界，那么修改后一个元素的左边界为两元素左边界最小的值，修改后一个元素的右边界为两元素右边界最大的值
如果后一个元素左边界大于前一个元素的右边界，直接把前一个元素加入结果list中
最后再把最后一个元素(修改过)加入结果list中

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                return Integer.compare(p1[0], p2[0]);
            }
        });
        List<int[]> res = new LinkedList<>();
        for (int i = 0; i < n - 1; ++i) {
            if (intervals[i + 1][0] <= intervals[i][1]) {
                intervals[i + 1][0] = Math.min(intervals[i + 1][0], intervals[i][0]);
                intervals[i + 1][1] = Math.max(intervals[i + 1][1], intervals[i][1]); 
            }
            else {
                res.add(new int[]{intervals[i][0], intervals[i][1]});
            }
        }
        res.add(new int[]{intervals[n - 1][0], intervals[n - 1][1]});
        return res.toArray(new int[res.size()][]);
    }
}

方法二：射气球的思路

首先将数组按照左边界升序排序
当intervals[i][1] >= intervals[j][0]，那么这两个元素一定是要合并的，因为是intervals数组是按照左边界升序排序的，那么合并区间[a, b]的a一定是intervals[i][0]，将intervals[i][1]赋值为intervals[i][1]与intervals[j][1]的最大值
当intervals[i][1] < intervals[j][0]，那么这个两个区间是不重合的，先把上一个重合区间加入结果集，再把j赋值给i，进行下一轮循环
当j == intervals.length - 1时候，
1. 如果intervals[i][1] >= intervals[j][0]，那么会将intervals[i][1]取intervals[i][1]与intervals[j][1]的最大值
2. 如果intervals[i][1] < intervals[j][0]，那么会将之前的重合区间存入结果集，并将j赋值给i
所以出循环，只需要把intervals[i]加入结果集就好！

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0])
                    return Integer.compare(a[1], b[1]);
                else
                    return Integer.compare(a[0], b[0]);
            }
        });
        List<int[]> res = new LinkedList<>();
        int i = 0;
        for (int j = 1; j < intervals.length; ++j) {
            if (intervals[i][1] >= intervals[j][0]) {
                intervals[i][1] = Math.max(intervals[i][1], intervals[j][1]);
            }
            else  { //  (intervals[i][1] < intervals[j][0])
                res.add(new int[]{intervals[i][0], intervals[i][1]});
                i = j;
            }
        }
        res.add(new int[]{intervals[i][0], intervals[i][1]});
        return res.toArray(new int[res.size()][]);
    }
}

738. 单调递增的数字

从后往前遍历，如果有后一个数大于前一个数，那么就用flag记录后一个数的位置，循环结束后，从flag开始，把后面的数全部赋值‘9’
注意边界！！！

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String str = String.valueOf(n);
        char[] ch = str.toCharArray();
        int flag = ch.length;
        for (int i = ch.length - 1; i > 0; --i) {
            if (ch[i - 1] > ch[i]) {
                --ch[i - 1];
                flag = i;
            }
        }     
        for (int i = flag; i < ch.length; ++i) {
            ch[i] = '9';
        }
        return Integer.parseInt(String.valueOf(ch));
    }   
}

968. 监控二叉树:star:

方法一：贪心

class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        // dfs后检查根节点是否被覆盖
        if (dfs(root) == 404)
            ++result;
        return result;
    }
    private int dfs(TreeNode root) {
        // state 404:未覆盖
        // state 200:覆盖
        // state 201:有监控
        //叶节点的左右空孩子需要返回被覆盖，这样才不会在叶子节点上装监控
        if (root == null)
            return 200;
        // post traversal
        int leftState = dfs(root.left);
        int rightState = dfs(root.right);
        // 1.如果左右子树都被覆盖
        if (leftState == 200 && rightState == 200)
            return 404;
        // 2.如果左右子树至少有一个没被覆盖
        if (leftState == 404 || rightState == 404) {
            ++result;
            return 201;
        }
        // 3.如果左右子树至少有一个监控
        if (leftState == 201 || rightState == 201) 
            return 200;
        return 666;
    }
}

BackTracing

开始回溯前要知道的

详细讲解

注意

如果递归终止条件是这个，那么结果回事全空

if (depth == len) {
    res.add(path);
    return;
}

执行 main 方法以后输出如下：

1	`[[], [], [], [], [], []]`

变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。

在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 6 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。

修改的部分：

if (depth == len) {
    res.add(new ArrayList<>(path));
    return;
}

算法模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

77. 组合

方法一：回溯

由于已知结果要存放的数组大小为k，所以res使用ArrayList
List没有removeLast方法，但是LinkedList中有！

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracing(n, k, 1);
        return res;
    }
    private void backtracing (int n, int k, int start) {
        if (path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i <= n; ++i) {
            path.add(i);
            backtracing(n, k, i + 1);
            // path.removeLast();
            path.removeLast();
        }
    }
}

方法二：方法一+剪枝

for循环横向遍历时候，i的执行条件为i <= n - (k - path.size()) + 1

例如，当i = 2，path里已经有1，需要组合k=3个元素，n为4，那么 4 - (3 - 1) + 1 = 3，说明i最多等于3，组成path[1, 3, 4]，如果此时i = 4，那么就不能组成3个元素，只能组成[1,4]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracing(n, k, 1);
        return res;
    }
    private void backtracing (int n, int k, int start) {
        if (path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
            path.add(i);
            backtracing(n, k, i + 1);
            // path.removeLast();
            path.removeLast();
        }
    }
}

方法二：选或不选

防止底层扩容

1	`Deque<Integer> path = new ArrayDeque<>(k);`

若n=3，k=2,即从[1,2,3]中选两个数，如果当前什么都没选(k=2)，n - k + 1= 2，说明至少要从2开始，才能满足选两个数这个要求
1
2
3
int bound = n - k + 1; if (start > bound) return;

代码如下

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        // 防止底层扩容
        Deque<Integer> path = new ArrayDeque<>(k);
        backtracking(path, n, k, 1);
        return res;
    }
    private void backtracking(Deque<Integer> path, int n, int k, int start) {
        if (k == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        // 若n=3，k=2,即从[1,2,3]中选两个数，如果当前什么都没选(k=2)，n - k + 1= 2，
        // 说明至少要从2开始，才能满足选两个数这个要求
        int bound = n - k + 1;
        if (start > bound)
            return;
        backtracking(path, n, k, start + 1);
        path.addLast(start);
        backtracking(path, n, k - 1, start + 1);
        path.removeLast();
    }
}

216. 组合总和 III

方法一：回溯+剪枝

i那里的剪枝可以这么理解，假设从i开始取，则从i到n一共有n-i+1个元素，而当前还需要k-path.size()个元素，所以必须满足n-i+1>=k-path.size()，移项就可以得到i<=n+1-(k-path.size())

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, new ArrayDeque<>(k));
        return res;
    }
    private void backtracking(int k, int n, int start, Deque<Integer> path) {
        if (path.size() == k) {
            if (n == 0)
                res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i <= 9 - (k - path.size()) + 1; ++i) {
            path.add(i);
            backtracking(k, n - i, i + 1, path);
            path.removeLast();
        }
    }
}

方法二：选或不选

注意：int bound = 9 - k + 1;而不是9 - (k - path.size()) + 1，因为这里的递归终止条件是k==0，==k的语义是还剩多少元素没选！！！==

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, new ArrayDeque<>(k));
        return res;
    }
    private void backtracking(int k, int n, int start, Deque<Integer> path) {
        if (k == 0) {
            if (n == 0)
                res.add(new LinkedList<>(path));
            return;
        }
        int bound = 9 - k + 1;
        if (start > bound)
            return;
        backtracking(k, n, start + 1, path);
        path.add(start);
        backtracking(k - 1, n - start, start + 1, path);
        path.removeLast();
    }
}

17. 电话号码的字母组合

注意边界条件！

class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    String[] alphabet = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0)
            return res;
        backtracing(digits, 0);
        return res;
    }
    private void backtracing(String digits, int start) {
        if (path.length() == digits.length()) {
            res.add(new String(path));
            return;
        }
        char num = digits.charAt(start);
        String str = alphabet[num - '0'];
        for (int i = 0; i < str.length(); ++i) {
            path.append(str.charAt(i));
            backtracing(digits, start + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

39. 组合总和

与前面两题不同的是，可以选取相同元素；以及组合不能重复，如[3，5]与[5，3]是同一个组合

同一个 数字可以 无限制重复被选取

解析

方法一：回溯

去重：遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要 按某种顺序搜索。具体的做法是：每一次搜索的时候设置 下一轮搜索的起点 begin，请看下图。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracing(candidates, target, 0);
        return res;
    }
    private void backtracing(int[] candidates, int target, int start) {
        if (target < 0)
            return;
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            path.add(candidates[i]);
            backtracing(candidates, target - candidates[i], i);
            path.removeLast();
        }
    }
}

方法二：回溯+剪枝

注意：

是i不是start！！！
回溯前要排序！！！

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 排序是剪枝的前提
        Arrays.sort(candidates);
        backtracing(candidates, target, 0);
        return res;
    }
    private void backtracing(int[] candidates, int target, int start) {
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
            if (target - candidates[i] < 0)
                break;
            path.add(candidates[i]);
            backtracing(candidates, target - candidates[i], i);
            path.removeLast();
        }
    }
}

40. 组合总和 II

树层去重，树枝不需要去重

去重和39题(上一题)以及三数之和差不多

方法一：

注意：if判断条件是i > start，不是i > 0

这个避免重复当思想是在是太重要了。
这个方法最重要的作用是，可以让同一层级，不出现相同的元素。即
                  1
                 / \
                2   2  这种情况不会发生 但是却允许了不同层级之间的重复即：
               /     \
              5       5
                例2
                  1
                 /
                2      这种情况确是允许的
               /
              2  
                
为何会有这种神奇的效果呢？
首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。 
因为当第二个2出现的时候，他就和前一个2相同了。
                
那么如何保留例2呢？
那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的，
例2的两个2是处在不同层级上的。
在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，
必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。
第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracing(candidates, target, 0);
            return res;
    }
    private void backtracing(int[] candidates, int target, int start) {
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            // 剪枝
            if (candidates[i] > target)
                break;
            // 去重
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            path.add(candidates[i]);
            backtracing(candidates, target - candidates[i], i + 1);
            path.removeLast();
        }
    }
}

方法二：used数组

多debug

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtracking(candidates, used, target, 0);
        return res;
    }
    public void backtracking(int[] candidates, boolean[] used, int target, int start) {
        if (target == 0) {
            res.add(new LinkedList(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            if (target < candidates[i])
                break;
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])
                continue;
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, used,  target - candidates[i], i + 1);
            used[i] = false;
            path.removeLast();
        }
    }
}

方法三：选或不选

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, false, target, 0);
        return res;
    }
    public void backtracking(int[] candidates, boolean choosePre, int target, int start) {
        if (target == 0) {
            res.add(new LinkedList(path));
            return;
        }
        if (target < 0 || start == candidates.length)
            return;
        backtracking(candidates, false, target, start + 1);
        if (start > 0 && !choosePre && candidates[start] == candidates[start - 1])
            return;
        path.add(candidates[start]);
        backtracking(candidates, true, target - candidates[start], start + 1);
        path.removeLast();
    }
}

131. 分割回文串:warning:

class Solution {
    List<List<String>> res = new LinkedList<>();
    Deque<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtracking(s.toCharArray(), 0);
        return res;
    }
    public void backtracking(char[] ch, int start) {
        if (start == ch.length) {
            res.add(new LinkedList(path));
            return;
        }
        for (int i = start; i < ch.length; ++i) {
            if (isPalindrome(ch, start, i)) {
                path.add(new String(ch, start, i - start + 1));
                backtracking(ch, i + 1);
                path.removeLast();
            }
        }
    }
    public boolean isPalindrome(char[] ch, int start, int end) {
        while (start < end) {
            if (ch[start++] != ch[end--])
                return false;
        }
        return true;
    }
}

:star:93. 复原 IP 地址

重做

方法一：回溯

78. 子集

以下两种方法的区别：

方法二有横向for循环，使用i进入递归方法
方法一有两个递归方法，分别表示选与不选，用start进入递归犯法

方法一：选或不选

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
    private void backtracking(int[] nums, int start) {
        if (start == nums.length) {
            res.add(new LinkedList(path));
            return;
        }
        backtracking(nums, start + 1);
        path.add(nums[start]);
        backtracking(nums, start + 1);
        path.removeLast();
    }
}

方法二：for循环横向顺序遍历

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
    private void backtracking(int[] nums, int start) {
        res.add(new LinkedList(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();	
        }
    }
}

90. 子集 II

方法一：选或不选

如果前后两个数相等，如[1,2,2]，那么只有在第一个2被选择了，才能选择第二个2，不然会重复

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums, false, 0);
        return res;
    }
    public void backtracking(int[] nums, boolean choosePre, int start) {
        if (start == nums.length) {
            res.add(new LinkedList(path));
            return;
        }
        backtracking(nums, false, start + 1);
        if (start > 0 && !choosePre && nums[start - 1] == nums[start])
            return;
        path.add(nums[start]);
        backtracking(nums, true, start + 1);
        path.removeLast();
    }
}

方法二：顺序递归

注意：if判断条件是i > start，不是i > 0

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums, 0);
        return res;
    }
    public void backtracking(int[] nums, int start) {
        res.add(new LinkedList(path));
        for (int i = start; i < nums.length; ++i) {
            if (i > start && nums[i - 1] == nums[i])
                continue;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();  
        }     
    }
}

491. 递增子序列:warning:

方法一：顺序DFS

注意：HashSet的位置！！！每进入一层递归，就会在for循环前创建一个HashSet，这样可以保证树层去重，并且树枝不会qu'chong

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return res;
    }
    public void backtracking(int[] nums, int start) {
        if (path.size() >= 2)
            res.add(new LinkedList(path));
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; ++i) {
            if ((!path.isEmpty() && nums[i] < path.peekLast()))
                continue;
            if (set.contains(nums[i]))
                continue;
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.pollLast();
        }
    }
}

46. 全排列

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtracking(nums);
        return res;
    }
    private void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums);
                used[i] = false;
                path.pollLast();
            }
        }
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtracking(nums);
        return res;
    }
    public void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new LinkedList(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && !used[i - 1] && nums[i - 1] == nums[i])
                continue;
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums);
                used[i] = false;
                path.pollLast();
            }
        }
    }
}

51. N 皇后

方法一：二维数组存表盘

时间复杂度\(O(n^n)\)
空间复杂度\(O(n^2)\)

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] row : chessboard)
            Arrays.fill(row, '.');
        backtracking(0, chessboard, n);
        return res;
    }
    private void backtracking(int row, char[][] chessboard, int n) {
        if (row == n) {
            res.add(toList(chessboard));
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, chessboard, n)) {
                chessboard[row][col] = 'Q';
                backtracking(row + 1, chessboard, n);
                chessboard[row][col] = '.';
            }
        }
    }
    private boolean isValid(int row, int col, char[][] chessboard, int n) {
      for (int i = 0; i < row; ++i)
        if (chessboard[i][col] == 'Q')
            return false;
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (chessboard[i][j] == 'Q')
                return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
            if (chessboard[i][j] == 'Q')
                return false;
        return true;
    }
    private List<String> toList(char[][] chessboard) {
        List<String> path = new ArrayList<>();
        for (char[] ch : chessboard) {
            path.add(String.copyValueOf(ch));
        }
        return path;
    }
}

方法二：一维数组存储每行皇后的列信息

class Solution {
    List<List<String>> res = new ArrayList<>();
    int[] chessboard;
    public List<List<String>> solveNQueens(int n) {
        chessboard = new int[n];
        backtracking(0, n);
        return res;
    }
    private void backtracking(int row, int n) {
        if (row == n) {
            res.add(generatePath(n));
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, n)) {
                chessboard[row] = col;
                backtracking(row + 1, n);
                chessboard[row] = 0;
            }
        }
    }
    private boolean isValid(int row, int col, int n) {
        for (int i = 0; i < row; ++i) {
            if (chessboard[i] == col || Math.abs(col - chessboard[i]) == Math.abs(row - i))
                return false;
        }
        return true;
    }
    private List<String> generatePath(int n) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; ++j) {
                if (j == chessboard[i])
                    sb.append('Q');
                else 
                    sb.append('.');
            }
            path.add(sb.toString());
        }
        return path;
    }
}

方法三：位运算加速

113. 路径总和 II

Graph

797. 所有可能的路径

优质题解

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        path.offerLast(0);
        backtracking(0, graph);
        return res;
    }
    private void backtracking(int start, int[][] graph) {
        if (start == graph.length - 1) {
            res.add(new LinkedList(path));
            return;
        }
        for (int x : graph[start]) {
            path.offerLast(x);
            backtracking(x, graph);
            path.removeLast();
        }
    }
}

200. 岛屿数量

方法一：DFS

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int row = 0; row < grid.length; ++row) {
            for (int col = 0; col < grid[0].length; ++col) {
                if (grid[row][col] == '1') {
                    ++res;
                    dfs(row, col, grid);
                }
            }
        }
        return res;
    }
    private void dfs(int row, int col, char[][] grid) {
        if (row < 0 || row > grid.length - 1 || col < 0 || col > grid[0].length - 1 || grid[row][col] != '1') 
            return;
        grid[row][col] = '2';
        dfs(row - 1, col, grid);
        dfs(row + 1, col, grid);
        dfs(row, col - 1, grid);
        dfs(row, col + 1, grid);
    }
}

方法二：BFS

class Solution {
    public int numIslands(char[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    grid[i][j] = '2';
                    queue.offer(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] coor = queue.poll();
                        int row = coor[0], col = coor[1];
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            queue.offer(new int[]{row -1, col});
                            grid[row - 1][col] = '2';
                        }
                        if (row + 1 < m && grid[row + 1][col] == '1') {
                            queue.offer(new int[]{row + 1, col});
                            grid[row + 1][col] = '2';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            queue.offer(new int[]{row, col - 1});
                            grid[row][col - 1] = '2';
                        }
                        if (col + 1 < n && grid[row][col + 1] == '1') {
                            queue.offer(new int[]{row, col + 1});
                            grid[row][col + 1] = '2';
                        }
                    }
                }
            }
        }        
        return res;
    }
}

方法三：不修改输入数据的DFSF

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int row = 0; row < grid.length; ++row) {
            for (int col = 0; col < grid[0].length; ++col) {
                if (!visited[row][col] && grid[row][col] == '1') {
                    ++res;
                    dfs(row, col, grid, visited);
                }
            }
        }
        return res;
    }
    private void dfs(int row, int col, char[][] grid, boolean[][] visited) {
        if (row >= 0 && col >= 0 && row < grid.length && col < grid[0].length && !visited[row][col] && grid[row][col] == '1') {
            visited[row][col] = true;
            int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
            for (int[] dir :  dirs) {
                dfs(row + dir[0], col + dir[1], grid, visited);
            }
        }
    }
}

695. 岛屿的最大面积

方法一：DFS

class Solution {
    int res = 0;
    int size = 0;
    public int maxAreaOfIsland(int[][] grid) {
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 1) {
                    size = 0;
                    dfs(i, j, grid);
                    System.out.println(res);
                }
            }
        }
        return res;
    }
    private void dfs(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i == grid.length || j == grid[0].length || grid[i][j] != 1) 
            return;
        grid[i][j] = 2;
        res = Math.max(res, ++size);
        dfs(i - 1, j, grid);
        dfs(i + 1, j, grid);
        dfs(i, j - 1, grid);
        dfs(i, j + 1, grid);
    }
}

不修改输入的DFS

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    res = Math.max(res, dfs(i, j, grid, visited));
                }
            }
        }
        return res;
    }
    private int dfs(int i, int j, int[][] grid, boolean[][] visited) {
        if (i < 0 || j < 0 || i == grid.length || j == grid[0].length || grid[i][j] != 1 || visited[i][j]) 
            return 0;
        int res = 1;
        visited[i][j] = true;
        int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            res += dfs(i + dir[0], j + dir[1], grid, visited);
        }
        return res;
    }
}

方法三：DFS标准写法

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, dfs(i, j, grid));
                }
            }
        }
        return res;           
    }
    public int dfs(int i, int j, int[][] grid) {
        int res = 1;
        grid[i][j] = 2;
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, grid.length, grid[0].length) && grid[row][col] == 1) {
                grid[row][col] = 2;
                res += dfs(row, col, grid);
            }
        }
        return res;
    }
    public boolean isValid(int i, int j, int m, int n) {
        return (i >= 0 && j >= 0 && i < m && j < n);
    }
}

827. 最大人工岛:warning::star:

优质题解

class Solution {
    public int largestIsland(int[][] grid) {
        Map<Integer, Integer> idToArea = new HashMap<>();
        int id = 2;
        int m = grid.length, n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    idToArea.put(id, getSingleArea(i, j, grid, id));
                    ++id;
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = Math.max(res, dfs(i, j, grid, idToArea));
            }
        }
        return res;
    }
    private int dfs(int i, int j, int[][] grid, Map<Integer,Integer> idToArea) {
        // if (i < 0 || j < 0 || i == grid.length || j == grid[0].length)
        //     return 0;
        if (grid[i][j] > 0) {
            return idToArea.get(grid[i][j]);
        }
        Set<Integer> set = new HashSet<>();
        int res = 1;
        int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            if (i + dir[0] < 0 || j + dir[1] < 0 || i + dir[0] == grid.length || j + dir[1] == grid[0].length)
                continue;
            set.add(grid[i + dir[0]][j + dir[1]]);
        }
        for (int element : set) {
            res += idToArea.getOrDefault(element, 0);
        }
        return res;
    }
    private int getSingleArea(int i, int j, int[][] grid, int id) {
        if (i < 0 || j < 0 || i == grid.length || j == grid.length || grid[i][j] != 1)
            return 0;
        int res = 1;
        grid[i][j] = id;
        int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            res += getSingleArea(i + dir[0], j + dir[1], grid, id);
        }
        return res;
    }
}

二刷

注意hashmap与hashset的使用细节

class Solution {
    public int largestIsland(int[][] grid) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int id = 2;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 1) {
                    map.put(id, getArea(i, j, grid, id));
                    ++id;
                }
            }
        }
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                res = Math.max(res, dfs(i, j, grid, map));
            }
        }
        return res;
    }
    public int dfs(int i, int j, int[][] grid, Map<Integer, Integer> map) {
        if (grid[i][j] > 0)
            return map.get(grid[i][j]);
        Set<Integer> set = new HashSet<>();
        int res = 1;
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, grid)) {
                int id = grid[row][col];
                set.add(id);
            }
        }
        for (int id : set) {
            res += map.getOrDefault(id, 0);
        }
        return res;
    }
    public int getArea(int i, int j, int[][] grid, int id) {
        grid[i][j] = id;
        int res = 1;
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, grid) && grid[row][col] == 1) {
                grid[row][col] = id;
                res += getArea(row, col, grid, id);
            }
        }
        return res;
    }
    public boolean isValid(int i, int j, int[][] grid) {
        return (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length);
    }
}

463. 岛屿的周长

方法一：DFS

岛屿的上下左右如果是水域或者超出边界，那么周长加一

class Solution {
    public int islandPerimeter(int[][] grid) {
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 2;
                    return dfs(i, j, grid);
                }
            }
        }
        return -1;
    }
    private int dfs(int i, int j, int[][] grid) {
        int res = 0;
        int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, grid) && grid[row][col] == 1) {
                grid[row][col] = 2;
                res += dfs(row, col, grid);
            }
            else {
                if (!isValid(row, col, grid) || grid[row][col] == 0)
                    ++res;
            }
        }
        return res;
    }
    private boolean isValid(int i, int j, int[][] grid) {
        return !(i < 0 || j < 0 || i == grid.length || j == grid[0].length);
    }
}

1020. 飞地的数量:warning:

遇到一个陆地，只会返回numEnclaves进入dfs返回的值，因为相连的陆地在grid中会被修改，numEnclaves循环中不会再次fang'wen

class Solution {
    public int numEnclaves(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 2;
                    res += dfs(i, j, grid);
                }
            }
        }
        return res;
    }
    private int dfs(int i, int j, int[][] grid) {
        int res = 1;
        int[][] dirs = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (!isValid(row, col, grid)) {
                grid[i][j] = 3;
            }
            else if (grid[row][col] == 1) {
                grid[row][col] = 2;
                int ans = dfs(row, col, grid);
                if (ans == 0) {
                    grid[i][j] = 3;
                }
                else 
                    res += ans;
            }
        }
        return grid[i][j] == 3 ? 0 : res;
    }
    private boolean isValid(int i, int j, int[][] grid) {
        return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
    }
}

130. 被围绕的区域

从边界(第一行，最后一行以及第一列和最后一列)找到O，这些O肯定不会被围绕，把这些O都标记为#
把其他位置的O全部赋值为X，将#还原为O

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        if (m <= 2 || n <= 2)
            return;
        for (int i = 0; i < m; i += m - 1) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = '#';
                    dfs(i, j, board);
                }
            }
        }
        for (int j = 0; j < n; j += n - 1) {
            for (int i = 0; i < m; ++i) {
                if (board[i][j] == 'O') {
                    board[i][j] = '#';
                    dfs(i, j, board);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '#')
                    board[i][j] = 'O';                
            }
        }
    }
    private void dfs(int i, int j, char[][] board) {
        int[][] dirs = new int[][] {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, board) && board[row][col] == 'O') {
                board[row][col] = '#';
                dfs(row, col, board);
            }
        }
    }
    private boolean isValid(int i, int j, char[][] board) {
        return i >= 0 && j >= 0 && j < board[0].length && i < board.length;
    }
}

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

方法一：DFS

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new LinkedList<>();
        int m = heights.length, n = heights[0].length;
        boolean[][] pacific = new boolean[m][n], atlantic = new boolean[m][n];
        for (int j = 0; j < n; ++j) 
            dfs(0, j, heights, pacific);
        for (int i = 1; i < m; ++i)
            dfs(i, 0, heights, pacific);
        for (int j = 0; j < n; ++j)
            dfs(m - 1, j, heights, atlantic);
        for (int i = 0; i < m - 1; ++i)
            dfs(i, n - 1, heights, atlantic);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> temp = new ArrayList<>(2);
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }
        return res;
    }   
    public void dfs(int i, int j, int[][] heights, boolean[][] ocean) {
        if (ocean[i][j])
            return;
        ocean[i][j] = true;
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, heights) && heights[row][col] >= heights[i][j])
                dfs(row, col, heights, ocean);
        }
    }
    public boolean isValid(int i, int j, int[][] heights) {
        return i >= 0 && j >= 0 && i < heights.length && j < heights[0].length;
    }
}

127. 单词接龙

方法一：单向广度优先搜索

需要两个队列存储邻居，第一个队列存储的邻居neighbor1距离beginWord的距离是d，将neighbor1的邻居neighbor2存储在queue2中，neighbor2距离beginWord的距离是d + 1
每当把访问完所有queue1中的neighbor1，并且将neighbor2加入到queue2中，那么需要访问新一轮邻居，于是把queue1指向queue2(queue2赋值给queue1)，queue2再新开辟一段空间，此时length(距离)需要加一
开始时需要使用一个HashSet，并将单词表直接放进去，Set<String> set = new HashSet<>(wordList)。函数getNeibours用于找到当前单词所有可能的邻居单词(只有一个字母不同)，对比set中的单词表，如果set中有对应的邻居单词x，则把x加入queue1，并且从set中移除x(如果不移除x，则会重复计算，比如hot的邻居有lot,如果不移除lot，那么下次，如下图

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue1 = new LinkedList<>();
        Queue<String> queue2 = new LinkedList<>();
        Set<String> set = new HashSet<>(wordList);
        int length = 1;
        queue1.offer(beginWord);
        while (!queue1.isEmpty()) {
            String word = queue1.poll();
            if (word.equals(endWord))
                return length;
            List<String> neibours = getNeibours(word);
            for (String str : neibours) {
                if (set.contains(str)) {
                    queue2.offer(str);
                    set.remove(str);
                }
            }
            if (queue1.isEmpty()) {
                ++length;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return 0;
    }
    public List<String> getNeibours(String word) {
        List<String> neibours = new ArrayList<>();
        char[] ch = word.toCharArray();
        for (int i = 0; i < ch.length; ++i) {
            char original = ch[i];
            for (char j = 'a'; j <= 'z'; ++j) {
                if (j != original) {
                    ch[i] = j;
                    neibours.add(new String(ch));
                }
            }
            // backtracking
            ch[i] = original;
        }
        return neibours;
    }
}

剑指 Offer II 109. 开密码锁

注意visited的位置！！！同上一题，在入队时就在visited加入该邻居，避免之后的重复访问

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends)), visited = new HashSet<>();
        String init = "0000";
        if (deadSet.contains(init) || deadSet.contains(target)) 
            return -1;
        visited.add(init);
        Queue<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        queue1.offer(init);
        int res = 0;
        while (!queue1.isEmpty()) {
            String code = queue1.poll();
            if (code.equals(target))
                return res;
            List<String> neibors = getNeibors(code);
            for (String neibor : neibors) {
                if (!deadSet.contains(neibor) && !visited.contains(neibor)) {
                    queue2.offer(neibor);
                    visited.add(neibor);
                }
            }
            if (queue1.isEmpty()) {
                ++res;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return -1;
    }
    public List<String> getNeibors(String code) {
        List<String> neibors = new LinkedList<>();
        for (int i = 0; i < code.length(); ++i) {
            char cur = code.charAt(i);
            StringBuilder sb = new StringBuilder(code);
            // down
            char changed = cur == '0' ? '9' : (char) (cur - 1);
            sb.setCharAt(i, changed);
            neibors.add(sb.toString());
            // up
            changed = cur == '9' ? '0' : (char) (cur + 1);
            sb.setCharAt(i, changed);
            neibors.add(sb.toString());
        }
        return neibors;
    }
}

剑指 Offer II 106. 二分图:warning:

方法一：DFS

染色法需要二刷

class Solution {
    private static final int UNCOLORED = 0;
    private static final int RED = 1;
    private static final int BLUE = 2; 
    private int[] colorArray;
    private boolean res = true;
    public boolean isBipartite(int[][] graph) {
        colorArray = new int[graph.length];
        for (int i = 0; i < graph.length && res; ++i) {
            if (colorArray[i] == UNCOLORED) {
                dfs(i, graph, RED);
            }
        }
        return res;
    }
    private void dfs(int i, int[][] graph, int color) {
        colorArray[i] = color;
        int neighborColor = color == RED ? BLUE : RED;
        for (int neibor : graph[i]) {
            if (colorArray[neibor] == UNCOLORED) {
                dfs(neibor, graph, neighborColor);
                if (!res)
                    return;
            }
            else if (colorArray[neibor] == neighborColor) {
                continue;
            }
            else {
                res = false;
                return;
            }
        }
    }
}

方法二：BFS

class Solution {
    private static final int UNCOLORED = 0;
    private static final int RED = 1;
    private static final int BLUE = 2; 
    private int[] colorArray;
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        colorArray = new int[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (colorArray[i] == UNCOLORED) {
                queue.offer(i);
                colorArray[i] = RED;
                while (!queue.isEmpty()) {
                    int cur = queue.poll();
                    int neiborColor = colorArray[cur] == RED ? BLUE : RED;
                    for (int neibor : graph[cur]) {
                        if (colorArray[neibor] == UNCOLORED) {
                            queue.offer(neibor);
                            colorArray[neibor] = neiborColor;
                        }
                        else if (colorArray[neibor] != neiborColor)
                            return false;
                    }
                }
            }
        }        
        return true;
    }
}

剑指 Offer II 107. 矩阵中的距离

方法一：BFS

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < mat.length; ++i) {
            for (int j = 0; j < mat[i].length; ++j) {
                if (mat[i][j] == 0) {
                    visited[i][j] = true;
                    // dist[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int distance = dist[pos[0]][pos[1]];
            for (int[] dir : dirs) {
                int row = pos[0] + dir[0], col = pos[1] + dir[1];
                if (isValid(row, col, m, n) && !visited[row][col]) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                    dist[row][col] = distance + 1;
                }
            }
        }
        return dist;
    }
    private boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

剑指 Offer II 111. 计算除法:warning:

方法一：BFS

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] res = new double[queries.size()];
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);
        for (int i = 0; i < queries.size(); ++i) {
            String from = queries.get(i).get(0);
            String to = queries.get(i).get(1);
            if (!graph.containsKey(from) || !graph.containsKey(to))
                res[i] = -1;
            else {
                Set<String> visited = new HashSet<>();
                res[i] = dfs(graph, visited, from, to);
            }
        }
        return res;    
    }
    private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited, String from, String to) {
        if (from.equals(to)) 
            return 1.0;
        visited.add(from);
        for (Map.Entry<String, Double> entry: graph.get(from).entrySet()) {
            String key = entry.getKey();
            double val = entry.getValue();
            if (!visited.contains(key)) {
                double res = dfs(graph, visited, key, to);
                if (res != -1) {
                    return res * val;
                }
            }
        }
        visited.remove(from);
        return -1.0;
    }
    private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); ++i) {
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            graph.putIfAbsent(var1, new HashMap<>());
            graph.get(var1).put(var2, values[i]);
            graph.putIfAbsent(var2, new HashMap<>());
            graph.get(var2).putIfAbsent(var1, 1.0 / values[i]);
        }
        return graph;
    }
}

剑指 Offer II 112. 最长递增路径:star:

方法一：DFS

class Solution {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] path;
    public int longestIncreasingPath(int[][] matrix) {
        int res = 0, m = matrix.length, n = matrix[0].length;
        path = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int dist = dfs(i, j, m, n, matrix);
                res = Math.max(res, dist);
            }
        }
        return res;
    }
    public int dfs(int i, int j, int m, int n, int[][] matrix) {
        if (path[i][j] != 0)
            return path[i][j];
        int max = 1;        
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col, m, n) && matrix[row][col] > matrix[i][j]) {
                int dist = dfs(row, col, m, n, matrix);
                max = Math.max(max, dist + 1);
            }
        }        
        path[i][j] = max;
        return max;
    }
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

剑指 Offer II 113. 课程顺序

方法一：拓扑排序

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; ++i)
            graph.put(i, new LinkedList<>());
        int[] inDegrees = new int[numCourses];
        for (int i = 0; i < prerequisites.length; ++i) {
            ++inDegrees[prerequisites[i][0]];
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        List<Integer> order = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i)
            if (inDegrees[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int next : graph.get(node)) {
                if (--inDegrees[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return order.size() == numCourses ? order.stream().mapToInt(Integer::intValue).toArray() : new int[0];
    }
}

剑指 Offer II 114. 外星文字典

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegrees = new HashMap<>();
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                graph.putIfAbsent(ch, new HashSet<>());
                inDegrees.putIfAbsent(ch, 0);
            }
        }
        for (int i = 1; i < words.length; ++i) {
            String word1 = words[i - 1];
            String word2 = words[i];
            if (word1.startsWith(word2) && !word1.equals(word2))
                return "";
            for (int j = 0; j < word1.length() && j < word2.length(); ++j) {
                char ch1 = word1.charAt(j);
                char ch2 = word2.charAt(j);
                if (ch1 != ch2) {
                    if (!graph.get(ch1).contains(ch2)) {
                        graph.get(ch1).add(ch2);
                        inDegrees.put(ch2, inDegrees.get(ch2) + 1);
                    }
                    break;
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : inDegrees.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        StringBuilder res = new StringBuilder();
        while (!queue.isEmpty()) {
            char ch = queue.poll();
            res.append(ch);
            Set<Character> nexts = graph.get(ch);
            for (char next : nexts) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }
        return res.length() == graph.size() ? res.toString() : "";
    }
}

剑指 Offer II 115. 重建序列

class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegrees = new HashMap<>();
        for (int[] sequence : sequences) {
            for (int num : sequence) {
                graph.putIfAbsent(num, new HashSet<>());
                inDegrees.put(num, 0);
            }
        }
        for (int i = 0; i < sequences.length; ++i) {
            for (int j = 1; j < sequences[i].length; ++j) {
                int num1 = sequences[i][j - 1], num2 = sequences[i][j];
                if (!graph.get(num1).contains(num2)) {
                    graph.get(num1).add(num2);
                    inDegrees.put(num2, inDegrees.get(num2) + 1);
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : inDegrees.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        List<Integer> res = new LinkedList<>();
        while (queue.size() == 1) {
            int num = queue.poll();
            res.add(num);
            Set<Integer> nexts = graph.get(num);
            for (int next : nexts) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }
        int[] resToArr = res.stream().mapToInt(Integer::intValue).toArray();
        return Arrays.equals(resToArr, nums);
    }
}

剑指 Offer II 116. 省份数量

方法一：DFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int res = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, n, visited, isConnected);
                ++res;
            }
        }
        return res;
    }
    private void dfs(int i, int n, boolean[] visited, int[][] isConnected) {
        for (int j = 0; j < n; ++j) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(j, n, visited, isConnected);
            }
        }
    }
}

方法二：BFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int res = 0;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                ++res;
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int province = queue.poll();
                    visited[province] = true;
                    for (int j = 0; j < n; ++j) {
                        if (isConnected[province][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            queue.offer(j);
                        }
                    }
                }
            }
        }
        return res;
    }
}

方法三：并查集

并查集的讲解

findFather一定要return fathers[i]，而不是return i，因为当0的father是1的时候，return 1 而不是return 0！
两层for循环第二层j = i + 1，因为首先j = i的话，是遍历两个相同的节点没意义；其次，i之前的节点在之前就已经合并过了，所以不需要再遍历了

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int res = n;
        int[] fathers = new int[n];
        for (int i = 0; i < n; ++i)
            fathers[i] = i;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isConnected[i][j] == 1 && union(i, j, fathers)) {
                    --res;
                }
            }
        }
        return res;
    }

    private boolean union(int i, int j, int[] fathers) {
        int fatherOfI = findFather(i, fathers);
        int fatherOfJ = findFather(j, fathers);
        if (fatherOfI != fatherOfJ) {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }
        return  false;
    }

    private int findFather(int i, int[] fathers) {
        if (i != fathers[i])
            fathers[i] = findFather(fathers[i], fathers);
        return fathers[i];
    }
}

剑指 Offer II 117. 相似的字符串

方法一：并查集

判断是否是相似字符串的函数isAnalogical之前用的蠢方法，还要拷贝再交换，直接判断不同字符num的个数就行
1. 如果num==0，那么相似
2. 由于题目给出的字符串数组中，所有字符串互为 字母异位词(字母顺序不同)，所以num == 2时，是交换了两个字符，如果num > 2，就不符合题意了

class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int res = n;
        int[] fathers = new int[n];
        for (int i = 0; i < n; ++i)
            fathers[i] = i;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                String str1 = strs[i], str2 = strs[j];
                if (isAnalogical(str1, str2) && union(i, j, fathers)) {
                    --res;
                }
            }
        }
        return res;
    }

    private boolean union(int i, int j, int[] fathers) {
        int fatherOfI = findFather(i, fathers);
        int fatherOfJ = findFather(j, fathers);
        if (fatherOfI != fatherOfJ) {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }
        return false;
    }

    private int findFather(int i, int[] fathers) {
        if (i != fathers[i])
            fathers[i] = findFather(fathers[i], fathers);
        return fathers[i];
    }

    private boolean isAnalogical(String a, String b) {
        int num = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                num++;
                if (num > 2) {
                    return false;
                }
            }
        }
        return true;
    }
}

剑指 Offer II 118. 多余的边

方法一：并查集

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] fathers = new int[n + 1];
        for (int i = 0; i < n; ++i)
            fathers[i] = i;
        for (int[] edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            if (!union(node1, node2, fathers))
                return new int[]{node1, node2};
        }
        return new int[2];
    }

    private boolean union(int i, int j, int[] fathers) {
        int fatherOfI = findFather(i, fathers);
        int fatherOfJ = findFather(j, fathers);
        if (fatherOfI != fatherOfJ) {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }
        return false;
    }

    private int findFather(int i, int[] fathers) {
        if (i != fathers[i])
            fathers[i] = findFather(fathers[i], fathers);
        return fathers[i];
    }
}

剑指 Offer II 119. 最长连续序列

方法一：暴力

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0)
            return 0;
        Arrays.sort(nums);
        for (int i : nums)
            System.out.print(i + " ");
        int res = 1, cur = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1])
                continue;
            if (nums[i] - nums[i - 1] == 1) {
                ++cur;
                res = Math.max(res, cur);
            }
            else {
                cur = 1;
            }
        }
        return res;
    }
}

方法二：并查集

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> fathers = new HashMap<>(), count = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            fathers.put(num, num);
            count.put(num, 1);
            set.add(num);
        }
        for (int num : nums) {
            if (set.contains(num + 1)) {
                union(num, num + 1, fathers, count);
            }
            if (set.contains(num - 1)) {
                union(num, num - 1, fathers, count);
            }
        }
        int res = 0;
        for (int val : count.values()) {
            res = Math.max(res, val);
        }
        return res;
    }

    private void union(int i, int j, Map<Integer, Integer> fathers, Map<Integer, Integer> count) {
        int fatherOfI = findFather(i, fathers);
        int fatherOfJ = findFather(j, fathers);
        if (fatherOfI != fatherOfJ) {
            fathers.put(fatherOfI, fatherOfJ);
            count.put(fatherOfJ, count.get(fatherOfI) + count.get(fatherOfJ));
        }
    }

    private int findFather(int i, Map<Integer, Integer> fathers) {
        int fatherOfI = fathers.get(i);
        if (i != fatherOfI) {
            fathers.put(i, findFather(fatherOfI, fathers));
        }
        return fathers.get(i);
    }
}

Binary Search

剑指 Offer II 068. 查找插入位置

方法一：

如果nums中有target，那么会被找到并被返回
如果nums中没有target，那么有三种情况，这个数应该被插入道
1. 第一个位置
2. 最后一个位置
3. 中间
这三种情况的索引都是退出循环后的left！！！

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) 
                right = mid - 1;
            else {
                left = mid + 1;
            }
        }
        return left;
    }
}

方法二：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (nums[mid] >= target) {
                if (mid == 0 || nums[mid - 1] < target)
                    return mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return nums.length;
    }
}

Heap

剑指 Offer II 059. 数据流的第 K 大数值

方法一：小根堆

class KthLargest {

    private PriorityQueue<Integer> queue;
    private int size;
    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>();
        size = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        queue.offer(val);
        if (queue.size() >  size) {
            queue.poll();
        }
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

方法二：小根堆另一种写法

class KthLargest {

    private PriorityQueue<Integer> queue;
    private int k;
    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (queue.size() < k) {
            queue.offer(val);
        }
        else if (queue.size() == k && queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

剑指 Offer II 060. 出现频率最高的 k 个数字

方法一：小根堆

小根堆的比较方式
小根堆的类型是Map.Entry

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
                (e1, e2) -> e1.getValue() - e2.getValue());
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }
            else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }
        int[] res = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) 
            res[i++] = minHeap.poll().getKey();
        return res;
    }
}

剑指 Offer II 061. 和最小的 k 个数对

方法一：大根堆

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
                (o1, o2) -> o2[0] + o2[1] - o1[0] - o1[1]);
        for (int i = 0; i < Math.min(k, nums1.length); ++i) {
            for (int j = 0; j < Math.min(k, nums2.length); ++j) {
                if (maxHeap.size() < k)
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                else if (maxHeap.peek()[0] + maxHeap.peek()[1] > nums1[i] + nums2[j]) {
                    maxHeap.poll();
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                }
            }
        }
        List<List<Integer>> res = new LinkedList<>();
        while (!maxHeap.isEmpty()) {
            int[] temp = maxHeap.poll();
            res.add(Arrays.asList(temp[0], temp[1]));
        }
        return res;
    }
}

排序

快速排序

边界问题：end > start。当start == end的时候，已经是排序好的一个数，不需要在进行partition

public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int start, int end) {
        if (end > start) {
            int pivot = partition(nums, start, end);
            quickSort(nums, start, pivot - 1);
            quickSort(nums, pivot + 1, end);
        }
    }

    private int partition(int[] nums, int start, int end) {
        int random = new Random().nextInt(end - start + 1) + start;
        swap(nums, random, end);
        int small = start - 1;
        for (int i = start; i < end; ++i) {
            if (nums[i] < nums[end]) {
                ++small;
                swap(nums, small, i);
            }
        }
        // 没有小于pivot的数了
        ++small;
        swap(nums, small, end);
        return small;
    }

    private void swap(int[] nums, int random, int end) {
        if (random != end) {
            int temp = nums[end];
            nums[end] = nums[random];
            nums[random] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 3, 1, 4};
        int[] clone = nums.clone();
        QuickSort quickSort = new QuickSort();
        quickSort.sortArray(nums);
        for (int num : nums)
            System.out.print(num + " ");
        System.out.println();
        Arrays.sort(clone);
        for (int cl : clone)
            System.out.print(cl + " ");
    }

剑指 Offer II 076. 数组中的第 k 大的数字

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0, end = nums.length - 1;
        int pivot = partition(nums, start, end);
        while (pivot != target) {
            if (pivot > target) {
                end = pivot - 1;
            }
            else {
                start = pivot + 1;
            }
            pivot = partition(nums, start, end);
        }
        return nums[pivot];
    }

    public int partition(int[] nums, int start , int end) {
        int random = new Random().nextInt(end - start + 1) + start;
        swap(nums, random, end);
        int small = start - 1;
        for (int i = start; i < end; ++i) {
            if (nums[i] < nums[end]) {
                ++small;
                swap(nums, small, i);
            }
        }
        ++small;
        swap(nums, small, end);
        return small;
    }

    public void swap(int[] nums, int index1, int index2) {
        if (index1 != index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

}

前缀树

剑指 Offer II 062. 实现前缀树

public class Trie {
    static class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public  TrieNode() {
            children = new TrieNode[26];
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.children[ch - 'a'] == null) {
                cur.children[ch - 'a'] = new TrieNode();
            }
            cur = cur.children[ch - 'a'];
        }
        cur.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.children[ch - 'a'] == null)
                return false;
            cur = cur.children[ch - 'a'];
        }
        return cur.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char ch : prefix.toCharArray()) {
            if (cur.children[ch - 'a'] == null)
                return false;
            cur = cur.children[ch - 'a'];
        }
        return true;
    }
}

剑指 Offer II 063. 替换单词

方法一：前缀树

class Solution {
    static class TrieNode {
        private TrieNode[] children;
        private boolean isWord;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }


    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = buildTrie(dictionary);
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; ++i) {
            String prefix = findPrefix(root, words[i]);
            if (!prefix.isEmpty()) {
                words[i] = prefix;
            }
        }
        return String.join(" ", words);
    }

    private String findPrefix(TrieNode root, String word) {
        TrieNode cur = root;
        StringBuilder sb = new StringBuilder();
        for (char ch : word.toCharArray()) {
            if (cur.children[ch - 'a'] == null || cur.isWord)
                break;
            sb.append(ch);
            cur = cur.children[ch - 'a'];
        }
        return cur.isWord == true ? sb.toString() : "";
    }

    private TrieNode buildTrie(List<String> dictionary) {
        TrieNode root = new TrieNode();
        for (String str : dictionary) {
            TrieNode cur = root;
            for (char ch : str.toCharArray()) {
                if (cur.children[ch - 'a'] == null)
                    cur.children[ch - 'a'] = new TrieNode();
                cur = cur.children[ch - 'a'];
            }
            cur.isWord = true;
        }
        return root;
    }
}

剑指 Offer II 064. 神奇的字典:warning:

方法一：前缀树


class MagicDictionary {
    static class TrieNode {
        private TrieNode[] children;
        private boolean isWord;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    /** Initialize your data structure here. */
    private TrieNode root;
    public MagicDictionary() {
        root = new TrieNode();
    }
    
    public void buildDict(String[] dictionary) {
        for (String str : dictionary) {
            TrieNode cur = root;
            for (char ch : str.toCharArray()) {
                if (cur.children[ch - 'a'] == null)
                    cur.children[ch - 'a'] = new TrieNode();
                cur = cur.children[ch - 'a'];
            }
            cur.isWord = true;
        }
    }
    
    public boolean search(String searchWord) {
        return dfs(root, searchWord, 0, 0);
    }

    public boolean dfs(TrieNode root, String searchWord, int index, int modifiedNum) {
        if (root == null)
            return false;
        if (root.isWord && index == searchWord.length() && modifiedNum == 1)
            return true;
        if (modifiedNum <= 1 && index < searchWord.length()) {
            boolean found = false;
            for (int j = 0; j < 26 && !found; ++j) {
                int next = j == searchWord.charAt(index) - 'a' ? modifiedNum : modifiedNum + 1;
                found = dfs(root.children[j], searchWord, index + 1, next);
            }
            return found;
        }
        return false;
    }

}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */
//leetcode submit region end(Prohibit modification and deletion)

剑指 Offer II 065. 最短的单词编码:warning::star:

方法一：前缀树

这种DFS技巧非常重要！！！

class Solution {
    static class TrieNode {
        private TrieNode[] children;
        private boolean isEnd;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    private int res = 0;
    public int minimumLengthEncoding(String[] words) {
        TrieNode root = buildTree(words);
        dfs(root, 1);
        return res;
    }

    private void dfs(TrieNode root, int length) {
        boolean isLeaf = true;
        for (TrieNode child : root.children) {
            if (child != null) {
                isLeaf = false;
                dfs(child, length + 1);
            }
        }
        if (isLeaf)
            res += length;
    }

    private TrieNode buildTree(String[] words) {
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            TrieNode cur = root;
            for (int j = word.length() - 1; j >= 0; --j) {
                char ch = word.charAt(j);
                if (cur.children[ch - 'a'] == null)
                    cur.children[ch - 'a'] = new TrieNode();
                cur = cur.children[ch - 'a'];
            }
            cur.isEnd = true;
        }
        return root;
    }
}

剑指 Offer II 066. 单词之和

方法一：前缀树

class MapSum {
    static class TrieNode {
        private TrieNode[] children;
        private int val;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    private TrieNode root;
    /** Initialize your data structure here. */
    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode cur = root;
        for (char ch : key.toCharArray()) {
            if (cur.children[ch - 'a'] == null)
                cur.children[ch - 'a'] = new TrieNode();
            cur = cur.children[ch - 'a'];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for (char ch : prefix.toCharArray()) {
            if (cur.children[ch - 'a'] == null)
                return 0;
            cur = cur.children[ch - 'a'];
        }
        return dfs(cur);
    }

    private int dfs(TrieNode cur) {
        int sum = cur.val;
        for (TrieNode child : cur.children) {
            if (child != null)
                sum += dfs(child);
        }
        return sum;
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        mapSum.sum("ap");
        mapSum.insert("app", 2);
        mapSum.sum("ap");
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

剑指 Offer II 067. 最大的异或

方法一：前缀树

class Solution {
    static class TrieNode {
        private TrieNode[] children;
        public TrieNode() {
            children = new TrieNode[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
        TrieNode root = buildTrie(nums);
        int max = 0;
        for (int num : nums) {
            TrieNode cur = root;
            int xor = 0;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                if (cur.children[1 - bit] != null) {
                    cur = cur.children[1 - bit];
                    xor = (xor << 1) + 1;
                }
                else {
                    cur = cur.children[bit];
                    xor = xor << 1;
                }
            }
            max = Math.max(max, xor);
        }
        return max;
    }

    private TrieNode buildTrie(int[] nums) {
        TrieNode root = new TrieNode();
        for (int num : nums) {
            TrieNode cur = root;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                if (cur.children[bit] == null) {
                    cur.children[bit] = new TrieNode();
                }
                cur = cur.children[bit];
            }
        }
        return root;
    }
}

tips

新建数组时赋值

int[] array = new int[]{3, 4}；

链表转数组

方法一：

1	`int[] intArray = linkedList.stream().mapToInt(Integer::intValue).toArray();`

这行代码可以分解为以下几个部分：

linkedList.stream(): 将LinkedList转换为Stream。
mapToInt(Integer::intValue): 将Stream中的每一个元素转换为int类型。
- Integer::intValue是一个方法引用，表示调用Integer对象的intValue()方法，将其转换为对应的int值。
toArray(): 将转换后的元素放到一个int数组中。
- toArray()的作用是将Stream中的所有元素转换为一个数组，返回值是一个int[]类型的数组。

综上所述，int[] intArray = linkedList.stream().mapToInt(Integer::intValue).toArray();的语义是将LinkedList中的所有元素转换为int类型，并将其放入一个int数组中。在这个过程中，我们使用了Java 8引入的Stream API，它提供了许多方便的操作，可以简化代码的编写和调试。

方法二：

1	`res.toArray(new int[res.size()][]);`

创建长度二维数组，其中一维数组的长度不确定

1	`new int[][]{{1, 2}, {3}, {3}, {}}`

char转int，String转int

// 将字符转换为整数
char c = '8';
int num = Character.getNumericValue(c); // num = 8

// 将字符串转换为整数
String str = "123";
int num2 = Integer.parseInt(str); // num2 = 123

String转int时，什么时候用parseInt什么时候用valueOf

在Java中，parseInt和valueOf都可以将字符串转换为整数。parseInt方法将字符串转换为基本数据类型int，而valueOf方法将字符串转换为对象类型Integer。因此，使用哪个方法取决于你要使用返回的数据类型。

如果你只需要一个基本数据类型int，那么使用parseInt是最好的选择，因为它会返回一个原始类型，不会产生额外的对象开销。

例如：

java Copy code String str = "123"; int num = Integer.parseInt(str);

如果你需要一个对象类型Integer，则使用valueOf方法是最好的选择。valueOf方法返回一个Integer对象，这在某些情况下非常有用。

例如：

java Copy code String str = "123"; Integer num = Integer.valueOf(str);

总之，如果你只需要一个基本数据类型，那么使用parseInt方法，否则使用valueOf方法。

使用scanner.nextLine()读取行末的换行符

public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       scanner.nextLine();
       for (int i = 0; i < n; ++i) {
           String word = scanner.nextLine();
           System.out.println("word: " + word);
           Main main = new Main();
           String ans = main.process(word);
           System.out.println(ans);
       }

这段代码首先从标准输入中读取一个整数n，然后通过调用scanner.nextLine()读取掉n后面的换行符。接下来，通过for循环n次，读取n行字符串，每次读取一行字符串后，调用process方法进行处理，最后将处理结果打印到标准输出中。

需要注意的是，在使用Scanner读取完整行时，由于nextInt只读取整数，因此需要在nextInt后面调用nextLine读取行末的换行符。这样做是为了防止接下来的nextLine方法误读取行末的换行符。

创建长度不同的二维数组

在Java中，可以创建长度不同的二维数组。以下是创建长度不同的二维数组的示例：

int[][] arr = new int[3][];
arr[0] = new int[2];
arr[1] = new int[3];
arr[2] = new int[4];

在这个示例中，我们创建了一个3 x n的二维数组，其中n的长度不同。第一行有两个元素，第二行有三个元素，第三行有四个元素。我们可以通过以下方式访问数组的元素：

arr[0][0] = 1;
arr[0][1] = 2;
arr[1][0] = 3;
arr[1][1] = 4;
arr[1][2] = 5;
arr[2][0] = 6;
arr[2][1] = 7;
arr[2][2] = 8;
arr[2][3] = 9;

请注意，当您创建长度不同的二维数组时，每行的长度必须在运行时确定。因此，您必须在运行时动态地为每行分配内存空间。

数组拷贝：ch.clone与Arrays.copyOf的区别

对基础类型的拷贝都是值传递的拷贝(深拷贝)，对对象的拷贝都是拷贝的引用(浅拷贝)

IDEA创建live template

在 IntelliJ IDEA 中使用 Live Template 来创建并查集的固定代码，可以按照以下步骤进行操作：

打开 IntelliJ IDEA，进入设置面板。你可以通过点击菜单栏的 "File" -> "Settings" (Windows/Linux) 或 "IntelliJ IDEA" -> "Preferences" (Mac) 打开设置面板。
在设置面板中，选择 "Editor" -> "Live Templates"。
在左侧的面板中，选择你想要创建代码模板的语言，比如 "Java"。
点击右侧面板的 "+" 按钮，添加一个新的模板。
在 "Abbreviation" 输入框中输入一个简短的缩写，用于触发代码模板。
在 "Template text" 输入框中输入代码模板的内容，例如：

// 并查集初始化
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
    parent[i] = i;
}

// 并查集查找根节点
private int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 并查集合并两个集合
private void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

点击 "Define" 按钮，选择模板的定义范围，比如选择 "Java"。
点击 "Apply" 或 "OK" 完成模板的创建。

现在，你可以在代码编辑器中输入你设定的缩写，比如 "uf"，然后按下 Tab 键，就会自动插入你定义的并查集代码模板。你可以根据需要修改模板中的变量名和其他细节，以适应你的项目要求。

笔试面试

5.8小红书

第一题.

第二题.

最大最小值
        时间限制： 1000MS
        内存限制： 65536KB
        题目描述：
        有一个长度为n的序列，其中第i个元素ai，你现在可以对这个序列进行最多k次操作，每次可选择一个连续的区间将其中的元素删掉，但剩余的元素个数必须大于0。 现在想让剩余元素的最小值尽可能大，求上述情况下的最大值。



        输入描述
        第一行两个正整数n和k，分别表示初始序列中元素的个数以及最多的操作次数。

        接下来1行，n个正整数，其中第i个数为ai。

        对于所有数据，1<=n<=10^5，0<=k<=10^5，1<=ai <=10^6。

        输出描述
        输出仅包含一个正整数，表示答案。


        样例输入
        8 1
        58 57 86 89 25 26 61 42
        样例输出
        58

1
2
3

这道题是要求给定一个序列，你可以进行最多k次操作，每次操作可以删除序列中的某个连续区间，但是最后删除后剩余元素的最小值尽可能大。你需要输出这个最大的最小值。

举个例子，对于样例输入 [58, 57, 86, 89, 25, 26, 61, 42]，可以进行1次操作，比如删除区间[86,89]，剩下的序列为[58, 57, 25, 26, 61, 42]，此时剩余元素的最小值为25，最大的最小值就是25。你需要编写一个程序来自动寻找最大的最小值。

第三题.

5.10 微众银行

第一题

Snipaste_2023-05-10_19-14-07

```



![1](https://leopold-bucket.oss-cn-guangzhou.aliyuncs.com/img/1.jpg) 

### 第二题

![第二题](https://leopold-bucket.oss-cn-guangzhou.aliyuncs.com/img/第二题.jpg) 

```java
package 面试题.微众银行暑期实习.第2题;

import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();
        long[] energy = new long[n], score = new long[n];
        for (int i = 0; i < n; ++i) {
            energy[i] = scanner.nextLong();
        }
        scanner.nextLine();
        for (int i = 0; i < n; ++i) {
            score[i] = scanner.nextLong();
        }
        long[] res = main.process(n, k, energy, score);
        for (long i : res)
            System.out.print(i + " ");
    }
    Queue<Long> queue = new PriorityQueue<>();

    private long[] process(int n, int k, long[] energy, long[] score) {
        long[] res = new long[n];
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            map.put(energy[i], score[i]);
        }
        long[] oriEnery = new long[n];
        for (int i = 0; i < n; ++i)
            oriEnery[i] = energy[i];
        Arrays.sort(energy);

        for (int i = 0; i < k; ++i) {
            long s = map.get(energy[i]);
            queue.offer(s);
        }
        long sum = map.get(energy[0]);
        for (int i = 1; i < k; ++i) {
            res[i] = sum;
            sum += map.get(energy[i]);
        }

        for (int i = k; i < n; ++i) {
            res[i] = getKMax();
            long s = map.get(energy[i]);
            if (s > queue.peek()) {
                queue.poll();
                queue.offer(s);
            }
        }

        long[] res2 = new long[n]; //resAsOriginalSequence
        for (int i = 0; i < n; ++i) {
            long e = oriEnery[i];
            int index = 0;
            for (; index < n; ++index) {
                if (energy[index] == e)
                    break;
            }
            res2[i] = res[index];
        }
        return res2;
    }

    private int getKMax() {
        int sum = 0;
        Queue<Long> queue2 = new PriorityQueue<>();
        while (!queue.isEmpty()) {
            long temp = queue.poll();
            sum += temp;
            queue2.offer(temp);
        }
        queue = queue2;
        return sum;
    }
}

第三题

Algorithms

https://leopol1d.github.io/2023/04/07/Algorithms/

作者

Leopold

发布于

2023年4月7日

许可协议

Backtracking 上一篇