剑指Offer

剑指 Offer 03. 数组中重复的数字

使用HashMap记录是否出现重复即可。高级一点的做法可以使用 原地交换 ——
当然如果记不住的话，HashMap方法也是可以的。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

剑指 Offer 04. 二维数组中的查找

使用递归进行查找即可，值得注意的地方是：从右上角（或左上角）开始查找，这样查找的话，可以分成当前数大于 target 和 当前数小于 target 进行递归。如果不这样做的话，两种递归方法完全相同，最终会导致一些错误。
递归函数要分成：越界的情况，成功的情况和继续递归的情况。

class Solution {
    public boolean fn(int[][] matrix,int i,int j,int target){
        //越界情况
        if(i>matrix.length-1 || j < 0){
            return false;
        }
        //成功情况
        if(matrix[i][j]==target){
            return true;
        }
        //继续递归情况
        else if(matrix[i][j]<target){
            //小的情况向下查找
            return fn(matrix,i+1,j,target);
        }
        else{
            //大的情况向左查找
            return fn(matrix,i,j-1,target);
        }
    }
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //特殊情况的处理
        if(matrix == null || matrix.length == 0 ||  matrix[0].length == 0){
            return false;
        }
        //从右上角开始
        return fn(matrix,0,matrix[0].length-1,target);
    }
}

剑指 Offer 05. 替换空格

用 StringBuffer 的 append方法，遇到空格就加入一个 “%20” 即可。

剑指 Offer 06. 从尾到头打印链表

对于这些有 反过来 字眼的链表题，可以考虑使用 辅助栈。把链表里的元素一个一个放入栈中，再一个一个取出打印即可。
但是对于栈的使用，我们可以用Java原生提供的 Stack类，同时也可以使用 LinkedList 来模拟栈。

class Solution {
    public int[] reversePrint(ListNode head) {
        int size = 0; //值得注意的是：Stack类没有size方法，需要自己手动计数
        Stack<Integer> stack = new Stack<>();
        while(head != null){
            stack.push(head.val);
            size++;
            head = head.next;
        }
        int[] arr = new int[size];
        for(int i=0;i<size;i++){
            arr[i] = stack.pop(); //每次弹出一个
        }
        return arr;
    }
}

class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
            stack.addLast(head.val); //每次加在末尾
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast(); //每次把末尾删除
        return res;
    }
}

剑指 Offer 07. 重建二叉树⭐

算法思想

在做这道题之前，我们需要知道数据结构中，根据二叉树的先序遍历和中序遍历怎么构建的二叉树。 以 [3,9,20,15,7] 这棵二叉树举例（中序遍历为 [9,3,15,20,7]）：

1. 先序遍历的第一个数就是根节点，然后在中序遍历中找到该节点，就可以找出根节点的左右子树。
2. 然后先序遍历中，根节点的下一个节点就是左子树的根节点，故 左子树根节点索引 = 根节点索引 + 1
3. 根据中序遍历中左子树的节点个数 (root - left + 1)，可以得到右子树的根节点索引。
4. 重复递归，每次递归生成一个节点，然后调用该节点左右子树的递归方法，构建二叉树

具体流程图可以参考解析。

属性准备

1. HashMap，由于我们要根据先序遍历的值，来得到中序遍历中节点对应的索引（注意这道题里值是唯一的，因此可以这样做），所以我们需要一个 HashMap来映射 值->索引。
2. 递归函数，假设 根节点在前序遍历的索引为 root 、子树在中序遍历的左边界为 left 、子树在中序遍历的右边界为 right

左子树在先序遍历的根节点对应的索引就是 root + 1，而右子树在先序遍历的根节点对应的索引是 root + 左子树长度 + 1。左子树长度 = 根节点在中序遍历的索引 - 左边界 = i - left。故对应索引为 root + i - left + 1
递归函数的作用：生成一个和根节点值相同的节点，再调用递归函数获取它的左右根节点。

    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                      // 递归终止
        TreeNode node = new TreeNode(preorder[root]);      // 建立根节点
        int i = dic.get(preorder[root]);                   // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }

    int[] preorder; //由于会在递归函数直接调用，因此可以做成一个属性
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }

剑指 Offer 09. 用两个栈实现队列

需要注意一点：当一次 appendTail 时，需要把s2的剩余元素全部倒入s1中（也就是上一次没有被删除完的元素，要不然无法模拟先进先出），当一次 deleteHead时，需要把s1的剩余元素（入队元素）全部倒入s2中，然后s2弹出一个。
因此s1模拟入队，s2模拟出队。

    public void appendTail(int value) {
        //在加入之前，首先要把s2的剩余全部倒入s1中
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
        s1.push(value);
    }

    public int deleteHead() {
        //删除的时候再把s1倒回去
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        if(s2.isEmpty()){
            return -1;
        }else{
            return s2.pop();
        }
    }

剑指 Offer 10- I. 斐波那契数列

如果单纯的使用递归，那么我们会进行许多无用的计算，比如我们已经计算出了 f(7) = f(6) + f(5)，那么在计算f(8) = f(7) + f(6) 的时候，我们需要重新计算一下 f(7)。这无疑浪费了大量的时间。
我们可以新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算，这就是记忆化递归法。
动态规划法也是同理，新建一个动态规划 dp 数组，以 dp[i+1] = dp[i] + dp[i-1] 为转移方程。初始
状态为 dp[0] = 0, dp[1] = 1，即初始化前两个数字，最终返回 dp[n] 即可。
当然我们还可以继续优化：记忆化递归法 和 动态规划法的空间复杂度是 O(N)，发现计算斐波那契数列时，其实只需要使用前面两个数字 (即 n 和 n-1)，因此我们不需要把所有结果全部记录，只需要用几个变量记录一下需要用到的数据即可。

class Solution {
    public int fib(int n) {
        int a = 0, b = 1, sum;
        //由于知道需要计算几次，不需要进行递归
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b; //更改需要的数据
            b = sum;
        }
        return a;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

对于跳某个台阶，它的方式有：f(n-1) + f(n-2) 种，因此同上一题的思路，比较不同的地方在于：f(0) = 1。

class Solution {
    public int numWays(int n) {
        //f(n) = f(n-1) + f(n-2) 跳一级台阶的方式和跳二级台阶的方式
        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }
        int a = 1, b = 1,r = a+b;
        for(int i=2;i<=n;i++){
            r = (a+b) % 1000000007;
            a = b;
            b = r;
        }
        return r;
    }
}

剑指 Offer 11. 旋转数组的最小数字

遍历法

这道题有一种比较好理解的方法：遍历整个数组，只要出现下降的元素，那么它必定是最小值。如果从头到尾都没有出现，那么就是类似 [2,2,2,2,2,2,2] 这样的数组，返回 numbers[0] 即可。

class Solution {
    public int minArray(int[] numbers) {
        //只要出现下降，那么一定是最小的元素
        for(int i=0;i<numbers.length-1;i++){
            if(numbers[i+1]-numbers[i]<0){
                return numbers[i+1];
            }
        }
        return numbers[0];
    }
}

二分法

有序数组的查找问题，我们一般会想到二分法。我们可以把数组分成左右数组。
声明 left,right 分别为数组的左右两端。mid = (left+right)/2 为每次的中点，接下来是判断左右数组的方法：

1. 当 numbers[mid] > numbers[right] 时，mid 一定在左数组中（因为左数组一定大于等于右数组的元素），此时转折点应该在 [mid+1,right] 之间，因此执行 left = m+1。
2. 当 numbers[mid] < numbers[right] 时，mid 一定在右数组中（因为右数组是递增数组），此时转折点应该在 [left,mid] 之间，因此执行 right = mid。
3. 当 numbers[mid] = numbers[right] 时，无法判断 mid 在哪个数组中（因为可能在相同的元素中间断开，比如[3,3,1,3,3]），此时转折点应该在 [left,right]之间（为什么不是 [mid,right]: 因为可能根本就没有转折点，比如 [1,3,3]），此时中间元素已经很少了，直接遍历 [left,right] 即可。

4. 如果没有出现第三种情况，最终 left 应该指向 右数组的第一个元素，right 应该指向 左数组的最后一个元素。

   class Solution {
    public int findRes(int[] numbers,int left,int right){
        int min = numbers[left];
        for(int i=left+1;i<=right;i++){
            if(numbers[i]<min){
                min = numbers[i];
            }
        }
        return min;
    } //找到对应的最小值
   
    public int minArray(int[] numbers) {
        int left = 0,right = numbers.length-1,mid;
        while(left<=right){
            mid = left + (right-left)/2;
            if(numbers[mid] > numbers[right]){
                //最小元素在右数组中 [mid+1,right]
                left = mid+1;
            }else if(numbers[mid] < numbers[right]){
                //最小元素在左数组中 [left,mid] (mid也可能是对应的最小元素)
                right = mid;
            }else{ //出现了第三种情况
                return findRes(numbers,left,right); //返回数组的最小值
            }
        }
        return numbers[left]; //left位置是右数组第一个元素，返回numbers[left]
    }
   }
   

   剑指 Offer 12. 矩阵中的路径⭐

   本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。

   DFS

• 遍历矩阵，只要跟word的第一个字符相同，就开始对它进行dfs。
• 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j，当前已经匹配字符个数 k。
• 终止条件：

返回 false： 1. 行或列索引越界 2. 当前矩阵元素与目标字符不同 3. 当前矩阵元素已访问过。
返回 true ： k = word.length() - 1 ，即字符串 word 已全部匹配。

• 递推工作：

标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘’ ，代表此元素已访问过，防止之后搜索时重复访问，这样做的好处是省去了传入visit[][]参数来判断是否已经走过，在下一层递归里，board[i][j]始终是空字符串，但是回到该层递归时，还需要把board[i][j]还原。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，只要有一个方向能够达到题目要求即可。
还原当前矩阵元素： 将 board[i][j] 元素还原至初始值 。

剪枝

在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问(**在这里就是空字符串””**)），则应立即返回，称之为 可行性剪枝。

AC代码

    public boolean exist(char[][] board, String word) {
        int k = 0;
        //只要与第一个字符对应，那就开始dfs
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j] == word.charAt(0)){
                    //因为有多个dfs，因此不能永久性改变矩阵
                    if(dfs(board,i,j,word,k)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,int i,int j,String word,int k){
        if(i<0||i>board.length-1||j<0||j>board[0].length-1){ //越界的情况
            return false;
        }
        if(board[i][j] == word.charAt(k)){
            k++; //匹配个数+1
            board[i][j] = '/'; //临时赋予，表示已经访问过了，免去visit数组的开销
        }else{
            //不相等说明这条路走不通
            return false;
        }
        if(k == word.length()){ //全部匹配上了
            return true;
        }else{ //还没有全匹配，就要上下左右四个方向继续匹配了
            //有一条路走通就行
            boolean res = dfs(board,i+1,j,word,k) || dfs(board,i-1,j,word,k) || dfs(board,i,j+1,word,k) || dfs(board,i,j-1,word,k);

            //注意回到这一层递归的时候，需要还原字符，因为下一次dfs会用到这里的字符
            board[i][j] = word.charAt(k-1); 
            return res;
        }
    }

复杂度分析

剑指 Offer 13. 机器人的运动范围

首先是写出计算数位之和的算法：

    public int cal(int i,int j){
        int sum = 0;
        while(i != 0){
            sum += i%10;
            i /= 10;
        }
        while(j != 0){
            sum += j%10;
            j /= 10;
        }
        return sum;
    }

基本解法

首先就是最基本的dfs算法。我们需要分析出递归的出口，返回的结果，如何递归，满足条件的情况。
递归的出口：1. i 或 j 越过了边界。2. 该位置已经被访问过(visit数组对应为1，或者其他优化方法对应的示意)。3. 根据题目要求，当数位之和大于k时，也需要return。
满足条件的情况：因为本题跟上一题需要得到一个字符串不一样，它是计算有几个格子满足要求，因此只要没有进入递归出口，那就是满足条件的情况，不需要特殊代码。
如何递归：当没有进入递归出口时，说明条件满足，那么计数器 res 要加一，同时 res 还需要加上 递归 上下左右 四个方向 的结果。
返回的结果：返回 res 即可。

    public int dfs(int i,int j,int k,int[][] visit){
        if(i>m-1||i<0||j>n-1||j<0||cal(i,j)>k || visit[i][j] == 1){
            return 0;
        }
        visit[i][j] = 1; //标记为已访问过
        int res = dfs(i-1,j,k,visit) + dfs(i+1,j,k,visit) + dfs(i,j-1,k,visit) + dfs(i,j+1,k,visit) + 1; // 1对应的是 [i,j] 这个格子，其余的是上下左右四个方向的res
        return res;
    }

由于一次dfs方法就能把所有满足要求的格子全部找出，因此不需要用for循环了。

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        visit = new int[m][n];
        int count = 0;
        return dfs(0,0,k,visit);
    }

剑指 Offer 14- I. 剪绳子⭐

这题用数学证明太难了… 就用动态规划做吧。
用 dp[i] 表示长度为 i 的绳子，对应的最大乘积。很明显 dp[0] = 0, dp[1] = 1, dp[2] = 1（只能是 1*1）
从长度为3开始遍历，一直到n，对每个绳子从切割长度为2开始遍历（不从1开始遍历的原因是：切割长度为1时，对乘积没有任何帮助）
动态规划转移方程为：dp[i] = Math.max(dp[i], Math.max((j(i-j), jdp[i-j])。
对方程的分析：首先是剪了长度为 j 的情况，如果接下来不再剪了，那么对应乘积就是 j (i-j)。如果接下来还要剪，那么就是 j dp[i-j]（也就是剩下长度对应的最大乘积），取它们俩的较大值为a，进行下一轮比较。如果不减的话，那么对应的就是 dp[i]，记为b，取Math.max(a,b)。
最后 dp[n] 就是长度为n的绳子对应的最大乘积。

class Solution {
    public int cuttingRope(int n) {
        //dp[i] 表示长度为i的绳子，对应的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            for(int j=2;j<i;j++){
                //j是切割的长度，由于切割长度为1时对乘积没有帮助，因此从2开始
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

优化：对于剪绳子的情况，当 j = 2 以及当 j = n - 2的时候完全相同，也就是第二个for循环进行到一半其实就已经算完了（因为后一半和前一半完全对称）。

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            //这里减去的长度从1 到 i /2 就包含了所有的情况
            for(int j = 1; j <= i / 2; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 15. 二进制中1的个数

这道题主要是使用 >>> 进行移位，然后根据 n & 1判断第一位是否为1(如果是1的话，那么 n & 1的结果也为1，因为第一位为1，其余位都是0)。

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){ //当右移全部之后，n变成0
            res += n & 1;
            n >>>= 1; //每次右移一位
        }
        return res;
    }
}

剑指 Offer 16. 数值的整数次方⭐

如果我们正常计算一个数值的整数次方，比如 2 的九次方，那么我们需要乘九个2，时间复杂度为O(N)。这样做的话最终会导致超时。
但是我们根据十进制转化为二进制的公式：（b1,b2,…,bm 对应的都是1或0）
这样我们只需要乘 二级制个数 个2就可以了，时间复杂度为 O(logN)
那么我们首先需要知道 x^1, x^2, x^4, …, x^{2^{m-1}} 的值，这个在 while循环里只需要每次让 x *= x 即可。
假设最终结果为res，那么res是否要乘上 x^1 等数据，取决于 b1,b2…bm 是 0 还是 1，因此我们还需要知道 x^1 对应的 b1是多少，x ^2 对应的 b2 是多少…以此类推。这个我们可以根据 n & 1 == 1 ？ 来判断，并且每次 n>>>=1 （参考剑指Offer15）
还有一种特殊情况是：当 n = 负数的时候，比如 2 的 -5 次方，这时我们要取 b = -n(b为long，否则会越界)，同时取 x = 1/x。

class Solution {
    public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        long b = n;
        double res = 1.0;
        if(n < 0){
            x = 1/x;
            b = -b;
        }
        while(b != 0){
            if((b & 1) == 1){
                res *= x; //只有当 b = 1的时候，才执行相乘操作
            }
            x *= x; //但是不管 b是否等于1，我们都要进行x的递推工作(下一个循环就是下一位了)
            b >>>= 1;
        }
        return res;
    }
}

剑指 Offer 17. 打印从1到最大的n位数

基本解法

正常的话，就是算出来n位数最大的那个数（比如 n =3 的时候，算出来 999），然后用一个for循环给数组赋值即可。时间复杂度为 O(10^n)

class Solution {
    public int[] printNumbers(int n) {
        if(n==0){
            return new int[]{};
        }
        int t = 1;
        while(n!=0){
            t *= 10;
            n--;
        }
        //t对应的就是 最大数 + 1
        //t也可以通过 (int)Math.pow(10,n) 得到
        int[] arr = new int[t-1];
        for(int i=0;i<t-1;i++){
            arr[i] = i+1;
        }
        return arr;
    }
}

考虑大数的情况⭐

很明显这么简单的东西不能在面试上写，因此需要考虑一下大数的情况：无论是 short / int / long … 任意变量类型，数字的取值范围都是有限的。因此，大数的表示使用字符串 String 类型。
生成的列表实际上是 n 位 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表：先固定高位，然后固定下一位…以此类推，直到长度 == n。

但是这样做会产生两个问题：1. 应从1开始，而不是从0开始。2. 会出现 “01”,”02” 这样的情况，应该删除高位的0。
解决第一个问题的方法很简单，只要在 append 的时候判断一下是不是 “0” 即可，如果是的就不加入了。
解决第二个问题就需要确定一下字符串的左边界。我们可以用 start 来表示字符串的左边界。通过调用String.substring(start)方法可以截出[start,string.length()-1] 长度的字符串。
刚开始肯定是一位数，因此 start = n-1。那么我们根据什么来改变左边界呢？当 位数全都是 ‘9’ 的时候，说明要进位了 (比如 009, 099)，那么我们就需要让 start - 1，这个用 n - start == nine 来判断。nine是出现 ‘9’ 的个数。
举例：假设 n = 3。那么先从0开始，

class Solution {
    int[] res;
    //start表示该数字当前左边界，这个左边界意思是指当前数字最高位对应的char数组下标。如n=2时，1~9左边界为1，10~99左边界为0
    //nine表示当前数字中出现了多少个9，如果出现1个9，左边界就要向左移1位。例如第1次出现“9”是在9这个数字出现的时候，此时nine++变为1，
    //进入下次递归n为2，nine为1，start为1，此时start就要-1，以便统计二位数字
    int nine = 0, count = 0, start, n;   
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] printNumbers(int n) {
        this.n = n;
        //用来保存最终数字结果的
        res = new int[(int)Math.pow(10, n) - 1];   
        //num数组用来表示字符串，比如n等于2，则num数组为['0''0']、['0''1']、['0''2']...后边是将它转为字符串并按照左边界的位置进行截取的
        num = new char[n];  
        start = n - 1;  //最开始的左边界是从n-1，开始的，因为char数组的下标是从0开始，最末一位为n-1
        dfs(0);   //从char数组的第0位开始
        return res;
    }
    void dfs(int x) {
        //结束条件：当前x的下标越过char数组的最后一位下标n-1，此时记录结果
        if(x == n) {
            String s = String.valueOf(num).substring(start);   //从start开始截取字符串，如"01"截取后就是"1"
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);   //防止将"0"、"00"、"000"加进来
            if(n - start == nine) start--;   //n减去start等于nine，表示要进位了, start--
            return;
        }
        //给char数组第x位添加数字，添加完后进入下一位
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;   //回溯
    }
}

剑指 Offer 18. 删除链表的节点

较为简单的一题，主要就是生成一前一后两个指针，进入while循环，如果前指针碰到了题目所说的节点，那么后指针的next修改为 前指针的next即可。

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null){
            return null;
        }
        if(head.val == val){
            return head.next;
        }//特殊情况，头节点就是的话，直接返回 head.next 即可
        ListNode node1 = head;
        ListNode node2 = head.next;
        while(node2 != null){ //node2==null时说明没有题目所说的节点
            if(node2.val == val){
                node1.next = node2.next;
                break; //直接退出
            }
            //移动指针
            node1 = node1.next;
            node2 = node2.next; 
        }
        return head;
    }
}

剑指 Offer 19. 正则表达式匹配

剑指 Offer 20. 表示数值的字符串

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

可以使用双指针法，根据 不同情况进行处理。

class Solution {
    public int[] exchange(int[] nums) {
        //双指针
        int i = 0,j = nums.length-1;
        while(i<j){
            if(nums[i] % 2 == 0 && nums[j] % 2 != 0){ //偶在前，奇在后，交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
            else if(nums[i]%2!=0 && nums[j]%2==0){ //奇在前，偶在后，不用交换，同时移动
                i++;
                j--;
            }
            else if(nums[i]%2==0 && nums[j]%2==0){ //偶在前，偶在后，j位置合理，只用移动j
                j--;
            }
            else{ //奇在前，奇在后，i位置合理，只用移动i
                i++;
            }
        }
        return nums;
    }
}

剑指 Offer 22. 链表中倒数第k个节点

核心思想：快慢指针，一个t1指向头节点，一个t2向后走k个节点，然后让 t1 和 t2 同时移动，当t2为null时，t1对应的就是 倒数第k个节点。
时间复杂度为 O(N)

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //快慢指针，一个指向头节点，另外一个向前走k个节点
        ListNode node1 = head;
        ListNode node2 = head;
        while(k-- > 0){ //node2移动k个节点
            node2 = node2.next;
           //如果k还没到0的时候，node2就为null了，说明根本没有倒数第k个节点
            if(node2 == null && k != 0){ 
                return null;
            }
        }
        while(node2 != null){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
}

剑指 Offer 24. 反转链表

使用双指针法，每次进入while循环就生成一个临时节点，然后移动指针，再调整临时指针对应的next即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }
}

剑指 Offer 25. 合并两个排序的链表

由于初始状态合并链表中无节点，因此循环第一轮时无法将节点直接添加到合并链表中。解决方案：初始化一个辅助节点 dum 作为合并链表的伪头节点，将各节点添加至 dum 之后。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }
}

剑指 Offer 26. 树的子结构⭐

若树B是树A的子结构，则子结构的根节点可能为树A的任意一个节点。因此，判断树B是否是树A的子结构，需完成以下两步工作：

1. 先序遍历 树A 的每一个节点（对应 isSubStructure函数）。

2. 调用方法查看以该节点为根节点时，是否是 B树 的结构（对应 recur 函数）。

   isSubstructure函数

   

   recur函数

   

   class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //递归查看左子树是否有，右子树是否有
        if(A==null || B==null){
            return false;
        }
        //查看 以A为根节点是否是B的结构，判断完之后进行先序遍历
        return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
   
    //recur的作用：查看以A为根节点是否与B有相同结构
    public boolean recur(TreeNode A,TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null || A.val != B.val){
            return false;
        }
        //值相等的时候，还需要判断左右子树是否相同
        return fn(A.left,B.left) && fn(A.right,B.right);
    }
   }
   

   为什么不写成 return recur(A,B) || recur(A.left,B) || recur(A.right,B)：因为 recur 函数的作用是判断 以 A为根节点的树是否和B的结构相同。如果这样写的话，等于说只能判断三个节点，剩下的都无法判断了。

   剑指 Offer 27. 二叉树的镜像

   
   我们需要把每个根节点的左右根节点进行交换，也就是说，递归的原则是：先交换左侧根节点左右节点，再交换右侧根节点的左右节点，最后再通过自己的父节点把自己进行交换。也就是说，这是一个后序遍历。
   

   class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //递归交换左右子树
        exchange(root);
        return root;
    }
   
    public void exchange(TreeNode root){
        if(root == null){ //如果节点为空就退出
            return;
        }
        //如果是叶子节点也退出
        if(root.left == null && root.right == null){
            return;
        }
        //后序遍历
        exchange(root.left);
        exchange(root.right);
        //这个相当于 visit 函数,交换左右节点
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
    }
   }
   

   剑指 Offer 28. 对称的二叉树

   这道题和上一题不一样：上一题是从下往上开始判断，而这道题则是从上往下开始判断，因此使用的是先序遍历。
   递归的入口：fn(root.left,root.right)
   递归的参数：一个左节点，一个右节点。
   递归退出的条件：左节点和右节点都是空。既满足了对称条件，又不需要继续向下遍历了。
   递归失败的条件：左节点或右节点一个为空，一个不为空。或者两者值不相等。
   继续递归的条件：左节点和右节点值相等，返回 fn(left.left,right.right) && fn(left.right,right.left)，注意要保持镜像。

   class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return fn(root.left,root.right);
    }
   
    public boolean fn(TreeNode left,TreeNode right){
        if(left == null && right == null){ //递归出口
            return true;
        }
        //不满足的情况
        if(left == null || right == null || left.val != right.val){
            return false;
        }
   
        return fn(left.left,right.right) && fn(left.right,right.left);
    }
   }
   

   

   剑指 Offer 29. 顺时针打印矩阵⭐

   顺时针打印矩阵的顺序是一个循环：从左到右，从上到下，从右到左，从下到上。其中每次进行完一个环节，需要修改对应的边界，因此我们需要使用四个变量 left,right,top,bottom 来记录上下左右边界的变化。
   

   class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0){ //特殊情况处理
            return new int[]{};
        }
        int[] arr = new int[matrix.length * matrix[0].length];
        int k = 0;
        //上下左右边界的初始值
        int left = 0,right = matrix[0].length-1,bottom = matrix.length-1, top = 0;
        while(true){　//进入循环
            for(int i=left;i<=right;i++){ //从左到右
                arr[k++] = matrix[top][i];
            }
            top++; //上面一层遍历完毕，修改top的值
            if(top > bottom){ //判断是否达到结束条件
                break; 
            }
            for(int i=top;i<=bottom;i++){ //从上到下
                arr[k++] = matrix[i][right];
            }
            right--;//右边一层遍历完毕，修改right的值
            if(right < left){
                break;
            }
            for(int i=right;i>=left;i--){ //从右到左
                arr[k++] = matrix[bottom][i];
            }
            bottom--; //下面一层遍历完毕，修改bottom的值
            if(top > bottom){
                break;
            }
            for(int i=bottom;i>=top;i--){ //从下到上
                arr[k++] = matrix[i][left];
            }
            left++; //左边一层遍历完毕，修改left的值
            if(right < left){
                break;
            }
        }
        return arr;
    }
   }
   

   

   剑指 Offer 30. 包含min函数的栈

   我们需要设置两个栈：一个数据栈A，用于存储所有元素，调用push压入元素，pop弹出元素等正常函数。一个辅助栈B，栈A中的最小元素始终对应栈B的栈顶元素。
   

   class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        //如果x比A中所有元素都小或相等，那么就加入
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        //栈A弹出后，跟B的栈顶进行比较，如果相等，那么B也需要弹出
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        //弹出栈A的栈顶元素即可
        return A.peek();
    }
    public int min() {
        //弹出栈B的栈顶元素即可
        return B.peek();
    }
   }
   

   剑指 Offer 31. 栈的压入、弹出序列

   我们需要准备一个栈，按照pushed数组的顺序一个一个的插入 (直到数组遍历到末尾)，并且插入后我们需要比较插入元素是否与 poped数组的元素 (从索引为0开始)相等，如果相等，那么弹出栈中元素，继续比较栈顶元素和poped数组的下一个元素 … 直到不相等为止，进行下一个pushed插入。
   退出比较循环的条件有两个：1. 栈为空，已经比较不了栈顶元素和poped数组了。 2. 比较不相等。

   class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //先一直加入，直到 peek = popped
        Stack<Integer> s = new Stack();
        int k=0,t=0; //k是pushed数组索引指针，t是popped数组索引指针
        while(k != pushed.length){ //没有到末尾的时候就一直加入
            s.push(pushed[k++]);
            //进入比较poped数组的循环
            while(!s.isEmpty() && s.peek() == popped[t]){
                s.pop();
                t++;
            }
        }
        return s.isEmpty();
    }
   }
   

   如果最后栈里剩余的有元素，就说明poped数组不是弹出的序列，返回false。

   ⭐剑指 Offer 32 - I. 从上到下打印二叉树

   从左到右打印二叉树，也就是要进行层次遍历，即二叉树的BFS，常借用队列进行实现。
   

   class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) 
            return new int[0];
        //queue用于实现层次遍历
        Queue<TreeNode> queue = new LinkedList<>(){
        queue.add(root);
        //ans记录打印顺序
        ArrayList<Integer> ans = new ArrayList<>();
        //队列不空时一直循环
        while(!queue.isEmpty()) {
            //每次弹出一个节点
            TreeNode node = queue.poll();
            //在数组中记录节点的值
            ans.add(node.val);
            //左节点入队
            if(node.left != null) 
                queue.add(node.left);
            //右节点入队
            if(node.right != null) 
                queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
   }
   

   

   剑指 Offer 32 - II. 从上到下打印二叉树 II

   这个题相较于上一题就是多了一个要求：每一层要打印到一个数组中，最终结果为List>。
   
   整体还是采用层次遍历，只不过我们需要在while循环里多加入一个for循环，用于把当前层打印到一个临时的list中，然后对节点进行处理。

   class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) 
            queue.add(root);
        while(!queue.isEmpty()) {
            //tmp用于处理一行的数据
            List<Integer> tmp = new ArrayList<>();
            //for循环处理一行节点
            for(int i = queue.size(); i > 0; i--) {
                //每次弹出一个
                TreeNode node = queue.poll();
                tmp.add(node.val);
                //在for循环里加入node，保证下一次还是一行节点
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            //把一行的节点数据加入二维数组
            res.add(tmp);
        }
        return res;
    }
   }
   

   如何保证每次for循环就是一行：在for循环的过程中，就把下一行节点全部加入到队列中，而不是下一次while循环。这样保证每次for循环都是处理的完整一行节点。
   为什么 i 初始化为 queue.size()：因为queue.size()是会变化的。
   

   剑指 Offer 32 - III. 从上到下打印二叉树 III

   这次多了一个要判断奇偶的步骤：偶数行(从0开始数)正序输出，奇数行反序输出。那么我们在第二题的基础上，只需要判断一下当前行是奇还是偶就可以了。
   判断的方法，如果简单点的话可以设置一个变量row去记录。聪明点的话，可以用结果res的size去判断，如果res.size()是偶数，说明当前是奇数行，需要调用 Collections.reverse(tmp) 去逆转。

   class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            //用res.size()去判断奇偶
            if(res.size() % 2 == 1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
   }
   

   

   ⭐剑指 Offer 33. 二叉搜索树的后序遍历序列

   题目解析

   首先我们需要知道后根遍历的顺序：左、右、根，因此最后一个元素为二叉树的根。
   然后我们还需要知道二叉搜索树的定义：左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。
   我们可以通过递归来判断给出的数组是否为二叉搜索树的后序遍历序列 (判断所有子树的正确性)。

   递归策略

• 参数解析：1. 要传入整个数组。2. 传入左边界i 和右边界j，根节点索引就是j。
• 递归工作：
  • 划分左右子树：遍历 [i,j] 区间的元素，寻找 第一个大于根节点 的节点，索引记为m。此时，可划分出左子树空间为 [i,m-1]，右子树空间为 [m,j-1]。
  • 判断是否为二叉搜索树：
    • 左子树区间 [i,m-1] 内的所有节点都应 < postorder[j] (根节点的值)，这一点在划分左右子树时就已经保证过了，因此不用写代码。
    • 右子树区间 [m,j-1] 内的所有节点都应 > postorder[j]。可以通过遍历实现，当遇到 <= postorder[j]的节点则跳出，如果不是j，那么就返回false。
• 返回值：所有子树都需判断为二叉搜索树才能返回true，因此用 &&连接 —— 1. p == j，当前树是二叉平衡树。2. recur(i,m-1)，左子树是二叉搜索树。3. recur(m,j-1)，右子树是二叉搜索树。

• 终止条件：i >= j，说明此子树节点数量 <=1，直接返回true。

  class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //初始条件
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        //结束条件
        if(i >= j) 
            return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++; //寻找第一个大于根节点的元素
        int m = p; //分成左右子树 
        while(postorder[p] > postorder[j]) p++; //继续在右子树验证是否满足搜索树
        //如果p==j，说明当前树是二叉搜索树，接着判断左右子树
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
  }
  

  

  ⭐剑指 Offer 34. 二叉树中和为某一值的路径

  典型的二叉树方案搜索问题，使用回溯法解决。我们通过先序遍历来遍历整棵树。
  递归参数：根节点root，当前剩余值tar。
  路径加入条件：1. tar == 0。2. root为叶子节点。
  回溯方法：在向上层回溯时，我们需要删除这一层添加的节点，避免对上一层的下一次遍历产生影响。至于tar为什么不回溯：因为它是递归参数，每一层都记录有对应的tar，下层对它的修改是影响不到上层的。

  class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    //记录成功的列表
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) 
            return; //节点为空，直接返回
        path.add(root.val);
        tar -= root.val; //减去加入节点的值
        if(tar == 0 && root.left == null && root.right == null)
            //满足三个条件，就是一个满足题意的路径，加入res中
            res.add(new LinkedList(path));
  
        //向下递归
        recur(root.left, tar);
        recur(root.right, tar);
        //回溯，删除这一次递归加入的节点
        path.removeLast();
    }
  }
  

  注：为什么不直接把path加入到res中 —— 因为path是对象引用，可能会发生变化，因此需要new出一个新的LinkedList。
  

  ⭐剑指 Offer 35. 复杂链表的复制

  本题链表的节点新增了random指针，指向链表中的任意节点或者null。这个random指针意味着在复制过程中，除了构建节点的next，还要构建节点和其随机节点的引用指向random。
  刚开始的想法就是遍历链表，然后每次生成一个新结点，把对应的属性赋值，然后问题就出现了：如果简单的使用 a.random = b.random 去给新结点进行赋值，那么random指针指向的还是一个旧结点。

  哈希表

  我们可以使用一个哈希表，来构建旧结点和新结点之间的映射关系，然后就能以 node.random 为key，查找出新链表中对应的random节点。
  假设cur指向旧链表的节点，那么map.get(cur) 就是新链表对应节点，可以通过以下语句对新链表的节点的next域和random域进行赋值：

  map.get(cur).next = map.get(cur.next); //把旧链表的next赋给新链表的next
  map.get(cur).random = map.get(cur.random); //把旧链表的random赋给新链表的random
  

  class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) 
            return null; //如果头结点都是空，那么直接返回null
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //重新回到头结点
        cur = head;
        // 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 返回新链表的头节点
        return map.get(head);
    }
  }
  

  

  ⭐剑指 Offer 36. 二叉搜索树与双向链表

  从图中可以看出：我们要对二叉搜索树进行中序遍历。根据中序遍历的流程，我们首先写出dfs代码：
  
  其中第三步是对根节点的处理，保持 左、根、右 的顺序。
  注意主函数在处理完dfs后，还需要让头结点的pre指向尾结点，尾结点的next指向头结点。

  class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root); //构建链表主体，此时pre为尾结点
        //处理最后两个域
        head.left = pre; 
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null)  //结束条件
            return;
        dfs(cur.left);  //左
        if(pre != null) 
            pre.right = cur;
        else 
            //如果pre为空，说明当前节点为头节点
            head = cur;
        cur.left = pre;
        pre = cur; //更新pre
        dfs(cur.right); //右
    }
  }
  

  

  ⭐剑指 Offer 38. 字符串的排列

  排列方案的生成：根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第1位字符 (n种情况)、再固定第2位字符 (n-1 种情况)、… 、最后固定第n位字符(1种情况)。
  
  重复排列方案与剪枝：
  当字符串存在重复字符时，排列方案中也存在重复的排列方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次”，即遇到重复字符时不交换，直接跳过。从DFS角度看，此操作称为”剪枝”。 我们可以通过Set去排除重复的字母。
  同时我们在一层递归完毕后，还需要恢复字符的位置(回溯)，避免对上一层递归产生影响。
  
  递归分析：
  
  为了方便交换字符，我们使用toCharArray方法，把String换成char[]。

  class Solution {
    //存储可行的String
    List<String> res = new LinkedList<>();
    char[] c; //用数组方便交换字符
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        //调用toArray方法返回一个String数组
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) { //x表示当前拼接的长度
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        //set记录当前位已经固定过哪些字符了
        HashSet<Character> set = new HashSet<>();
        //开始遍历
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
  }
  

  

  剑指 Offer 39. 数组中出现次数超过一半的数字

  正常做法：数组排序后返回 nums[nums.length/2]。

  class Solution {
    public int majorityElement(int[] nums) {
        //排序之后，索引为nums/2位置必定是那个元素
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
  }
  

  还有一种特殊的方法，摩尔投票法：核心理念为 票数正负抵消。此方法时间和空间复杂度分别为O(N)和O(1)，为本题的最佳解法。
  假设出现次数超过一半的数字为x，数组长度为n，有以下推论：
  
  因此，我们可以随便假设某个数是超过一半的数字，只有最后存活的数字才是真正的答案。

  class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) 
                x = num; //更新当前假设的众数
            if(x == num){ //这里有一个巧妙的设计：当x刚更新时，votes也会变成1
                votes++;
            }else{
                votes--;
            }
        }
        return x;
    }
  }
  

  

  ⭐剑指 Offer 40. 最小的k个数

  对于TopK问题，我们不需要对数组进行完全的排序(Arrays.sort)，需要我们自己手写排序方法。

  快速排序

  我们可以先对数组进行快速排序，然后再对快速排序进行优化。
  快速排序算法有两个核心点，分别为 “哨兵划分” 和 “递归”。
  哨兵划分操作：以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
  递归：对左子数组和右子数组递归执行哨兵划分，直至子数组长度为1时终止递归，即可完成对整个数组的排序。
  
  在一次划分后，arr[i]为基准点，左数组为[l,i-1]，右数组为[i+1,r]。

  class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        //截取前k个
        return Arrays.copyOf(arr, k);
    }
    private void quickSort(int[] arr, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l, j = r;
        while (i < j) {
            //找到右侧第一个小于arr[l]的元素
            //注：为什么必须写 i<j，因此j可能一直满足，最终为-1，数组越界
            while (i < j && arr[j] >= arr[l]) j--;
            //找到左侧第一个大于arr[l]的元素
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        //把l位置与i位置进行交换，一次划分完成
        swap(arr, i, l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
  }
  

  注：下面两行代码互换会报错。

  while (i < j && arr[j] >= arr[l]) j--;
  while (i < j && arr[i] <= arr[l]) i++;
  

  文中的写法这两个 while 执行完，i j 同时指向一个小于 arr[l] 的数，因此需要执行 swap(arr,i,l)，可以把哨兵交换到正确的位置。而如果互换这两句，那么就是 i 先向右遍历，两个 while 执行完，i j 同时指向一个 大于 arr[l] 的数，那么就不对了。如果要交换写，那么同时也要把哨兵换成数组的末元素，让整个哨兵划分操作对称。
  比如：[5,2,3,6,7,8,9]，按照先调整j的顺序写，最终 i 和 j 都指向 3，操作正确。但是如果先调整 i，那么最终 i 和 j 都指向6，操作就发生错误。
  

  快速排序的优化

  题目只要求返回最小的k个数，对这k个数的顺序并没有要求。因此，只需要将数组划分为最小的k个数和其他数字两部分即可，而快速排序的哨兵划分可完成此目标。
  根据快速排序原理，如果某次哨兵划分后基准数正好是第 k＋1 小的数字，那么此时基准数左边的所有数字便是题目所求的最小的 k 个数。
  因此我们需要给递归添加一个判断内容，判断 k 和当前基准点 i 之间的关系：

1. 若 k = i，则arr[k]为第k+1小的数字，直接返回数组的前k个元素即可。
2. 若 k < i，则第 k+1 小的数字在左数组中，需要递归左数组。

3. 若 k > i，则第 k+1 小的数字在右数组中，需要递归右数组 (左数组的已经全部都需要了，不需要再排)。

   class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length)
            return arr; //特殊情况
        return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
   }
   

   

   大顶堆的应用

   可以使用Java默认提供的堆结构来实现，因为我们需要的是大顶堆，而Java提供的是小顶堆，因此我们需要传入比较器。

   // 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
   // 1. 若目前堆容量小于K，将当前数字放入堆中，顶端一直维持着最大值。
   // 2. 如果已经超过了容量k 那么判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
   //    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
   class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
   
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
   }
   

   剑指 Offer 42. 连续子数组的最大和

   使用动态规划：假设dp[i]表示以元素nums[i]为结尾的连续子数组最大和。这样做主要是保证连续性，如果不以nums[i]为结尾，那么很有可能就不是连续的子数组了(比如跳过了中间的一个负数)。
   转移方程：
   即 dp[i] = Math.max(dp[i-1] + nums[i],nums[i])。主要看的是dp[i-1]做的是正贡献还是负贡献。

   class Solution {
    public int maxSubArray(int[] nums) {
        //动态规划,dp[i]记录 i位置的最大子数组和
        int[] dp = new int[nums.length];
        int max = nums[0]; //初始化max
        dp[0] = nums[0]; //初始化dp[0]
        for(int i=1;i<nums.length;i++){
            //转移方程
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>max){
                //修改max
                max = dp[i];
            }
        }
        return max;
    }
   }
   

   降低空间复杂度：由于 dp[i] 只与 dp[i−1] 和 nums[i] 有关系，因此可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。此时空间复杂度为O(1)
   此时nums[i]就对应着dp[i]。

   class Solution {
    public int maxSubArray(int[] nums) {
        //降低空间复杂度
        int max = nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i-1] > 0){
                //dp[i-1]是正收益，修改nums[i]
                nums[i] += nums[i-1];
            }
            //修改max
            max = Math.max(max,nums[i]);
        }
        return max;
    }
   }
   

   剑指 Offer 44. 数字序列中某一位的数字

   ⭐剑指 Offer 45. 把数组排成最小的数

   这道题需要用到比较特殊的排序：字符串排序，排序规则为：
   在Java中，调用(A+B).compareTo(B+A) 就可以完成上述比较。

   自带的sort

   class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        //传入一个比较器，对数组进行排序
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        //最后组合在一起输出即可
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
   }
   

   快速排序

   面试的时候可能不让使用 Arrays.sort，因此我们也可以使用快速排序来实现。只不过内部的两个while需要着重分析：
   由于我们在一次quickSort后，想要得到的目标是：在 l 和 i 交换后，l 的左边都是小于它的，l的右边都是大于它的。把这个理论结合题目，那就是：左边的元素(strings[i]) + strings[l] <= strings[l] + 左边的元素，strings[l] + 右边的元素(strings[j]) <= 右边的元素 + strings[l]。这样才符合要求，注意要先调整右边。

   class Solution {
    public String minNumber(int[] nums) {
        //转化为字符串数组
        String[] strings = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            strings[i] = String.valueOf(nums[i]);
        }
        quickSort(strings,0,strings.length-1);
        //数组排完序后直接拼接即可
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<strings.length;i++){
            sb.append(strings[i]);
        }
        return sb.toString();
    }
   
    public void quickSort(String[] strings,int l,int r){
        //初始时以nums[l]为哨兵
        if(l >= r){
            return;
        }
        int i = l,j = r;
        while(i < j){
            //注：必须把j放在第一
            while(i<j && (strings[l]+strings[j]).compareTo(strings[j]+strings[l])<=0)
            j--;
            while(i<j && (strings[i]+strings[l]).compareTo(strings[l]+strings[i])<=0)
            i++;
            swap(strings,i,j);
        }
        //交换l和i对应内容
        swap(strings,l,i);
        quickSort(strings,l,i-1);
        quickSort(strings,i+1,r);
    }
   
    public void swap(String[] strings,int i,int j){
        String tmp = strings[i];
        strings[i] = strings[j];
        strings[j] = tmp;
    }
   }
   

   

   ⭐剑指 Offer 46. 把数字翻译成字符串

   我们可以使用动态规划解决，核心思想就是根据数字连在一起能不能被翻译来决定转移方程。
   
   注意 01，02这种情况也是不可以翻译的。
   初始状态：dp[0] = 1，dp[1] = 1，即无数字和第一位数字的翻译情况都是一种。
   

   字符串遍历

• 可以将数字num转换为字符串s，遍历s实现动态规划。
• 通过对字符串进行分割 [i-2,i-1] 获取数字组合，比对ASCII码。
• 空间使用优化：由于dp[i] 只和 dp[i-1] 与 dp[i-2] 有关，因此可以使用两个变量 a,b 分别记录 dp[i-1] 和 dp[i-2]，两变量交替前进即可。

  class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        //初始化dp[0]和dp[1]
        int a = 1,b = 1;
        //从索引为1开始(0已经被初始化为1了)
        for(int i = 1;i < s.length();i++){
            //划分字符串
            String tmp = s.substring(i-1,i+1);
            //判断是否能翻译，如果可以，dp[i] = dp[i-1] + dp[i-2]
            int c = tmp.compareTo("10")>=0 && tmp.compareTo("25")<=0 ?a+b:b;
            //更新dp[i-1]和dp[i-2]
            a = b;
            b = c;
        }
        return b;
    }
  }
  

  

  数字求余

  使用字符串会占用额外的空间复杂度，我们也可以使用数字求余的方式得到对应的两位数。
  注：数字求余是从右往左开始的，但是根据此题动态规划的对称性，这样也没有问题。

  class Solution {
    public int translateNum(int num) {
        //y初始化为最后一位
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
  }
  

  

  剑指 Offer 47. 礼物的最大价值

  这道题用dfs会超时，因此我们可以尝试使用动态规划。dp[i][j]表示在(i,j)坐标上能拿到的最大价值。由于dp[i][j]只与dp[i-1][j]，dp[i][j-1]，grid[i][j]有关系，因此可以将原矩阵grid用作dp矩阵。
  

  class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) continue;
                //第一行的礼物
                if(i == 0) grid[i][j] += grid[i][j - 1] ;
                //第一列礼物
                else if(j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
  }
  

  还可以进一步优化：由于第一行和第一列都属于特殊情况，我们可以先把它们初始化，这样就不需要多次判断了。

  class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) 
                //注意是 +=，自己的也要算上去
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
  }
  

  

  ⭐剑指 Offer 48. 最长不含重复字符的子字符串

  整体思想

  使用动态规划，dp[j] 表示以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。
  转移方程：设字符 s[j] 左边距离最近的相同字符为 s[i]。

1. 当 i < 0时，说明 s[j] 左边没有相同字符，则 dp[j] = dp[j-1] + 1。
2. 当 i > 0时，我们就需要判断 s[i] 是否在dp[j-1]这个子字符串中。如果不在，那么 s[j] 就可以加入到子字符串dp[j-1]中。如果在，那么就不能使用dp[j-1]的长度了，dp[j] 为 j - i (从s[i]后的字符到s[j]的距离)。
   1. 当 dp[j-1] == j - i 时，此时子字符串 dp[j-1]的第一个字符就是 s[i]，这是 s[j] 刚好不能加入的临界点，此时dp[j] = dp[j-1] = j - i。
   2. 当 dp[j-1] > j - i 时，s[i] 在子字符串dp[j-1]中，最终dp[j]的长度为 j - i。
   3. 当 dp[j-1] < j - i 时，s[i] 不在子字符串dp[j-1]中，s[j] 可以加入子字符串中，最终长度为 dp[j-1] + 1

最终的转移方程为：

空间复杂度优化：由于只需要最大值，那么我们可以用tmp存储dp[j]，res存储最大值。

使用哈希表

使用哈希表得到离s[j]最近的相同字符s[i]。
注：哈希表的 getOrDefault(key,default) 方法：代表当前哈希表包含键 key 时返回对应 value，不包含时返回默认值 default。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 得到相同字符的位置
            dic.put(s.charAt(j), j); // 更新哈希表
            //由于第一种已经被合并，因此不需要单独判断 j == -1 的情况
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

比较好理解的代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //s[j]为当前字符，s[i]为前面第一个和s[j]相同的字符
        HashMap<Character,Integer> map = new HashMap<>();//记录字符出现的位置
        if(s.length() == 0){
            return 0;
        }
        //tmp=dp[0]
        int tmp = 0,max = 1;
        for(int j=0;j<s.length();j++){
            int i = map.getOrDefault(s.charAt(j),-1);
            if(i == -1){
                //没出现过，可以直接添加
                tmp++;
            }else{
                if(j-i>tmp){
                    //dp[j-1]里没有出现chars[i]
                    tmp++;
                }else{
                    //dp[j-1]里出现了chars[i]
                    tmp = j - i; //以chars[j]结尾的字串长度
                }
            }
            map.put(s.charAt(j),j);
            if(max < tmp)
                max = tmp;
        }
        return max;
    }
}

⭐剑指 Offer 49. 丑数

在已有的丑数序列上每一个数都必须乘2， 乘3， 乘5， 这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, …, n1, n2]，如果单纯的让每个丑数乘2， 乘3， 乘5顺序排列的话肯定会有问题，因为前面乘5之后的数据，可能比后面乘2的数据要大 (比如25 和 32)。
因此，我们需要知道每个丑数是否已经被乘2，乘3以及乘5了。
设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如 a 表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数。b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数。c表示前 (c-1) 个数都已经乘过一次5了，下次应该乘5的是第 c 个数。
因此，下一个丑数一定是从第 a 个数乘2， 第 b 个数乘3， 第 c 个数乘5中获得，他们三者最小的那个就是下个丑数。
求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2，乘3还是乘5得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，所以a++，其余同理。
注：如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5，说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b 都应该加一。

class Solution {
    public int nthUglyNumber(int n) {
        //指示已经乘2，乘3，乘5的丑数索引
        int a = 0, b = 0, c = 0;
        //dp[i]表示索引为i的丑数的值
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            //得到对应的数
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            //其中最小的数是下一个丑数
            dp[i] = Math.min(Math.min(n2, n3), n5);
            //看看该丑数是根据乘2，乘3还是乘5得到的，注意如果有相同的那么索引都+1
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

剑指 Offer 50. 第一个只出现一次的字符

用哈希表记录字符是否出现一次以上，只要出现一次以上就设置为 false。最后再次遍历哈希表，返回value为true的字符。

剑指 Offer 52. 两个链表的第一个公共节点

使用Set集合

先从一条链表开始遍历，把遍历的节点全部加入到Set中，当headA = null时退出。然后遍历另外一条链表，当出现相同的节点时，返回。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        //指针指向的位置相同
        Set<ListNode> set = new HashSet<>();//记录一个链表遍历的结点
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

遍历法⭐

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1 = headA;
        ListNode head2 = headB;
        while(head1 != head2){
            if(head1 == null){
                head1 = headB;
            }else{
                head1 = head1.next;
            }
            if(head2 == null){
                head2 = headA;
            }else{
                head2 = head2.next;
            }
        }
        return head1;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

排序数组里的查找问题，首先就应该想到使用二分法来解决。本题要求统计数字target 的出现次数，可转化为：使用二分法分别找到左边界left和右边界right，易得数字target 的数量为right - left - 1。

正常的二分查找法是查找数组里是否有某个数，那么我们就不能用普通的二分查找，而需要使用二分查找来查找边界。我们可以返回target的右边界（第一个大于target数的索引）和target-1的右边界，然后相减就可以得到对应的元素个数。
找到某个数右边界的函数：

    public int findRight(int[] nums,int target){
        int low = 0,high = nums.length-1,mid;
        while(low <= high){
            mid = (low+high)/2;
            if(nums[mid] <= target){
                //向右边找
                low = mid + 1; //low最终位置在重复元素的右边
            }else{
                high = mid - 1;
            }
        }
        return low;
    }

由于我们需要返回右边界，因此while循环的退出条件应该是 low == high + 1，即 while(low<= high)，此时low对应的就是target的右边界。
另外一个必须要注意的地方：当nums[mid] == target 的时候，我们不需要返回数值，因为我们需要的是右边界。这时候做的操作是 low = mid + 1，继续往右边搜索，直到找到第一个比target大的元素。

class Solution {
    public int search(int[] nums, int target) {
        return findRight(nums,target) - findRight(nums,target-1);
    }
    public int findRight(int[] nums,int target){
        int low = 0,high = nums.length-1,mid;
        while(low<=high){
            mid = (low+high)/2;
            if(nums[mid] <= target){
                //向右边找
                low = mid + 1; //low最终位置在重复元素的右边
            }else{
                high = mid - 1;
            }
        }
        return low;
    }
}

查找左边界和右边界的代码我们可以背一下：

public int findRight(int[] nums,int target){
    int i = 0, j = nums.length - 1;
    while(i <= j) {
        int m = (i + j) / 2;
        if(nums[m] <= target) i = m + 1;
        else j = m - 1;
    }
    int right = i;
    return right;
}

public int findLeft(int[] nums,int target){
    int i = 0; j = nums.length - 1;
    while(i <= j) {
        int m = (i + j) / 2;
        if(nums[m] < target) i = m + 1;
        //这次是相等时调整左边界
        else j = m - 1;
    }
    int left = j;
    return left;
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

依然是递增排序数组，我们还是通过二分法去做。
但是这个题跟其它的二分法不是很一样，它没有明确要查找的 target 或者左边界，右边界等，而是数组的中间有一个断点。
我们可以根据这个断点把数组分为两部分：左数组和右数组，然后我们可以发现，左数组的所有元素的值都和他们的索引相同，而右数组则不是。
因此，我们可以用 值是否与索引相同 这一点来判断是左数组还是右数组。而根据题目要求，我们需要返回右数组的第一个元素的索引，它就是缺失的元素。

最终 left 应该对应的 右数组的第一个元素，而 right 应该对应左数组的最后一个元素。

当 nums[m] == m时，m位于左数组中，说明右数组第一个元素在 [m+1 , j] 中，执行 i = m+1。
当 nums[m] != m时，m位于右数组中，说明左数组最后一个元素在 [i , m-1]中，执行 j = m-1。

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        //i为右数组第一个元素，返回索引即可
        return i;
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

使用反向中序遍历法。
已知：二叉搜索树的中序遍历是递增序列。因此，二叉搜索树的反向中序遍历（右，根，左）是递减序列。故第k大节点就是 反向中序遍历的第k个节点。

// 打印中序遍历倒序
void dfs(TreeNode root) {
    if(root == null) return;
    dfs(root.right); // 右
    System.out.println(root.val); // 根
    dfs(root.left); // 左
}

class Solution {
    public int k,res;
    public int kthLargest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        this.k = k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        //如果root为null 或者 k已经为0，那么就不需要继续递归了
        if(root == null || k == 0){ 
            return;
        }
        dfs(root.right); //右
        k--; //计数器减一
        if(k == 0){ //如果计数器为0，说明当前节点就是第k个节点
            res = root.val;
        } 
        dfs(root.left); //左
    }
}

剑指 Offer 55 - I. 二叉树的深度

DFS

树的深度 = 左子树的深度 与 右子树的深度 中的较大值 + 1。(+1是加上本层)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

BFS

使用队列完成，每遍历一层则计数器加一，直到队列为空。使用类似 剑指Offer 32中，用for循环遍历每一层的方法来完成。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) 
            return 0;
        List<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<TreeNode> tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            //tmp用于存储下一层的节点
            tmp = new LinkedList<>();
            for(TreeNode node : queue) { //操作本层节点
                if(node.left != null) 
                    tmp.add(node.left);  //加入左节点
                if(node.right != null) 
                    tmp.add(node.right); //加入右节点
            }
            queue = tmp;
            res++; //层数加一
        }
        return res;
    }
}

剑指 Offer 55 - II. 平衡二叉树

先序(后序)遍历 + 剪枝

思路是对二叉树做先序遍历(或者后序遍历)，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
递归函数：

• 返回值：
  • 当左右子树深度差 <= 1，则返回当前子树的深度。
  • 当左右子树深度差 > 1，则返回-1，代表当前子树不是平衡树 (也就意味着整棵树都不是平衡树)。

class Solution {
    public boolean isBalanced(TreeNode root) {
        //如果返回的是-1，那么就是false
        int res = recur(root);
        if(res == -1){
            return false;
        }else{
            return true;
        }
    }

    private int recur(TreeNode root) {
        if (root == null)
            return 0; //结束条件
        int left = recur(root.left); //左
        if(left == -1) 
            return -1;
        int right = recur(root.right); //右
        if(right == -1) 
            return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

⭐剑指 Offer 56 - I. 数组中数字出现的次数、

基本介绍

由于要求时间复杂度为 O(N)，空间复杂度为 O(1)，因此直接排除暴力遍历法和哈希表法。
这道题需要使用 异或 进行计算：两个相同数字异或为 0，即对于任意整数 a有 a ^ a = 0 。因此，若将 nums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 x
同时，x ^ 0 = x
但是问题在于，本题有两个出现一次的数字，因此无法直接通过亦或来得到x和y。但是我们可以根据 x 和 y 的第一个二进制不同的数字 把数组分成两半，分别进行亦或，最后输出 [x,y] 即可。
注：我们所需要做的就是把x和y分开，并不需要把数组均分为两半，因此只要找到 x和y 第一个不一样的二进制位，不需要管其他相同的数。

算法流程

1. 对nums遍历异或：nums = [a,a,b,b,…,x,y]，最终异或结果为 x ^ y。
2. 接下来就开始找x和y第一个不一样的二进制位：根据异或运算定义，若 x^y 的某二进制位为1，那么 x 和 y的此二进制位一定不同，故我们要获取的就是x^y的首位1。假设 x^y = a，有——

因此可以初始化一个辅助变量m=1，从右往左循环判断，获取整数 x^y 的首位1，注意是使用&。

while(a & m == 0) // m 循环左移一位，直到 a & m ！= 0
    m <<= 1

1. 拆分nums为两个数组，在拆分的过程中进行异或。

通过遍历数组，每个数跟 m 进行异或运算，x和y与m做异或运算肯定不相等，然后根据是否等于零分成两个数组即可，分出来一个异或一个，最终就可以得到x和y。

for(int num: nums) {
    if((num & m) != 0) x ^= num;  // 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或
    else y ^= num;                // 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或
}
return new int[] {x, y};          // 遍历异或完毕，返回只出现一次的数字 x 和 y

1. 返回数组[x,y]即可。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int m = 1,n = 0,x = 0,y = 0;
        for(int num : nums){ //1.数组整体异或，得到x^y
            n ^= num; //最终n的值为x^y (注意是要返回的x和y)
        }
        //2.得到x和y第一个不一样的二进制位
        while((n&m) == 0){ //直到出现不相同的位
            m<<=1; //左移进行下一位判断
        }
        for(int num : nums){
            if((num & m) == 0){
                x^=num;
            }else{
                y^=num;
            }
        }
        return new int[]{x,y};
    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II

剑指 Offer 57. 和为s的两个数字

双指针法即可。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i < j) {
            int s = nums[i] + nums[j];
            if(s < target) i++; //需要更大，左指针向右移动
            else if(s > target) j--; //需要更小，右指针向左移动
            else return new int[] { nums[i], nums[j] }; //返回
        }
        return new int[0];
    }
}

**

⭐剑指 Offer 57 - II. 和为s的连续正数序列

使用 滑动窗口 解决这道题目。
滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。
滑动窗口的左边界和右边界只能向右边移动。

算法流程：

1. 初始化窗口：将左边界初始化为1 (根据值来的，因此跟索引没关系)，右边界初始化为2，和 res 初始化为3。
2. 进入while循环，当 i>=j的时候退出。
3. 当结果res 等于 target 的时候，需要把窗口生成一个数组，对应数组长度为 j-i+1，这里需要注意的是，当list加入数组后，还需要开启下一层(不然就会一直相等)，具体做法就是 res 减去左边界的值，然后左边界向右移动。
4. 然后是结果大于target时，需要移动左边界。结果小于target时，需要移动右边界，注意是先移动再加。

5. 最后使用list的toArray方法返回一个二维数组即可。

   class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int i=1,j=2,res=3; //i为左边界，j为右边界
        while(i < j){
            if(res == target){
                //数组长度为 j-i+1
                int[] arr = new int[j-i+1];
                for(int k=i;k<=j;k++){
                    arr[k-i] = k;
                }
                list.add(arr);
                //开启下一层
                res -= i;
                i++; 
            }
            else if(res > target){
                res-=i;
                i++;
            }else{
                j++;
                res+=j;
            }
        }
        return list.toArray(new int[0][]);
    }
   }
   

   

   剑指 Offer 58 - I. 翻转单词顺序

   难度正常的一题，我们可以通过 双指针法 和 分割拼接法 两种方法来做。

   双指针法

   倒序遍历字符串s，记录单词左右索引边界 i,j (其中 i 指向单词左边第一个空格，j 指向单词末尾)。每确定一个边界，就用 substring方法 把它添加到单词列表res。注意单词之间可能不止一个空格，因此需要加上一步跳过空格。

   class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
   }
   

   

   分割+拼接

   这里需要说明一个问题，使用split分割字符串时，若两单词间有 x > 1 个空格，则在单词列表 strs 中，这两个单词间会多出 x - 1个空字符串 (“”) 。如下图所示：最终分割为了 [hello,,,world]。
   因此在分割后，我们需要倒序遍历进行拼接。

   class Solution {
    public String reverseWords(String s) {
        String str = s.trim();
        String[] strs = str.split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空字符串则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
   }
   

   

   剑指 Offer 58 - II. 左旋转字符串

   很简单，不管是用 substring 切割字符串也好，StringBuffer也好，都可以做到。这里提供一个比较基础的方法：辅助数组法。

   class Solution {
    public String reverseLeftWords(String s, int n) {
        //辅助数组
        int count=0;
        char[] ss = new char[s.length()];
        for(int i=n;i<s.length();i++){
            ss[count++] = s.charAt(i);
        }
        for(int i=0;i<n;i++){
            ss[count++] = s.charAt(i);
        }
        return new String(ss,0,count);
    }
   }
   

   剑指 Offer 59 - II. 队列的最大值

   感谢解答区答主 腐烂的橘子 提供的动图。
   虽然本题与 剑指Offer 30 包含min函数的栈 有些相同，但是本质却完全不一样。min栈可以直接根据压入的元素是否小于辅助栈的栈顶元素来更新辅助栈栈顶，因为先压入的元素一定会先出，不会对后面的元素产生影响。
   但是队列却不行，如下面动图所示，如果只根据入队元素来改变最大值：
   
   
   可以发现，在最大值4出队后，明明还有最大值3，但是已经没有最大值记录了。因此，我们需要根据队列的性质：先进先出，来确定一种方法 —— 由于后面入队的元素一定比先入队的元素晚出去，因此我们只需要在辅助栈中，把比后入队元素小的元素全部出队，然后再让该元素入队即可。

    public void push_back(int value) {
        //对于辅助队列，添加时如果没有大于尾元素，那么直接添加
        //如果大于尾元素，那么一个一个出队，直到没有比尾元素大
        while(!list1.isEmpty() && list1.peekLast() < value){
            //如果小于，则删除 (根据队列的特性)
            //等于不删除，因为还用得上
            list1.removeLast();
        }
        list1.add(value);
        list2.add(value);
    }
   

   
   而出队的操作就比较正常了，就是判断一下出队元素是否是辅助队列的头元素即可，注意要先判断队列是否为空。

   class MaxQueue {
    //辅助队列，队列头保持最大元素
    LinkedList<Integer> list1;
    LinkedList<Integer> list2;
   
    public MaxQueue() {
        list1 = new LinkedList<>();
        list2 = new LinkedList<>();
    }
   
    public int max_value() {
        if(list1.isEmpty()){
            return -1;
        }
        return list1.peek();
    }
   
    public void push_back(int value) {
        //对于辅助队列，添加时如果没有大于尾元素，那么直接添加
        //如果大于尾元素，那么一个一个出队，直到没有比尾元素大
        while(!list1.isEmpty() && list1.peekLast() < value){
            //如果小于，则删除 (根据队列的特性)
            //等于不删除，因为还用得上
            list1.removeLast();
        }
        list1.add(value);
        list2.add(value);
    }
   
    public int pop_front() {
        //看看普通队列出队元素是否与头结点相同即可
        if(list2.isEmpty()){
            return -1;
        }
        int res = list2.poll();
        if(!list1.isEmpty() && res == list1.peek()){
            list1.poll();
        }
        return res;
    }
   }
   

   ⭐⭐剑指 Offer 60. n个骰子的点数

   做这道题之前，我们必须先计算出一个数据：
   n 个骰子的点数和的范围是 [n , 6n]，当n个骰子全为1时，对应的是n，全为6时对应的是6n，因此总共有 6n - n + 1 = 5n + 1 个数。
   可以发现，如果使用暴力破解法，也就是需要统计n个骰子的所有点数组合，总共是 6的n次方 种。也就是说，时间复杂度为 O(6^N)

   动态规划

   假设二维数组 dp[i][j] 代表 i 个骰子的点数和为 j 的概率，那么我们可以通过动态规划推出 dp[i][j]。

        for(int i = 2;i <= n;i++){
            for(int j = i;j <= i*6;j++){
                for(int k = 1;k <= 6;k++){
                    if(j - k > 0)
                        dp[i][j] += dp[i-1][j-k]/6;
                    else
                        break;
                }
            }
        }
   

   i 代表当前骰子的个数，j 代表当前 i个骰子的点数和，而k则代表了 在dp[i-1][…] 基础上 新增加的那个骰子 (也就是第i个骰子) 投出的数字。
   当 k = 1 时，如果想要达到点数和为 j，那么对应前 i-1 个骰子的总点数需要为 j-1，当 k = 2时，如果想要达到点数和为 j，那么对应前 i-1 个骰子的总点数需要为 j-2 …… 以此类推，前 i-1 个骰子对应的点数和为 j-k。
   由于总共有六种情况（新增加的骰子投出1~6），因此需要在累加的概率和上 除以6。这就是 dp[i][j]的概率。
   同时我们需要注意，如果出现 j - k<0的情况，比如说我们想要的点数和为2，结果新加入的骰子却投出了6这种情况，我们则需要跳过这个k。

由于我们最终要的是 n 个骰子对应的情况，即 dp[n][n1 ~ n6] 之间的数据 (n个骰子的数据范围)：

        for(int j = n;j <= 6*n;j++){
            res[j-n] = dp[n][j];
        }

同时，我们还需要做初始化工作，即当 n = 1时，所有的点数和概率都是 1.0/6.0 (必须用浮点数)，这个是动态规划的基石。
根据之前的计算，最终结果为 5n-1 个数，这也是res数组的长度。同时最大只会有n个骰子，最大数是 6n，因此动态规划数组分别开空间为 n+1，n6+1 (因为是从1开始的)

        double res[] = new double[n*5+1]; //记录结果
        double dp[][] = new double[n+1][n*6+1]; //动态规划数组
        for(int j = 1;j <= 6;j++){
            dp[1][j] = 1.0/6;
        }

class Solution {
    public double[] dicesProbability(int n) {
        //总共 5*n+1 种组合
        double[] res = new double[5*n+1];
        //i表示 i个骰子 j表示 点数和，从1开始数
        double[][] dp = new double[n+1][6*n+1];
        //初始化：dp[1][1~6] 对应的概率都是 1.0/6.0
        for(int j = 1;j<=6;j++){
            dp[1][j] = 1.0/6.0;
        }
        //开始动态规划
        for(int i = 2;i<=n;i++){
            //从骰子数量为2开始，数量为n结束
            for(int j=i;j<=6*i;j++){
                //骰子点数和最小为i，最大为6*i
                for(int k=1;k<=6;k++){
                    //从第i个骰子点数为1开始，为6结束
                    if(j - k > 0){
                        //dp[i-1][j-k]就是缺的那一部分
                        dp[i][j] += dp[i-1][j-k]/6;
                    }else{
                        //超出界限，直接退出这轮k循环
                        break;
                    }
                }
            }
        }
        for(int j=n;j<=6*n;j++){
            //n个骰子，最小点数和为n，最大点数和为6*n
            res[j-n] = dp[n][j];
        }
        return res;
    }
}

⭐剑指 Offer 61. 扑克牌中的顺子

这道题主要就是一个证明：
即：

第一个条件可以使用Set遍历判重，同时在遍历的过程中，可以记录数组的最大值和最小值（除了大小王），然后看是否满足第二个条件。

class Solution {
    public boolean isStraight(int[] nums) {
        int max = 1,min = 14; //注意大小别反了，刚开始min是最大的
        Set<Integer> repeat = new HashSet<>(); 
        for(int num:nums){
            if(num == 0){ //跳过大小王
                continue;
            }
            if(repeat.contains(num)){
                //第一个条件不满足
                return false;
            }
            max = Math.max(num,max);
            min = Math.min(num,min);
            repeat.add(num);
        }
        if(max - min >= 5){ //第二个条件不满足
            return false;
        }
        return true;
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

即约瑟夫环问题，对于这个问题，我们可以使用模拟链表法，也可以使用数学方法解决。

模拟链表

注意只能使用 ArrayList，不能使用 LinkedList，原因是 ArrayList 的remove方法稍微快一点，刚好满足题目要求。
假设 idx 为当前索引，那么递推公式为：idx = (idx + m - 1)%n 。

class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            //递推公式
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}

数学解法

暂时先不管吧。

剑指 Offer 63. 股票的最大利润

使用动态规划即可。我们在算最大利润时，需要参考前几天的最小值，因此需要专门记录一下。然后就是参考以前的最大利润。因此状态转移方程为：dp[i] = Math.max(prices[i] - min, dp[i-1])。是当天股价减去最小值大，还是以前的利润大。
dp[i] 就表示当前的最大利润。dp[0] = 0，第一天的利润肯定为0。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0){ //特殊判断
            return 0;
        }
        //用动态规划做
        int[] dp = new int[prices.length];
        int min = prices[0]; //记录出现过的最小值
        dp[0] = 0; //初始化
        for(int i = 1;i<prices.length;i++){
            if(min > prices[i])
                min = prices[i];
            dp[i] = Math.max(prices[i]-min,dp[i-1]);
        }
        return dp[prices.length-1];
    }
}

由于只需要最后一天的dp值，因此可以用一个变量来记录，从而减小空间复杂度。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        //节省空间复杂度
        int min = prices[0];
        int res = 0; //dp[0]
        for(int i = 0;i<prices.length;i++){
            if(min>prices[i])
                min = prices[i];
            res = Math.max(prices[i]-min,res);
        }
        return res;
    }
}

⭐剑指 Offer 64. 求1+2+…+n

由于加了种种限制，因此只能使用递归的方法(不需要使用for循环)，但是递归的出口需要使用 if 判断，我们需要写一个替代语句。

public int sumNums(int n) {
    if(n == 1) return 1;
    n += sumNums(n - 1);
    return n;
}

我们会使用到 逻辑运算符的短路效应。

if(A && B)  // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false

if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

由于递归的条件是 n > 1，因此这个可以作为短路的条件，与递归语句结合在一起。递归语句改写成条件判断语句 (后面加一个 > 0)。

class Solution {
    int res = 0;
    public int sumNums(int n) {
        boolean x = n > 1 && sumNums(n - 1) > 0;
        res += n;
        return res;
    }
}

⭐剑指 Offer 65. 不用加减乘除做加法

考察位运算，这道题的主要难点就是怎么用位运算还原加法。假设二进制 s = a + b，则有以下四种情况：
(i 为二进制的第几位)
可以看出，无进位的情况，与 a(i) && b(i) 相同，而进位的情况则与 a(i) ^ b(i) 相同 (但需要左移一位)。
得到公式： 因此 s = a + b = n + c。

class Solution {
    public int add(int a, int b) {
        int n = a ^ b;
        int c = (a & b) << 1;
        return n + c;
    }
}

但是这很明显也不可以，因为使用到了加号。因此，我们需要将 n 或者 c 变化为0，从而直接返回另一个数即可。
我们可以通过一直重复 且运算和异或运算 (因为重复以上过程对两个数相加的结果没有变化，相当于要把 1+1 变成 2 + 0，只要输出那个2就可以)，直到 进位和 为0，此时只要输出 非进位和 即可。

class Solution {
    public int add(int a, int b) {
        int n,c;
        while(b!=0){
            c = (a & b)<<1; //进位和
            n = a ^ b; //非进位和
            a = n; // a始终保持为非进位和
            b = c; // b始终保持为进位和
        }
        return a; //最终b为0，输出非进位和 即a
    }
}

剑指 Offer 66. 构建乘积数组

这道题的难点就在于不能使用除法。因此如果想求得数组B，需要通过别的方法。
根据 B[i] 的公式，列出表格，可以发现能分为 上三角 和 下三角 两部分：

因此，我们可以使用两个数组 left 和 right，记录 上三角(左边) 和 下三角(右边) 每一行的值，最后 b[i] = left[i] * right[i]。

1. 从上到下，左边是：left[0] ~ left[a.length-1]，其中 left[0] = 1，left[a.length-1] = a[n-1] * a[n-2] … a[1] a[0]。
2. 右边是：right[0] ~ right[a.length-1]，其中 right[0] = a[n] a[n-1] … a[2] a[1]，right[a.length-1] = 1。

3. res[i] = left[i] * right[i]。

   class Solution {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length]; //结果数组
        if(a == null || a.length == 0){
            return a; //特殊情况
        }
        int[] left = new int[a.length]; //左三角
        int[] right = new int[a.length]; //右三角
        left[0] = 1;
        right[a.length - 1] = 1;
        for(int i = 1;i<a.length;i++){
            //记录左边三角的值 (可以代入 left[1] = a[0] * left[0] 检验)
            left[i] = a[i-1] * left[i-1];
        }
        for(int i = a.length - 2;i>=0;i--){
            //记录右边三角的值，注意是正好反过来的
            right[i] = a[i+1] * right[i+1];
        }
        for(int i = 0;i<a.length;i++){
            //最终结果
            res[i] = left[i] * right[i];
        }
        return res;
    }
   }
   

   剑指 Offer 67. 把字符串转换成整数

   这道题主要就麻烦在如何判断溢出上。

   判断溢出

   我们可以设置一个边界 b = Integer.MAX_VALUE / 10。总共有两种情况可能越界：

4. res > b，说明下面的数字已经不能继续加上去了（此时chars[i] 还没处理），只能返回溢出值。

5. res == b && chars[i] > ‘7’。由于 整型的最大值为 2147483647，最小值为 -2147483648，因此只要出现当前位超过7的情况，就可以判定为溢出 (没必要单独判断符号位了，因为即使是负数可以接受的 8，返回的也是 Integer.MIN_VALUE)。

符号处理

判断溢出外，我们还需要对符号进行处理，一共有以下几种：

1. 首部空格：删除即可。

2. 符号位：总共有 “+” “-“ 以及 无符号 三种情况，需要使用一个变量来记录一下符号，同时在累加时需要跳过符号位。

        if(chars[i] == '-'){
            i = 1; //跳过负号，从索引为1开始
            sign = -1;
        }else if(chars[i] == '+'){
            i = 1;
            sign = 1;
        }else if(chars[i]>='0' && chars[i]<='9'){
            i = 0;
            sign = 1;
        }else{
            //不是数字
            return 0;
        }
   

3. 非数字字符：遇到即返回。

4. 数字字符：累加。

   class Solution {
    public int strToInt(String str) {
        //2^31 = 2147483648 = Integer.MAX_VALUE -1  
        int res = 0;
        int i = 0; //从第几位开始
        int sign; //标记一下是正数还是负数
        int b = Integer.MAX_VALUE/10; //边界
        char[] chars = str.trim().toCharArray();
        if(chars.length == 0){
            return 0;
        }
        if(chars[i] == '-'){
            i++; //跳过负号，从索引为1开始
            sign = -1;
        }else if(chars[i] == '+'){
            i++;
            sign = 1;
        }else if(chars[i]>='0' && chars[i]<='9'){
            sign = 1;
        }else{
            //不是数字
            return 0;
        }
        for(;i<chars.length;i++){
            if(chars[i]<'0'||chars[i]>'9'){
                //中途出现符号，直接返回即可
                return sign == -1?-res:res;
            }
            if(res > b || (res == b && chars[i]>'7')){
                return sign==-1?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            res = res * 10 + chars[i] - '0';
        }
        return sign == -1?-res:res;
    }
   }
   

   
   当然，我们也可以不适用 trim 方法，这样就能降低时间复杂度和空间复杂度。

        while(str.charAt(i) == ' '){
            i++;
            if(i == str.length()){ //防止越界
                return 0;
            }
        }
   

   class Solution {
    public int strToInt(String str) {
        if(str.length() == 0){
            return 0;
        }
        int res = 0;
        int i = 0; //从第几位开始
        int sign; //标记一下是正数还是负数
        int b = Integer.MAX_VALUE/10; //边界
        while(str.charAt(i) == ' '){
            i++;
            if(i == str.length()){
                return 0;
            }
        }
        if(str.charAt(i) == '-'){
            i++; //跳过负号
            sign = -1;
        }else if(str.charAt(i) == '+'){
            i++;
            sign = 1;
        }else if(str.charAt(i)>='0' && str.charAt(i)<='9'){
            sign = 1;
        }else{
            //不是数字
            return 0;
        }
        for(;i<str.length();i++){
            if(str.charAt(i)<'0'||str.charAt(i)>'9'){
                //中途出现符号，直接返回即可
                return sign == -1?-res:res;
            }
            if(res > b || (res == b && str.charAt(i)>'7')){
                return sign==-1?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            res = res * 10 + str.charAt(i) - '0';
        }
        return sign == -1?-res:res;
    }
   }
   

   剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

   迭代法

   找到两节点的公共祖先总共有三种情况：

5. p 和 q 分别在 root 的两侧。

6. p 是 root，q在左子树或者右子树上，此时公共祖先为 root。
7. q 是 root，q在左子树或者右子树上，此时公共祖先为 root。

因此，我们必须排除 p和q 都不是root，并且他们俩都在同一侧的情况。这样的情况有：

1. p.val < root.val，q.val < root.val，此时需要向左子树寻找。

2. p.val > root.val，q.val > root.val，此时需要向右子树寻找。

   class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)
            return null;
        while(root != null){
            if(p.val < root.val && q.val < root.val){
                //去左子树找
                root = root.left;
            }else if(p.val > root.val && q.val > root.val){
                //去右子树找
                root = root.right;
            }else{ //包含了可以得到结果的三种情况
                break;
            }
        }
        return root;
    }
   }
   

   递归法

   目的就是 当两节点在同一侧时一直递归，直到找出 p和q 不同侧时对应的 root 节点 (不同侧也包括 p = root 或者 q = root)。

   class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val)
            //公共祖先节点在右子树上
            return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val)
            //公共祖先节点在左子树上
            return lowestCommonAncestor(root.left, p, q);
   
        //此时的root就是公共祖先
        return root; //其他情况返回root
    }
   }
   

   剑指 Offer 68 - II. 二叉树的最近公共祖先

   上一题可以使用 迭代法 以及 递归法可以直接判断 p 和 q是否位于两侧 的原因是：二叉树是二叉搜索树，可以根据值直接判断两个节点对应的位置关系。
   现在不是二叉搜索树了，我们只能通过 先序遍历(或者别的遍历) 来推出 p 和 q 的位置关系。

3. 递归的出口：当 root = null 或者 root = p 或者 root = q 时，返回 root。因此方法的作用就是返回 p 或 q 的节点。

4. 递归：得到左子树是否有 p 或 q，以及 右子树是否有 p 或 q。

        if(root == null || root == p || root == q) 
            return root; //根 
        TreeNode left = lowestCommonAncestor(root.left, p, q); //左
        TreeNode right = lowestCommonAncestor(root.right, p, q); //右
   

5. 返回值：一共有四种情况：

   1. left 和 right 同时为空，说明 root 的 左右子树 中都不包含 p，q，返回null。
   2. left 和 right 同时不为空，说明 p 和 q 在root两侧，此时root就是最近的公共祖先，返回root。
   3. right 为空，left 不为空，说明 p 和 q 都在root的左子树里，有两种情况：1. p 是 q 的子节点(假设) ，此时返回的就是 p。2. p 和 q 在其他节点的两侧，那么就返回该节点，即最近公共祖先 (如下图所示)。 因此直接返回 root 即可。

建议去题解里看看动图演示。

1. left 为空，right 不为空，同理。

   class Solution {
   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     if(root == null || root == p || root == q)
         return root;
     TreeNode left = lowestCommonAncestor(root.left,p,q); //p或q在左子树的位置
     TreeNode right = lowestCommonAncestor(root.right,p,q);//p或q在右子树的位置
     //以下就是四种返回情况
     if(left == null && right == null)
         return null; 
     else if(left == null && right != null)
         return right;
     else if(left != null && right == null)
         return left;
     else
         return root;
   }
   }