【吐血整理】LeetCode与剑指Offer百道经典题解总结

小灰灰 2023-07-07 08:52 17阅读 0赞

**本文整理了LeetCode与剑指Offer中百余道经典的题目，整理出了数组、字符串、链表、二叉树、栈、回溯、动态规划、位运算中的经典问题以及问题对应的链接地址和个人提供的题解，方便查阅以及练习。以下是百题的索引，点击即可找到题目的出处并练习，也可直接查阅答案。**

**建议刚开始刷题的朋友直接按一下的Tag分类一个专题一个专题地进行学习与作答，完全理解这一百题，一线大厂非你莫属。**

### 文章目录 ###

*   *   *  一.数组 & 字符串 & 双指针
         *   *  1.两数之和
             *  2.三数之和
             *  3.顺时针打印矩阵
             *  4.构建乘积数组
             *  5.约瑟夫环问题
             *  6.左旋转字符串
             *  7.丑数判断
             *  8.第N个丑数
             *  9.调整数组使奇数位于偶数前面
             *  10.替换空格
             *  11.实现pow函数
             *  12.实现sqrt函数「int和double」
             *  13.旋转打印二维数组
             *  14.二维数组的查找
             *  15.数字中超过一半的数字
             *  16.盛最多水的容器
             *  17.删除数组重复项
             *  18.在排序数组中寻找第一个和最后一个
             *  19.旋转图像
             *  20.最大子序和
             *  21.接雨水
             *  22.颜色分类
             *  23.杨辉三角
             *  24.和为k的子数组
             *  25.求众数
             *  26.返回数据流中第k大元素
             *  27.滑动窗口最大值
             *  28.数据流的中位数
             *  29.滑动窗口中位数
             *  30.子数组最大平均数
             *  31.有效字母异位词
             *  32.翻转单词序列
             *  33.无重复字符的最长子串
             *  34.七进制转化
         *  二.位运算
         *   *  1.位1的个数
             *  2.2的幂
             *  3.只出现一次的数字
             *  4.只出现一次的数字2
         *  三.回溯
         *   *  1.全排列
             *  2.组合总数
             *  3.N皇后问题
             *  4.复原IP地址
             *  5.括号生成
             *  6.岛屿数量
             *  7.正则表达式匹配
             *  8.单词搜索
         *  四.动态规划
         *   *  1.买卖股票最佳时机
             *  2.买卖股票最佳时机含冷冻期
             *  3.买卖股票最佳时机含手续费
             *  4.不同路径
             *  5.最长回文子串
             *  6.编辑距离「二维dp」
             *  7.最长公共子序列「二维dp」
             *  8.最长上升子序列
             *  9.换钱最少货币数
             *  10.矩阵最小路径和
             *  11.龙与地下城
             *  12.打家劫舍
             *  13.剪绳子
             *  14.爬楼梯
             *  15.单词拆分
             *  16.丑数2
             *  17.完全平方数
             *  18.三角形最小路径和
             *  19.乘积最大子序列
         *  五.二叉树
         *   *  1.前序和后序重建二叉树
             *  2.序列化反序列化二叉树
             *  3.二叉树的子结构
             *  4.二叉树镜像
             *  5.从上往下打印二叉树
             *  6.验证二叉搜索树的后序遍历序列
             *  7.二叉搜索树转化双向链表
             *  8.平衡二叉树校验
             *  9.二叉树的深度
             *  10.二叉树的中序下一节点
             *  11.之字形打印二叉树
             *  12.有序数组转化二叉搜索树
             *  13.路径总和
             *  14.二叉搜索树第k小节点
             *  15.找树左下角的值
             *  16.最长同值路径（节点间最长路径）
             *  17.二叉树最近公共祖先
             *  18.二叉搜索树最近公共祖先
             *  19.二叉树的右视图
             *  20.左叶子之和
         *  六.链表
         *   *  1.反转链表
             *  2.反转局部链表
             *  3.删除链表重复节点
             *  4.链表中环的入口
             *  5.链表是否有环
             *  6.相交链表公共节点
             *  7.复杂链表的复制
             *  8.合并两个有序链表
             *  9.删除链表倒数第k个节点
             *  10.两数相加
             *  11.将有序链表转化为二叉搜索树
         *  七.栈
         *   *  1.用两个栈实现队列
             *  2.含有getMin的栈
             *  3.有效括号
             *  4.下一个更大元素
             *  5.每日温度
             *  6.验证栈序列
             *  7.最长有效括号
         *  八.其他
         *   *  1.36进制的加法与整形转化
             *  2.（SQL）排名排序
             *  3.（SQL）第二高的薪水

### 一.数组 & 字符串 & 双指针 ###

#### 1.两数之和 ####

https://leetcode-cn.com/problems/two-sum

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            // 使用HashMap优化暴力搜索，时间复杂度O（n），空间复杂度O（n）
            int[] res = new int[2];
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) { 
                int cur = nums[i];
                int need = target - cur;
                if (map.containsKey(need)) { 
                    res[0] = i;
                    res[1] = map.get(need);
                    break;
                } else { 
                    map.put(cur, i);
                }
            }
            return res;
        }
    }

#### 2.三数之和 ####

https://leetcode-cn.com/problems/3sum

class Solution { 
        /* 思路是现将nums排序，然后确定k为第一个数，再确定k左边的数left以及数组最右边的数right，让后面这两个数形成对撞指针，当sum < 0时，说明left太小，让left右移；若sum > 0，则说明right太大，right--； */
        public List<List<Integer>> threeSum(int[] nums) { 
            int n = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums); // 先将nums排序
            for (int k = 0; k < n; k++) { 
                // 当前数字已经大于0，那么之后的数子在相加也不可能等于0，结束程序
                if (nums[k] > 0) { 
                    break;
                }   
                // 跳过重复结果
                if (k > 0 && nums[k] == nums[k - 1]) { 
                    continue;
                }
                // 定义左右指针
                int left = k + 1, right = n - 1;      
                // 不断地缩小范围
                while (left < right) { 
                    // sum为总和
                    int sum = nums[k] + nums[left] + nums[right];
                    if (sum < 0) { 
                        left++;
                    } else if (sum > 0) { 
                        right--;
                    } else { 
                        // sum == 0，记录当前结果
                        res.add(Arrays.asList(nums[k], nums[left], nums[right]));
                        // 避免记录重复结果
                        while (left + 1 < right && nums[left + 1] == nums[left]) { 
                            left++;
                        }
                        while (left < right - 1 && nums[right] == nums[right - 1]) { 
                            right--;
                        }
                        // 缩小窗口
                        left++;
                        right--;
                    }
                }
            }
            return res;
        }
    }

#### 3.顺时针打印矩阵 ####

https://leetcode-cn.com/problems/spiral-matrix

class Solution { 
        /* 记录上下左右四个指针用来标识矩阵 */
        public List<Integer> spiralOrder(int[][] matrix) { 
            List<Integer> res = new ArrayList<>();
            int rows = matrix.length;
            if (rows == 0) { 
                return res;
            }
            int cols = matrix[0].length;
            // 左、右、上、下指针
            int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
            while (left <= right && top <= bottom) { 
                // 从左到右收集
                for (int i = left; i <= right; i++) { 
                    res.add(matrix[top][i]);
                }
                // 从上到下收集
                for (int i = top + 1; i <= bottom; i++) { 
                    res.add(matrix[i][right]);
                }
                // 从右到左收集(需要防止第一次收集过)
                if (top != bottom) { 
                    for (int i = right - 1; i >= left; i--) { 
                        res.add(matrix[bottom][i]);
                    }
                }
                // 从下到上收集(需要防止第二次收集过)
                if (left != right) { 
                    for (int i = bottom - 1; i >= top + 1; i--) { 
                        res.add(matrix[i][left]);
                    }
                }
                // 收集完一圈，缩小矩阵
                left++;
                right--;
                top++;
                bottom--;
            }
            return res;
        }
    }

#### 4.构建乘积数组 ####

https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=11204&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

import java.util.ArrayList;
    import java.util.HashMap;
    
    public class Solution { 
        /* 画图可知，每个区域对应的下三角已经上三角的区域 */
        public int[] multiply(int[] A) { 
            int length = A.length;
            int[] B = new int[length];
            if(length != 0 ){ 
                B[0] = 1;
                //计算下三角连乘
                for(int i = 1; i < length; i++){ 
                    B[i] = B[i-1] * A[i-1];
                }
                int temp = 1;
                //计算上三角
                for(int j = length-2; j >= 0; j--){ 
                    temp *= A[j+1];
                    B[j] *= temp;
                }
            }
            return B;
        }
    }

#### 5.约瑟夫环问题 ####

https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
    public int LastRemaining_Solution(int n, int m) { 
        // 约瑟夫环
        if (n == 0) { 
            // 当前没有人参与
            return -1;
        }
        if (n == 1) { 
            // 剩余该人生还，索引为0
            return 0;
        }
        // 约瑟夫环递推公式:f(n, m) = (f(n - 1, m) + m) % n
        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
    }
    
    public class Solution { 
    /* 使用链表来模拟这一淘汰过程 */
    public int LastRemaining_Solution(int n, int m) { 
        if (n <= 0 || m <= 0) { 
            return -1;
        }
        ArrayList<Integer> list = new ArrayList<>();
        // 先将数组添加到链表中
        for (int i = 0; i < n; i++) { 
            list.add(i);
        }
        // 初始化索引-1
        int index = -1;
        // 当幸存者大于1时，进行淘汰
        while (list.size() > 1) { 
            // 计算出需要淘汰的索引
            index = (index + m) % list.size();
            list.remove(index);
            // 记得让索引自减，以达下一轮的目标
            index--;
        }
        // 只剩一个元素时就是幸存者
        return list.get(0);
        }
    }

#### 6.左旋转字符串 ####

https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 首先反转整体字符串，然后反转前半部分，再反转后半部分即可 */
        public String LeftRotateString(String str,int n) { 
            if (str == null || str.length() == 0) { 
                return str;
            }
            // 分三部分反转即可
            int len = str.length();
            n = n % str.length();
            // 反转全部
            char[] chars = str.toCharArray();
            reverse(chars, 0, len - 1);
            // 反转第一部分
            reverse(chars, 0, len - n - 1);
            // 反转第二部分
            reverse(chars, len - n, len - 1);
            return new String(chars);
        }
        
        /* * 反转left到right之间的字符 */
        private void reverse(char[] chars, int left, int right) { 
            while (left < right) { 
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
    }

#### 7.丑数判断 ####

https://leetcode-cn.com/problems/ugly-number

class Solution { 
        /* 依次除以2、3、5，然后判断最后为不为1即可知是否为丑数 */
        public boolean isUgly(int num) { 
            if (num <= 0) { 
                return false;
            }
            while (num % 2 == 0) { 
                num /= 2;
            }
            while (num % 3 == 0) { 
                num /= 3;
            }
            while (num % 5 == 0) { 
                num /= 5;
            }
            return num == 1;
        }
    }

#### 8.第N个丑数 ####

https://leetcode-cn.com/problems/ugly-number-ii

class Solution { 
        /* 使用dp存储第n个丑数，定义p2、p3、p5分别指向dp中的第n个2、3、5类型的丑树，每次选出一个最小值用于作为当前的丑数*/
        public int nthUglyNumber(int n) { 
            if (n < 1) { 
                throw new RuntimeException("n不可小于1");
            }
            int[] dp = new int[n];
            dp[0] = 1;
            int p2 = 0, p3 = 0, p5 =0;
            for (int i = 1; i < n; i++) { 
                // 获取丑数队列的最小值作为下一个丑数
                int min = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
                // 将符合条件的丑数索引递增
                if (min == dp[p2] * 2) { 
                    p2++;
                }
                if (min == dp[p3] * 3) { 
                    p3++;
                }
                if (min == dp[p5] * 5) { 
                    p5++;
                }
                // 设置最小值为当前丑数
                dp[i] = min;
            }
            return dp[n - 1];
        }
    }

#### 9.调整数组使奇数位于偶数前面 ####

https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
         /* 使用插入排序，原地交换，能保证最后结果的有序性 */
         public void reOrderArray(int [] A) { 
            if (A == null) { 
                throw new RuntimeException("数组不能为空");
            }
            int cur = 0; // cur表示当前奇数的末尾
            for (int i = 0; i < A.length; i++) { 
                // 为奇数时，往前交换，直到遇到cur
                int temp = i;
                if (A[temp] % 2 == 1) { 
                    while (temp > cur) { 
                        swap(A, temp, temp - 1);
                        temp--;
                    }
                    cur++;//奇数位后移
                }
            }
        }
        private void swap(int[] nums, int i, int j) { 
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
     }

#### 10.替换空格 ####

https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&tqId=11155&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 统计空格数然后加上字符数创建一个新的字符数组，再从头到尾填充，最后转化为字符串 */
        public String replaceSpace(StringBuffer str) { 
            char[] chars = str.toString().toCharArray();
            // 统计空格数和非空格数
            int spaceCount = 0, charCount = 0;
            for (int i = 0; i < chars.length; i++) { 
                if (chars[i] == ' ') { 
                    spaceCount++;
                } else { 
                    charCount++;
                }
            }
            // 计算最终所需长度
            int len = charCount + 3 * spaceCount;
            // 声明新数组
            char[] res = new char[len];
            int index1 = 0, index2 = 0;
            while (index1 < res.length && index2 < chars.length) { 
                if (chars[index2] != ' ') { 
                    res[index1++] = chars[index2++];
                } else { 
                    // 遇到了空格，插入%20
                    char[] aux = new char[]{ '%', '2', '0'};
                    for (char c:aux) { 
                        res[index1++] = c;
                    }
                    index2++;
                }
            }
            return new String(res);
        }
    }

#### 11.实现pow函数 ####

https://leetcode-cn.com/problems/powx-n

class Solution { 
        /* 思路是将a^n递归拆分为a^(n/2)*a^(n/2) 「针对n为偶数情况」 * 或拆分为a^(n/2)*a^(n/2)*a *「针对n为奇数的情况」，最后再考虑符号 */
        public double myPow(double x, long n) { 
            // 边界条件
            if (n == 0) { 
                return 1.0;
            }
            // 递归终止条件，当n==1或-1时返回x或1/x
            if (n == 1 || n == - 1) { 
                return (n == 1) ? x : 1 / x;
            }
            // 递归拆分： a^b = a^(b/2) * a^(b/2) （b为偶数）
            // 递归拆分： a^b = a^(b/2) * a^(b/2) * a （b为奇数）
            long temp = Math.abs(n);
            double res = myPow(x, temp / 2);
            if (temp % 2 == 0) { 
                // 偶数次幂
                res *= res;
            } else { 
                // 奇数次幂
                res *= res * x;
            }
            // 是否为正数次幂
            if (n >= 0) { 
                return res;
            } else { 
                return 1 / res;
            }
        }
    }

#### 12.实现sqrt函数「int和double」 ####

https://leetcode-cn.com/problems/sqrtx

class Solution { 
        /* 夹逼法，int型，无需精度,舍弃小数点，只保留整数 */
        public int mySqrt(int x) { 
            // 使用夹逼定理，一直缩小区间逼近
            long left = 0, right = x, mid = left + (right - left) / 2;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                if (mid*mid == x || mid*mid < x && (mid+1)*(mid+1) > x) { 
                    break;
                }
                if (mid*mid < x) { 
                    // 向右区间逼近
                    left = mid + 1;
                } else { 
                    // 向左区间逼近
                    right = mid - 1;
                }
            }
            return (int)mid;
        }
        
        /* 夹逼法，double型，需讨论精度 */
        public double mySqrt(double x) { 
            // 使用夹逼定理，一直缩小区间逼近,附带精度校验
            double precision = 0.001;
            double left = 0.0, right = x, mid = left + (right - left) / 2;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                // 符合精度要求
                if (Math.abs(mid*mid - x) <= precision) { 
                    break;
                }
                if (mid*mid < x) { 
                    // 向右区间逼近
                    left = mid + precision;
                } else { 
                    // 向左区间逼近
                    right = mid - precision;
                }
            }
            return mid;
        }
    }

#### 13.旋转打印二维数组 ####

https://leetcode-cn.com/problems/spiral-matrix

class Solution { 
        /* 定义上下左右四个指针即可 */
        public List<Integer> spiralOrder(int[][] matrix) { 
            List<Integer> res = new ArrayList<>();
            int rows = matrix.length;
            if (rows == 0) { 
                return res;
            }
            int cols = matrix[0].length;
            int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
            while (left <= right && top <= bottom) { 
                // 从左到右收集
                for (int i = left; i <= right; i++) { 
                    res.add(matrix[top][i]);
                }
                // 从上到下收集
                for (int i = top + 1; i <= bottom; i++) { 
                    res.add(matrix[i][right]);
                }
                // 从右到左收集(需要防止第一次收集过)
                if (top != bottom) { 
                    for (int i = right - 1; i >= left; i--) { 
                        res.add(matrix[bottom][i]);
                    }
                }
                // 从下到上收集(需要防止第二次收集过)
                if (left != right) { 
                    for (int i = bottom - 1; i >= top + 1; i--) { 
                        res.add(matrix[i][left]);
                    }
                }
                // 收集完一圈
                left++;
                right--;
                top++;
                bottom--;
            }
            return res;
        }
    }

#### 14.二维数组的查找 ####

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 在左下角开始寻找，若小于target，则往右寻找，若大于target，则往上寻找 */
        public boolean Find(int target, int [][] array) { 
            if (array.length == 0) { 
                return false;
            }
            int rows = array.length;
            int cols = array[0].length;
            int i = rows - 1, j = 0;
            while (i >= 0 && j < cols) { 
                if (array[i][j] < target) { 
                    // 需要更大的数，往右侧走
                    j++;
                } else if (array[i][j] > target) { 
                    // 需要更小的数，往上走
                    i--;
                } else { 
                    return true;
                }
            }
            return false;
        }
    }

#### 15.数字中超过一半的数字 ####

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
    
        /* 利用快排的partition函数,时间复杂度为O（nlogn） */
        public int MoreThanHalfNum_Solution(int [] array) { 
            if (array.length == 0) { 
                return 0;
            }
             if (array.length == 1) { 
                return array[0];
             }
            int left = 0, right = array.length - 1, mid = left + (right - left)/2;
            int index = partition(array, left, right);
            while (index != mid) { 
                if (index < mid) { 
                    // 需要在index的右边继续寻找,并且进行排序
                    index = partition(array, index + 1, right);
                } else { 
                    // 需要在index的左边继续寻找,并且进行排序
                    index = partition(array, left, index - 1);
                }
            }
            // 确定该数字出现是否超过了一半[若该数字出现超过半数，那么该数左边和右边都应该和它相等]
            if (array[index - 1] != array[index] || array[index] != array[index + 1]) { 
                return 0;
            }
            return array[index];
        }
        private int partition(int[] array, int left, int right) { 
            // 选取base
            int base = array[left];
            int i = left, j = right;
            while (i < j) { 
                while (i < j && array[j] >= base) { 
                    j--;
                }
                while (i < j && array[i] <= base) { 
                    i++;
                }
                // 交换i, j
                swap(array, i, j);
            }
            // i, j相重合
            swap(array, left, i);
            return i;
        }
        private void swap(int[] array, int i, int j) { 
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

#### 16.盛最多水的容器 ####

https://leetcode-cn.com/problems/container-with-most-water

class Solution { 
        /* 对撞指针法，时间复杂度O（n） */
        public int maxArea(int[] height) { 
            if (height == null) { 
                throw new RuntimeException("input cant be null");
            }
            int left = 0, right = height.length - 1, res = 0;
            while (left < right) { 
                // 比较当前的面积和之前的面积哪个更大
                res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
                // 不断地移动短板才有可能扩大面积
                if (height[left] <= height[right]) { 
                    left++;
                } else { 
                    right--;
                }
            }
            return res;
        }
    }

#### 17.删除数组重复项 ####

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

class Solution { 
    /* 数组重复项最多为2个，返回删除后的长度 */
    public int removeDuplicates(int[] nums) { 
            int n = nums.length;
            if (n <= 2) { 
                return n;
            }
            int cur = 1; // 直接从第2个元素开始考虑
            // 从第3个元素开始考虑重复项
            for (int i = 2; i < n; i++) { 
                // 当当前元素不等于cur-1位置的元素，说明没有两个以上重复项，cur继续往右走并交换
                if (nums[i] != nums[cur - 1]) { 
                    nums[++cur] = nums[i];
                }
            }
            // 返回最后的长度
            return cur + 1;
        }
    }

#### 18.在排序数组中寻找第一个和最后一个 ####

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

class Solution { 
        /* 使用二分搜索获取第一个和最后一个元素，时间复杂度O（logn） */
        public int[] searchRange(int[] nums, int target) { 
            if (nums == null) { 
                throw new RuntimeException("input cant be null");
            }
            int[] res = { -1, -1};
            res[0] = getBegin(nums, target);
            res[1] = getEnd(nums, target);
            return res;
        }
        private int getBegin(int[] array, int k) { 
            int left = 0,right = array.length - 1;
            while (left <= right) { 
                int mid = left + (right - left) / 2;
                if (array[mid] < k) { 
                    // 搜索右边
                    left = mid + 1;
                } else if (array[mid] > k) { 
                    // 搜索左边
                    right = mid - 1;
                } else { 
                    // 获取到第一个出现的位置
                    if (mid == 0 || array[mid - 1] != array[mid]) { 
                        return mid;
                    } else { 
                        // 继续往左搜索
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
         private int getEnd(int[] array, int k) { 
             int left = 0,right = array.length - 1;
              while (left <= right) { 
                int mid = left + (right - left) / 2;
                if (array[mid] < k) { 
                    // 搜索右边
                    left = mid + 1;
                } else if (array[mid] > k) { 
                    // 搜索左边
                    right = mid - 1;
                } else { 
                    // 获取到最后一个出现的位置
                    if (mid == array.length -1 || array[mid + 1] != array[mid]) { 
                        return mid;
                    } else { 
                        // 继续往右搜索
                        left = mid + 1;
                    }
                }
            }
             return -1;
        }
    }

#### 19.旋转图像 ####

https://leetcode-cn.com/problems/rotate-image

class Solution { 
        /* 使用辅助空间，寻找旋转后图像与原图像的对应关系 */
        public void rotate(int[][] matrix) { 
            if (matrix == null) { 
                throw new RuntimeException("input cant be null");
            }
            // 使用辅助空间 + 遍历 对应关系映射
            int rows = matrix.length;
            if (rows == 0) { 
                return;
            }
            int cols = matrix[0].length;
            int[][] aux = new int[rows][cols];
            // aux[i][j] = matrix[n-j-1][i];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    aux[i][j] = matrix[rows-j-1][i];
                }
            }
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    matrix[i][j] = aux[i][j];
                }
            }
        }
    }

#### 20.最大子序和 ####

https://leetcode-cn.com/problems/maximum-subarray

class Solution { 
        public int maxSubArray(int[] nums) { 
            int n = nums.length;
            if (n == 0) { 
                return 0;
            }
            // dp[i]表示i及之前的最大连续和
            // dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])-->接上之前的连续和，或从当前开始作为最大连续和
            int[] dp = new int[n];
            dp[0] = nums[0];
            int res = dp[0];
            for (int i = 1; i < n; i++) { 
                // 接上最大子序列和或直接从当前开始算起
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

#### 21.接雨水 ####

https://leetcode-cn.com/problems/trapping-rain-water

class Solution { 
        /* 暴力搜索法 O(n^2),每到一个位置，就从当前位置向左搜索最大值并记录，再从当前位置向右搜索最大值并记录，然后取两者之间的较小值减去当前高度即可得到当前位置的雨水量 */
        public int trap(int[] height) { 
            if (height == null || height.length == 0) { 
                return 0;
            }
            int res = 0, n = height.length;
            for (int i = 1; i < n - 1; i++) { 
                int leftMax = 0, rightMax = 0;
                // 向左找最大的
                for (int j = i; j >= 0; j--) { 
                    leftMax = Math.max(leftMax, height[j]);
                }
                // 向右找最大的
                for (int j = i; j < n; j++) { 
                    rightMax = Math.max(rightMax, height[j]);
                }
                // 累加结果
                res += Math.min(leftMax, rightMax) - height[i];
            }
            return res;
        }
        
        /* 先构建leftMaxs和rightMaxs数组，最后再进行累加，时间复杂度O（n） */
        public int trap(int[] height) { 
            if (height == null || height.length == 0) { 
                return 0;
            }
            int res = 0, n = height.length;
            int[] leftMaxs = new int[n];
            int[] rightMaxs = new int[n];
            leftMaxs[0] = height[0];
            rightMaxs[n - 1] = height[n - 1];
            // 从左往右构建leftMaxs数组
            for (int i = 1; i < n; i++) { 
                leftMaxs[i] = Math.max(leftMaxs[i - 1], height[i]);
            }
            // 从右往左构建rightMaxs数组
            for (int i = n - 2; i >= 0; i--) { 
                rightMaxs[i] = Math.max(rightMaxs[i + 1], height[i]);
            }
            // 进行累加
            for (int i = 1; i < n - 1; i++) { 
                res += Math.min(leftMaxs[i], rightMaxs[i]) - height[i];
            }
            return res;
        }
    }

#### 22.颜色分类 ####

https://leetcode-cn.com/problems/sort-colors

class Solution { 
        public void sortColors(int[] nums) { 
            // TODO: 这是三路快排的划分应用
            partition3Way(nums);
        }
    
        private void partition3Way(int[] nums) { 
            //基数为1
            int base = 1;
            int i = 0;
            int cur = i;
            int j = nums.length - 1;
            //在[0...i)区间，值为0
            //在[i...cur)区间，值为1
            //在(j...n - 1]区间，值为2
            //当cur >= j，终止划分
            while (cur <= j) { 
                //三路快排的交换过程
                int curValue = nums[cur];
                if (curValue < base) { 
                    swap(nums, i++, cur++);
                } else if (curValue > base) { 
                    swap(nums, cur, j--);
                } else { 
                    cur++;
                }
            }
        }
        
        private void swap(int[] a, int i, int j) { 
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

#### 23.杨辉三角 ####

https://leetcode-cn.com/problems/pascals-triangle

class Solution { 
        /* 注意要首先在最左边填充1，填充完中间部分后，在最右边填充1 */
        public List<List<Integer>> generate(int numRows) { 
            List<List<Integer>> res = new ArrayList<>();
            if (numRows == 0) { 
                return res;
            }
            res.add(Arrays.asList(1));
            for (int i = 1; i < numRows; i++) { 
                ArrayList<Integer> oneRes = new ArrayList<>();
                // 第一个1
                oneRes.add(1);
                for (int j = i - 1; j > 0; j--) { 
                    // 根据上一行填充中间部分
                    List<Integer> lastRows = res.get(i - 1);
                    oneRes.add(lastRows.get(j - 1) + lastRows.get(j));
                }
                // 最后一个1
                oneRes.add(1);
                // 将本次结果添加进res
                res.add(oneRes);
            }
            return res;
        }
    }

#### 24.和为k的子数组 ####

https://leetcode-cn.com/problems/subarray-sum-equals-k

class Solution { 
        /* 暴力破解法，O(n^2) */
        public int subarraySum(int[] nums, int k) { 
            if (nums == null || nums.length == 0) { 
                return 0;
            }
            int res = 0;
            for (int i = 0; i < nums.length; i++) { 
                int temp = 0;
                for (int j = i; j < nums.length; j++) { 
                    temp += nums[j];
                    if (temp == k) { 
                        res++;
                    }
                }
            }
            return res;
        }
        
        /* 动态规划法 + 哈希表，时间复杂度O(n) */
        public int subarraySum(int[] nums, int k) { 
            if (nums == null || nums.length == 0) { 
                return 0;
            }
            // dp[i]表示[0, i - 1]的累计和
            int[] dp = new int[nums.length + 1];
            dp[0] = nums[0];
            for (int i = 1; i < dp.length; i++) { 
                dp[i] = dp[i - 1] + nums[i - 1];
            }
            HashMap<Integer, Integer> map = new HashMap<>();
            int res = 0;
            for (int i = 0; i < dp.length; i++) { 
                if (map.containsKey(dp[i] - k)) { 
                    res += map.get(dp[i] - k);
                }
                map.put(dp[i], map.getOrDefault(dp[i], 0) + 1);
            }
            return res;
        }
    }

#### 25.求众数 ####

https://leetcode-cn.com/problems/majority-element-ii

class Solution { 
        /* 使用哈希表作为计数器,时间复杂度O（n），空间复杂度O（k），k为不重复元素个数 */
        public List<Integer> majorityElement(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return new ArrayList<>();
            }
            List<Integer> res = new ArrayList<>();
            HashMap<Integer, Integer> map  =new HashMap<>();
            HashSet<Integer> set  =new HashSet<>();
            if (nums.length <= 2) { 
                for (int i = 0; i < nums.length; i++) { 
                    if (!set.contains(nums[i])) { 
                        set.add(nums[i]);
                        res.add(nums[i]);
                    }
                }
                return res;
            }
            int k = nums.length / 3, n = nums.length;
            for (int i = 0; i < n; i++) { 
                if (map.containsKey(nums[i])) { 
                    if (map.get(nums[i]) + 1 > k && !set.contains(nums[i])) { 
                        set.add(nums[i]);
                        res.add(nums[i]);
                    } else { 
                        map.put(nums[i], map.get(nums[i]) + 1);
                    } 
                } else { 
                    map.put(nums[i], 1);
                }
            }
            return res;
        }
    }

#### 26.返回数据流中第k大元素 ####

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream

class KthLargest { 
    
        // 默认小顶堆
        private PriorityQueue<Integer> minHeap;
        // 记录k
        private int k = -1;
    
        /* 使用小顶堆来收集TOP K大的元素 */
        public KthLargest(int k, int[] nums) { 
            this.k = k;
            this.minHeap = new PriorityQueue<>(k);
            for (int i = 0; i < nums.length; i++) { 
                add(nums[i]);
            }
        }
        
        /* 在小顶堆中添加元素并返回第top k */
        public int add(int val) { 
            if (minHeap.size() == k) { 
                // 当元素大于堆头，删除堆头并添加该元素->重新建堆，时间复杂度O（logn）
                if (val > minHeap.peek()) { 
                    minHeap.poll();
                    minHeap.offer(val);
                }  
            } else { 
                minHeap.offer(val);
            }
            return minHeap.peek();
        }
    }

#### 27.滑动窗口最大值 ####

https://leetcode-cn.com/problems/sliding-window-maximum

class Solution { 
        /* 暴力破解法, 依次收集滑动窗口的最大值，时间复杂度 O（n * k） */
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if (nums == null || nums.length == 0 || k > nums.length) { 
                return new int[]{ };
            }
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i < res.length; i++) { 
                int temp = nums[i];
                // 收集当前窗口的最大值
                for (int j = i; j < i + k; j++) { 
                    temp = Math.max(temp, nums[j]);
                }
                res[i] = temp;
            }
            return res;
        }
        
        /* 使用一个降序的队列充当滑动窗口去收集每个窗口的最大值，时间复杂度O（n） */
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if (nums == null || nums.length == 0 || k > nums.length) { 
                return new int[]{ };
            }
            int[] res = new int[nums.length - k + 1];
            // 降序队列
            LinkedList<Integer> queue = new LinkedList<>();
            int cur = 0;
            for (int i = 0; i < nums.length; i++) { 
                // 1.维护降序队列
                while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) { 
                    queue.pollLast();
                }
                queue.offerLast(i);
                // 2.确保队头不超出范围
                if (queue.peekFirst() == i - k) { 
                    queue.pollFirst();
                }
                // 3.当滑动窗口形成时，依次取队头作为滑动窗口的最大值
                if (i >= k - 1) { 
                    res[cur++] = nums[queue.peekFirst()];
                }
            }
            return res;
        }
        
    }

#### 28.数据流的中位数 ####

https://leetcode-cn.com/problems/find-median-from-data-stream/

class MedianFinder { 
        /* 使用大顶堆和小顶堆的解法 */
        private PriorityQueue<Integer> maxHeap;
        private PriorityQueue<Integer> minHeap;
        private int count;
        
        /** initialize your data structure here. */
        public MedianFinder() { 
            maxHeap = new PriorityQueue<>((x, y) -> y - x);
            minHeap = new PriorityQueue<>();
            count = 0;
        }
    
        public void addNum(int num) { 
            count += 1;
            maxHeap.offer(num);        
            minHeap.offer(maxHeap.poll());
            // 是奇数的话，需要把小顶堆中删去堆头并添加到大顶堆中，保持大顶堆元素比小顶堆多一个
            if ((count & 1) == 1) { 
                maxHeap.offer(minHeap.poll());
            }
        }
        
        public double findMedian() { 
            if (!maxHeap.isEmpty()) { 
                if (maxHeap.size() - minHeap.size() == 1) { 
                    // 当大顶堆比小顶堆元素多1时，去大顶堆的堆头即为中位数
                    return (double)maxHeap.peek();
                } 
                if (maxHeap.size() == minHeap.size()) { 
                    // 当大顶堆与小顶堆元素相同时，取两者堆头/2即获得中位数
                    return (double)(maxHeap.peek() + minHeap.peek()) / 2;
                }
            }
            return 0.0;
        }
    }
    
    /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */

#### 29.滑动窗口中位数 ####

https://leetcode-cn.com/problems/sliding-window-median

class Solution { 
        /* 暴力搜索 O(n^2) */
        public double[] medianSlidingWindow(int[] nums, int k) { 
            if (nums == null || nums.length == 0 || k > nums.length) { 
                return new double[]{ };
            }
            double[] res = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length - k + 1; i++) { 
                res[i] = getMedian(nums, i, i + k - 1);
            }
            return res;
        }
    
        private double getMedian(int[] nums, int i, int j) { 
            // 获取[i, j]间的中位数
            int len = j - i + 1;
            double[] temp = new double[len];
            int cur = 0; double res = 0;
            for (int k = i; k <= j; k++) { 
                temp[cur++] = nums[k];
            }
            Arrays.sort(temp);
            if (len % 2 == 0) { 
                res = (temp[len / 2 - 1] + temp[len / 2]) / 2;
            } else { 
                res = temp[len / 2];
            }
            return res;
        }
    }

#### 30.子数组最大平均数 ####

https://leetcode-cn.com/problems/maximum-average-subarray-i

class Solution { 
            public double findMaxAverage(int[] nums, int k) { 
                if (nums == null || nums.length == 0 || k <= 0 || nums.length < k) { 
                    throw new RuntimeException("数组和k参数不合法");
                }
                double max = 0;
                // 第一个窗口
                for (int i = 0; i < k; i++) { 
                    max += nums[i];
                }
                double temp = max;
                // 遍历，删头加尾确定窗口最大值
                for (int i = 1; i <= nums.length - k; i++) { 
                    temp = temp - nums[i - 1] + nums[i + k - 1];
                    max = Math.max(max, temp);
                }
                return max / k;
            }
        }

#### 31.有效字母异位词 ####

https://leetcode-cn.com/problems/valid-anagram

class Solution { 
        /* O(n) */
        public boolean isAnagram(String s, String t) { 
            if (s.length() != t.length()) { 
                return false;
            }
            int[] nums = new int[26]; 
            // 每个位置记录字符出现次数
            for (int i = 0; i < s.length(); i++) { 
                nums[s.charAt(i)-'a']++;
            }
            // 字符抵消
            for (int i = 0; i < t.length(); i++) { 
                nums[t.charAt(i)-'a']--;
            }
            // 如果仍有字符没有被抵消，说明不是异位词
            for (int count: nums) { 
                if (count != 0) { 
                    return false;
                }
            }
            return true;
        }
    }

#### 32.翻转单词序列 ####

https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 先将整体反转，然后对单词进行逐个反转，时间复杂度O(n) */
        public String ReverseSentence(String str) { 
            if (str == null || str.trim().equals("")) { 
                return str;
            }
            char[] chars = str.toCharArray();
            // 反转整个单词序列
            reverse(chars, 0, chars.length - 1);
            // 依次反转每个单词
            int left = 0, right = 0;
            while (left < chars.length) { 
                // 如果开头就是空格，那么两者一起跳过
                if (chars[left] == ' ') { 
                    left++;
                    right++;
                } else if (right == chars.length - 1) { 
                    // 如果right已经走到结尾，直接反转
                    reverse(chars, left, right);
                    break;
                } else if (chars[right] != ' ') { 
                    // 如果right遇到的不是空格，那么继续寻找单词的末尾空格
                    right++;
                } else if (chars[right] == ' ') { 
                    // right已经走到一个单词的空格处,反转
                    reverse(chars, left, --right);
                    left = ++right;
                }
            }
            return new String(chars);
        }
        private void reverse(char[] chars, int i , int j) { 
            while (i < j) { 
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
                i++;
                j--;
            }
        }
    }

#### 33.无重复字符的最长子串 ####

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

class Solution { 
        /* 使用HashSet保存窗口出现的字符，时间复杂度O（n） */
        public int lengthOfLongestSubstring(String s) { 
            if (s == null || s.length() == 0) { 
                return 0;
            }
            char[] chars = s.toCharArray();
            HashSet<Character> set = new HashSet<>();
            int left = 0, right = 0, res = 0;
            while (left <= right && right < chars.length) { 
                if (!set.contains(chars[right])) { 
                    // 滑动窗口右扩张
                    set.add(chars[right++]);
                    res = Math.max(res, right - left);
                } else { 
                    // 滑动窗口左缩小
                    set.remove(chars[left++]);
                }
            }
            return res;
        }
    }

#### 34.七进制转化 ####

https://leetcode-cn.com/problems/base-7/

class Solution { 
        public String convertToBase7(int num) { 
            if (num == 0) { 
                return "0";
            }
            boolean flag = false; // 是否为负数
            if (num < 0) { 
                num = -1 * num;
                flag = true;
            }
            StringBuilder builder = new StringBuilder();
            // 商为下一次的值，余数为当前的七进制值，从后往前追加
            while (num > 0) { 
                int v = num % 7;// 余数
                num /= 7; // 商
                builder.insert(0, v);
            }
            // 负数处理
            if (flag) { 
                builder.insert(0, "-");
            }
            return builder.toString();
        }
    }

### 二.位运算 ###

#### 1.位1的个数 ####

https://leetcode-cn.com/problems/number-of-1-bits

public class Solution { 
        /* 解法1，循环n次,n为二进制数长度 */
        public int hammingWeight(int n) { 
            int res = 0;
            String bin = Integer.toBinaryString(n);
            for (int i = 0; i < bin.length(); i++) { 
                if (bin.charAt(i) == '1') { 
                    res++;
                }
            }
            return res;
        }
        
         /* 解法2，循环k次,k为二进制数中最高位的1的位数 */
        public int hammingWeight(int n) { 
            int res = 0;
            while (n != 0) { 
                if ((n & 1) == 1) { 
                    res++;
                }
                // 无符号右移，消去末尾1位
                n >>>= 1;
            }
            return res;
        }
    
        /* 解法3，循环res次 */
        public int hammingWeight(int n) { 
            int res = 0;
            while (n != 0) { 
                res++;
                n = (n - 1) & n;
            }
            return res;
        }
    }

#### 2.2的幂 ####

https://leetcode-cn.com/problems/power-of-two

class Solution { 
        public boolean isPowerOfTwo(int n) { 
            // 一个数是2的幂，那么这个数的二进制中只有1个1，使用(n-1)&n消去1后为0
            if (n == 0) { 
                return false;
            }
            // 转化为long型防止溢出
            long ln = (long)n;
            if (((ln - 1) & ln) != 0) { 
                return false;
            }
            return true;
        }
    }

#### 3.只出现一次的数字 ####

https://leetcode-cn.com/problems/single-number

class Solution { 
        public int singleNumber(int[] nums) { 
            // 1.任何数异或0都等于原数
            // 2.相同的数异或为0
            int res = 0;
            for (int value: nums) { 
                res ^= value;
            }
            return res;
        }
    }

#### 4.只出现一次的数字2 ####

https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

//num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    import java.util.HashMap;
    public class Solution { 
        /* 使用HashMap记录数字出现的次数, 时间复杂度O（n），空间复杂度O（k），k为不重复的元素个数 */
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            if (array == null || array.length == 0) { 
                return;
            }
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < array.length; i++) { 
                // 记录每个元素出现的次数
                 map.put(array[i], map.getOrDefault(array[i], 0) + 1);
            }
            boolean first = false;
            for (int i = 0; i < array.length; i++) { 
                 if (map.getOrDefault(array[i], 0) == 1) { 
                     if (!first) { 
                         // 填充第一个元素
                         num1[0] = array[i];
                         first = true;
                         // 标识已经找到
                         map.put(array[i], -1);
                     } else { 
                         // 第二个元素
                         num2[0] = array[i];
                     }
                 }
            }
        }
        
        /* 使用位运算，先将所有的元素异或一遍，相当于两个不重复的元素之间做了一次异或， 然后根据异或得到的结果，获取结果的最低位1出现的位置，再通过该位置将数组分割成两个部分， 这两个部分分别含有一个唯一的元素，再次异或即可分别获取。时间复杂度O（n），空间复杂度O（1） */
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            if (array == null || array.length == 0) { 
                return;
            }
            // 全体异或
            int res = 0;
            for (int value: array) { 
                res ^= value;
            }
            // 获取异或结果的最低位1的位置
            int index = getLower1Index(res);
            // 根据这个位置将数组分割成两个部分来进行异或，就可以得到相应的唯一元素
            int res1 = 0, res2 = 0;
            for (int value: array) { 
                if (getLower1Index(value) == index) { 
                    res1 ^= value;
                } else { 
                    res2 ^= value;
                }
            }
            num1[0] = res1;
            num2[0] = res2;
        }
        /* 获取低位的1位置 */
        private int getLower1Index(int num) { 
            int index = -1;
            while ((num & 1) != 1) { 
                // 当最低位不为1，则无符号右移动
                index++;
                num >>>= 1;
            }
            return index;
        }
    }

### 三.回溯 ###

#### 1.全排列 ####

https://leetcode-cn.com/problems/permutations

class Solution { 
        // 存储结果
        private List<List<Integer>> res = new ArrayList<>();
        // 是否已使用该位置
        private boolean[] used;
        public List<List<Integer>> permute(int[] nums) { 
                used = new boolean[nums.length];
                // 单个答案的数据数
                int count = 0;
                ArrayList<Integer> oneRes = new ArrayList<>();
                // 回溯搜索
                backTraceSearch(count, nums, oneRes);
                return res;
        }
        private void backTraceSearch(int count, int[] nums, ArrayList<Integer> oneRes) { 
            // 回溯终止条件
            if (count == nums.length) { 
                res.add(new ArrayList<>(oneRes));
                return;
            }
            // 回溯搜索
            for (int i = 0; i < nums.length; i++) { 
                if (!used[i]) { 
                    // 没有使用过
                    used[i] = true;
                    oneRes.add(nums[i]);
                    backTraceSearch(count + 1, nums, oneRes);
                    // 状态回溯
                    oneRes.remove(oneRes.size() - 1);
                    used[i] = false;
                }
            }
            return;
        }
    }

#### 2.组合总数 ####

https://leetcode-cn.com/problems/combinations

class Solution { 
        // 存储结果
        private List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> combine(int n, int k) { 
                // 开始索引
                int index = 1;
                ArrayList<Integer> oneRes = new ArrayList<>();
                // 回溯搜索
                backTraceSearch(index, k, n, oneRes);
                return res;
        }
        private void backTraceSearch(int index, int k, int n, ArrayList<Integer> oneRes) { 
            // 回溯终止条件
            if (oneRes.size() == k) { 
                res.add(new ArrayList<>(oneRes));
                return;
            }
            // 回溯搜索
            for (int i = index; i <= n; i++) { 
                oneRes.add(i);
                backTraceSearch(i + 1, k, n, oneRes);
                // 状态回溯
                oneRes.remove(oneRes.size() - 1);
            }
            return;
        }
    }

#### 3.N皇后问题 ####

https://leetcode-cn.com/problems/n-queens-ii/

class Solution { 
        private int res = 0;
        // 记录已经摆放了的皇后位置
        private int[] record;
    
        public int totalNQueens(int n) { 
            record = new int[n];
            int row = 0;
            backTraceSearch(row, n);
            return res;
        }
        private void backTraceSearch(int row, int n) { 
            // 回溯终止条件
            if (row == n) { 
                res++;
                return;
            }
            // 回溯搜索，逐列寻找摆放皇后的位置
            for (int col = 0; col < n; col++) { 
                if (check(row, col)) { 
                    // 该位置可以摆放皇后，继续往上一行放置皇后
                    record[row] = col;
                    backTraceSearch(row + 1, n);
                    // 状态回溯
                    record[row] = 0;
                }
            }
            return;
        }
        /* 检查该位置是否可放置皇后 */
        private boolean check(int row, int col) { 
            for (int i = 0; i < row; i++) { 
                // 检查该列以下是否存在皇后 
                if (record[i] == col) { 
                    return false;
                }
                 // 检查对角线是否含皇后
                 if (Math.abs(i - row) == Math.abs(record[i] - col)) { 
                     return false;
                 }
            }
            return true;
        }
    }

#### 4.复原IP地址 ####

https://leetcode-cn.com/problems/restore-ip-addresses

class Solution { 
        private List<String> res = new ArrayList<>();
        
        public List<String> restoreIpAddresses(String s) { 
            // 当前索引
            int index = 0;    
            // 当前结果 
            ArrayList<String> oneRes = new ArrayList<>();
            backTraceSearch(s, index, oneRes);
            return res;
        }
        private void backTraceSearch(String s, int index, ArrayList<String> oneRes) { 
            // 回溯终止条件
            if (oneRes.size() == 4) { 
                // 已经是最后一个位置
                if (index == s.length()) { 
                    res.add(String.join(".", oneRes));
                }
                return;
            }
            // 回溯搜索
            for (int i = 1; i <= 3; i++) { 
                // IP段最长为3位
                if (index + i > s.length()) { 
                    break;
                }
                // 获取分段
                String segment = s.substring(index, index + i);
                // 分段校验
                if (segment.startsWith("0") && segment.length() > 1 || 
                     segment.length() == 3 && Integer.valueOf(segment) > 255) { 
                    break;
                }
                oneRes.add(segment);
                backTraceSearch(s, index + i, oneRes);
                // 状态回溯
                oneRes.remove(oneRes.size() - 1);
            }
            return;
        }
    }

#### 5.括号生成 ####

https://leetcode-cn.com/problems/generate-parentheses

class Solution { 
        private List<String> res = new ArrayList<>();
    
        public List<String> generateParenthesis(int n) { 
            // 括号总数、左括号数量、右括号数量
            int count = 0, left = 0, right = 0;
            backTraceSearch(count, left, right, n, new StringBuilder());    
            return res;
        }
        private void backTraceSearch(int count, int left, int right, int n, StringBuilder oneRes) { 
            // 回溯终止条件
            if (count == 2 * n) { 
                res.add(oneRes.toString());
                return;
            }
            // 回溯搜索
            if (left < n) { 
                oneRes.append("(");
                backTraceSearch(count + 1, left + 1, right, n, oneRes);
                oneRes.deleteCharAt(oneRes.length() - 1);
            }
            if (right < left) { 
                oneRes.append(")");
                backTraceSearch(count + 1, left, right + 1, n, oneRes);
                oneRes.deleteCharAt(oneRes.length() - 1);
            }
            return;
        }
    
    }

#### 6.岛屿数量 ####

https://leetcode-cn.com/problems/number-of-islands/

class Solution { 
        // x-1,y
        // x,y-1 x,y x,y+1
        // x+1,y
        // 方向数组
        private int[][] direction = { { -1, 0}, { 0, 1}, { 1, 0}, { 0, -1}};
        // 最终结果
        private int res = 0;
        // 是否已被标记过
        private boolean[][] marked;
        // 地图
        private char[][] grid;
            
        /* 使用回溯搜索 + 深度优先搜索的方式，上下左右地搜索 */
        public int numIslands(char[][] grid) { 
            int rows = grid.length;
            if (rows == 0) { 
                return res;
            }
            int cols = grid[0].length;
            marked = new boolean[rows][cols];
            this.grid = grid;
            
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    // 如果是没被标记过的陆地，则在此进行回溯搜索（dfs）
                    if (!marked[i][j] && grid[i][j] == '1') { 
                        res++;
                        backTraceSearch(i, j);
                    }
                }
            }
            return res;
        }
        private void backTraceSearch(int row, int col) { 
            // 标记该位置被访问
            marked[row][col] = true;
            // 进行上右下左的回溯搜索
            for (int i = 0; i < 4; i++) { 
                int x = row + direction[i][0];
                int y = col + direction[i][1];
                // 剪枝，越界的和非陆地、被访问过的区域不再访问
                if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == '1' && marked[x][y] == false) { 
                    backTraceSearch(x, y);
                }
            }
        }
    }

#### 7.正则表达式匹配 ####

https://leetcode-cn.com/problems/regular-expression-matching/

/* 暴力递归匹配 */
    
    class Solution { 
        public boolean isMatch(String s, String p) { 
        //如果正则串p为空字符串s也为空这匹配成功，如果正则串p为空但是s不是空则说明匹配失败
        if (p.isEmpty()) { 
            return s.isEmpty();
        }
        //判断s和p的首字符是否匹配，注意要先判断s不为空
        boolean headMatched = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        if (p.length() >= 2 && p.charAt(1) == '*') { //如果p的第一个元素的下一个元素是*
            //则分别对两种情况进行判断
            return isMatch(s, p.substring(2)) ||
                (headMatched && isMatch(s.substring(1), p));
        } else if (headMatched) { //否则，如果s和p的首字符相等
            return isMatch(s.substring(1), p.substring(1));
        }else { 
            return false;
        }
    }
    }
    
    
    
    /* 回溯搜索 */
    public class Solution { 
        public boolean isMatch(String str, String pattern) { 
        if (str == null || pattern == null) { 
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str.toCharArray(), strIndex, pattern.toCharArray(), patternIndex);
    }
      
      
    /* *当模式中的第二个字符不是“*”时： *1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模*式都后移一个字符，然后匹配剩余的。 *2、如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。 * *而当模式中的第二个字符是“*”时： *如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继*续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方*式： *1、模式后移2字符，相当于x被忽略； *2、字符串后移1字符，模式后移2字符； *3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位； */
    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) { 
        // 有效性检验：str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) { 
            return true;
        }
        // pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) { 
            return false;
        }
        //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') { 
            // 分三种情况匹配
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
             (pattern[patternIndex] == '.' && strIndex != str.length)) { 
                 // 模式的前一个和字符串的前一个是想同的，或模式前一个为.，继续向右匹配
                return matchCore(str, strIndex, pattern, patternIndex + 2)// 模式后移2，视为x*匹配0个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2)// 字符串后移1位，模式后移2位，视为x*匹配1个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex);// x*匹配1个，再匹配str中的下一个
            } else { 
                // 直接略去模式的x*，接着往下匹配
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        //模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) { 
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
        }
    }

#### 8.单词搜索 ####

https://leetcode-cn.com/problems/word-search/

class Solution { 
            
        private boolean[][] marked;
    
        // x-1,y
        // x,y-1 x,y x,y+1
        // x+1,y
        private int[][] direction = { { -1, 0}, { 0, -1}, { 0, 1}, { 1, 0}};
        // 盘面上有多少行
        private int m;
        // 盘面上有多少列
        private int n;
        private String word;
        private char[][] board;
    
        public boolean exist(char[][] board, String word) { 
            m = board.length;
            if (m == 0) { 
                return false;
            }
            n = board[0].length;
            marked = new boolean[m][n];
            this.word = word;
            this.board = board;
    
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (dfs(i, j, 0)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean dfs(int i, int j, int start) { 
            if (start == word.length() - 1) { 
                // 已经是最后一个字符时，若一样则为true
                return board[i][j] == word.charAt(start);
            }
            // 当当前start与board的该位置匹配，则继续dfs
            if (board[i][j] == word.charAt(start)) { 
                marked[i][j] = true;
                for (int k = 0; k < 4; k++) { 
                    // 上下左右进行搜索
                    int newX = i + direction[k][0];
                    int newY = j + direction[k][1];
                    // 当前没有被标记到则进行搜索
                    if (inArea(newX, newY) && !marked[newX][newY]) { 
                        if (dfs(newX, newY, start + 1)) { 
                            return true;
                        }
                    }
                }
                marked[i][j] = false;
            }
            return false;
        }
    
        private boolean inArea(int x, int y) { 
            return x >= 0 && x < m && y >= 0 && y < n;
        }
     }

### 四.动态规划 ###

#### 1.买卖股票最佳时机 ####

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

class Solution { 
        public int maxProfit(int[] prices) { 
            // dp[i] = Math.max(0, dp[i - 1] + prices[i] - prices[i - 1])
            // dp[i] 表示第i天卖出可以获取到第最大利润
            if (prices == null || prices.length <= 1) { 
                return 0;
            }
            int res = 0;
            int[] dp = new int[prices.length];
            dp[0] = 0;// 第一天利润为0
            for (int i = 1; i < prices.length; i++) { 
                // 当今天可以买时则累加，不然则为0
                dp[i] = Math.max(0, dp[i - 1] + prices[i] - prices[i - 1]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

class Solution { 
        public int maxProfit(int[] prices) { 
            // 定义dp[i][j]表示第i天处于j状态时的利润
            // j = 0，不持股；昨天可不持股或持股卖出
            // j = 1，持股；昨天一直持股或冷冻期买入
            // j = 2，冷冻期；前天持股卖出 ，冷冻期为卖出股票后的一天，所以昨天不持股
            if (prices == null || prices.length < 2) { 
                return 0;
            }
            int[][] dp = new int[prices.length][3];
            // 第一天边界条件
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            dp[0][2] = 0;
    
            for (int i = 1 ; i < prices.length; i++) { 
                // 不持股，可能昨天不持股或持股卖出
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 持股，可能昨天持股或冷冻期买入
                dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][2] - prices[i]);
                // 冷冻期，昨天不持股
                dp[i][2] = dp[i - 1][0];
            }
            // 最后的最大利润在不持股或冷冻期两者中
            return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
        }
    }

#### 3.买卖股票最佳时机含手续费 ####

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

class Solution { 
        public int maxProfit(int[] prices, int fee) { 
            // dp[i][j]表示在i天之前各状态可获取的最大利润
            // j定义不持有状态为0，持有状态为1
            // j = 0，昨天不持有或昨天持有卖出
            // j = 1，昨天持有或昨天不持有买入（需要算手续费）
            if (prices == null || prices.length < 2) { 
                return 0;
            }
            int[][] dp = new int[prices.length][2];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            for (int i = 1; i < prices.length; i++) { 
                // 不持股，昨天不持股或卖出（含手续费）
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
                // 持股，昨天持股或买入
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
            // 最大值在不持股的情况下发生
            return dp[prices.length - 1][0];
        }
    }

#### 4.不同路径 ####

https://leetcode-cn.com/problems/unique-paths

class Solution { 
     public int uniquePaths(int m, int n) { 
            // 状态转移方程: dp[i][j] = dp[i + 1][j] + dp[i][j + 1] (设机器人从左下角出发,只能往右和上走,目标在右上角)
            int[][] dp = new int[m + 1][n + 1];
            //已知目标的左边一行和下边一列只能有一个走法:向右或向上
            for (int i = 1; i <= m ; i++) { 
                dp[i][n] = 1;
            }
            for (int i = 1; i <= n ; i++) { 
                dp[m][i] = 1;
            }
            for (int i = m - 1; i >= 1; i--) { 
                //填充dp[i][j], 求dp[1][1]
                for (int j = n - 1; j >= 1 ; j--) { 
                    dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
                }
            }
            return dp[1][1];
        }
    }

#### 5.最长回文子串 ####

https://leetcode-cn.com/problems/longest-palindromic-substring

class Solution { 
        /* * 中心扩散法,时间复杂度O(n^2) */
        public String longestPalindrome(String s) { 
            if (s == null || s.length() == 0) { 
                return s;
            }
            String res = "";
            for (int i = 0; i < s.length(); i++) { 
                int len1 = lenOfPalindrome(s, i, i);// 从i为分界点扩散
                int len2 = lenOfPalindrome(s, i, i + 1);// 以i与i+1之间为分界点扩散
                int max = Math.max(len1, len2);
                if (max > res.length()) { 
                    // 确定以i为中心的和max为直径的回文起始点和结束点
                    int left = i - (max -1) / 2;
                    int right = i + max / 2;
                    // 截取出最长子串
                    res = s.substring(left, right + 1);
                }
            }
            return res;
        }
        private int lenOfPalindrome(String s, int left, int right) { 
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { 
                    left--;
                    right++;
            }
            return right - left - 1;
        }
    }

#### 6.编辑距离「二维dp」 ####

https://leetcode-cn.com/problems/edit-distance

class Solution { 
        public int minDistance(String word1, String word2) { 
             int rows = word1.length();
             int cols = word2.length();
             // 状态转移方程: dp[i][j] = min{dp[i][j - 1] + 1//增, dp[i - 1][j] + 1//删, dp[i - 1][j - 1] + 0或1//改}
             // 其中dp[i - 1][j - 1] + 0代表着word1和word2的第i,j个位置元素相同，所以无需改；
             //dp[i - 1][j - 1] + 1代表着word1和word2的第i,j个位置元素不相同，所以要改
             int[][] dp = new int[rows + 1][cols + 1];
             // 填充word1为""时转化为word2的编辑距离
             for (int i = 1; i <= cols; i++) { 
                 dp[0][i] = i; 
             }
             // 填充word2为""时转化为word1的编辑距离
             for (int i = 1; i <= rows; i++) { 
                 dp[i][0] = i; 
             }
             // 填充dp
             for (int i = 1; i <= rows; i++) { 
                 for (int j = 1; j <= cols; j++) { 
                     int addCount = dp[i - 1][j] + 1; // 增
                     int deleteCount = dp[i][j - 1] + 1; // 删
                     int changeCount = dp[i - 1][j - 1];  // 改
                     if (word1.charAt(i - 1) != word2.charAt(j - 1)) { 
                         changeCount++;
                     }
    
                     dp[i][j] = Math.min(addCount, Math.min(deleteCount, changeCount));
                 }
             }
             return dp[rows][cols];
        }
    }

#### 7.最长公共子序列「二维dp」 ####

https://leetcode-cn.com/problems/longest-common-subsequence

class Solution { 
     public int longestCommonSubsequence(String text1, String text2) { 
            if (text1.length() == 0 || text2.length() == 0) { 
                return 0;
            }
            int rows = text1.length();
            int cols = text2.length();
            int[][] dp = new int[rows + 1][cols + 1];
            // 填充dp表,状态转移方程： 
            // 1.text1[i] == text2[j],dp[i][j] = dp[i - 1][j] + 1
            // 2.text1[i] != text2[j],dp[i][j] = max{dp[i - 1][j], dp[i][j - 1]}
            for (int i = 1; i <= rows; i++) { 
                for (int j = 1; j <= cols; j++) { 
                    if (text1.charAt(i - 1) == text2.charAt(j - 1)) { 
                        // 相等，取dp[i - 1][j - 1]的值 + 1
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else { 
                        // 不想等，取dp[i - 1][j]和dp[i][j - 1]中的最大值
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[rows][cols];
        }
    }

#### 8.最长上升子序列 ####

https://leetcode-cn.com/problems/longest-increasing-subsequence

class Solution { 
        public int lengthOfLIS(int[] nums) { 
            if (nums.length <= 1) { 
                return nums.length;
            }
            // 状态转移方程 dp[i] = max{dp[i-1], dp[i-2],..., dp[0]} + 1,其中dp[i-1], dp[i-2]等需要小于nums[i],这个过程是往后寻找，接上最长上升子序列的过程，所以每个dp都表示了当前i能够与之前范围组成的最长的上升子序列长度。
            int[] dp = new int[nums.length];
            // 默认自身就是一个最长上升子序列
            int res = 1;
            for (int i = 0; i < nums.length; i++) { 
                dp[i] = 1;// 默认以自身开始
                for (int j = i; j >= 0; j--) { 
                    if (nums[i] > nums[j]) { 
                        // 往后寻找
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

#### 9.换钱最少货币数 ####

https://leetcode-cn.com/problems/coin-change

class Solution { 
        public int coinChange(int[] coins, int amount) { 
            if (amount < 1 || coins.length == 0) { 
                return 0;
            }
            // dp[i]表示凑i元最少所需的货币数
            // 状态转移方程: dp[i] = min(dp[i-j] + 1); j表示某货币数值
            int[] dp = new int[amount + 1];
            // 先对货币进行排序
            Arrays.sort(coins);
            // 默认不可换钱
            Arrays.fill(dp, Integer.MAX_VALUE);
            // 边界条件
            for (int i = 0; i < coins.length; i++) { 
                // 直接兑换
                if (coins[i] < dp.length) { 
                  dp[coins[i]] = 1;
                }
            }
            // 填充dp[i]
            for (int i = 1; i <= amount; i++) { 
                for (int j = 0; j < coins.length; j++) { 
                    int coin = coins[j];
                    // 可兑换
                    if (i > coin && dp[i - coin] != Integer.MAX_VALUE) { 
                        dp[i] = Math.min(dp[i], dp[i - coin]+ 1);
                    }
                }
            }
            return (dp[amount] == Integer.MAX_VALUE) ? - 1 : dp[amount];
        }
    }

#### 10.矩阵最小路径和 ####

https://leetcode-cn.com/problems/minimum-path-sum/

class Solution { 
        public int minPathSum(int[][] grid) { 
            // dp[i]表示从起点走到该位置的最小和
            // 状态转移方程： dp[i] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            if (grid == null || grid.length == 0) { 
                return 0;
            }
            int rows = grid.length, cols = grid[0].length;
            int[][] dp = new int[rows][cols];
            // 边界状态
            dp[0][0] = grid[0][0];
            // 第一行和第一列直接累加
            for (int i = 1; i < rows; i++) { 
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }
            for (int i = 1; i < cols; i++) { 
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }
            // 填充dp
            for (int i = 1; i < rows; i++) { 
                for (int j = 1; j < cols; j++) { 
                    // 从上一行或上一列中寻找最小的进行相加d
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
            return dp[rows - 1][cols - 1];
        }
    }

#### 11.龙与地下城 ####

https://leetcode-cn.com/problems/dungeon-game

class Solution { 
        public int calculateMinimumHP(int[][] dungeon) { 
            if (dungeon == null || dungeon.length == 0) { 
                return 0;
            }
            int rows = dungeon.length;
            int cols = dungeon[0].length;
            int[][] dp = new int[rows][cols];
            int identValue = dungeon[rows - 1][cols - 1];
            dp[rows - 1][cols - 1] = (identValue > 0) ? 1 : 1 - identValue;
            for (int i = rows - 2; i >= 0; i--) { 
                int val = dp[i + 1][cols - 1] - dungeon[i][cols - 1];
                dp[i][cols - 1] = (val <= 0) ? 1 : val;
            }
            for (int i = cols - 2; i >= 0; i--) { 
                int val = dp[rows - 1][i + 1] - dungeon[rows - 1][i];
                dp[rows - 1][i] = (val <= 0) ? 1 : val;
            }
            for (int i = rows - 2; i >= 0; i--) { 
                for (int j = cols - 2; j >= 0; j--) { 
                    int min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                    // 不断填充dp,当当前期望值小于等于0，说明当前的补血多于扣血，当前血量设置为1
                    int val = (min - dungeon[i][j]) <= 0 ? 1 : min - dungeon[i][j];
                    dp[i][j] = val;
                }
            }
            return dp[0][0];
        }
    
    }

#### 12.打家劫舍 ####

https://leetcode-cn.com/problems/house-robber

class Solution { 
        public int rob(int[] nums) { 
            // dp[i]表示第i天获得的最高利益，有两种选择，不偷窃或放弃前一天的结果，偷窃
            // dp[i] = Math.max(dp[i-2] + nums[i] (隔天偷盗), dp[i - 1](不偷盗))
            if (nums == null || nums.length == 0) { 
                return 0;
            }
            int[] dp = new int[nums.length + 1]; 
            dp[1] = nums[0];
            // 从第2天开始
            for (int i = 2; i <= nums.length; i++) { 
                // dp[i - 1],不偷窃
                // dp[i - 2] + nums[i - 1],隔天偷窃
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
            }
            return dp[nums.length];
        }
    }

#### 13.剪绳子 ####

https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=33257&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

import java.lang.Math;
    public class Solution { 
        public int cutRope(int target) { 
            // 动态规划解法，dp表示绳子的长度：
            // 当长度为1时，最大乘积只能为1
            // 当长度为2时，最大乘积为1
            // 当长度为3时，最大乘积为2
            // 当长度大于等于4时，可以换分为不同的小段，每一段即一个dp
            switch (target) { 
                    case 2 : return 1;
                    case 3 : return 2;
            }
            // 以下是可以分段的情形，dp1 ，2， 3直接就可使用
            int[] dp = new int[target + 1];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;
            // 构造dp
            for (int i = 4; i <= target; i++) { 
                for (int j = 1; j <= i / 2; j++) { 
                    // 将绳子切分成两段
                    // dp[i - j] * dp[j] 表示两段的乘积
                    dp[i] = Math.max(dp[i], dp[i - j] * dp[j]);
                }
            }
            return dp[target];
        }
    }

#### 14.爬楼梯 ####

https://leetcode-cn.com/problems/climbing-stairs

class Solution { 
        /* 斐波那契数列类问题 */
        public int climbStairs(int n) { 
            if (n <= 3) { 
                return n;
            }
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;
            for (int i = 4; i <= n; i++) { 
                // 状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

#### 15.单词拆分 ####

https://leetcode-cn.com/problems/word-break

class Solution { 
        public boolean wordBreak(String s, List<String> wordDict) { 
            // 动态规划解法，dp[i]=true表示[0,i）的单词可以使用wordDict表示，那么只需要判断[i,length）的单词可不可以表示即可
            // 状态转移方程：dp[i] = dp[0...j] && set.contains(0, j)
            // 将wordDict添加到hashSet中
            HashSet<String> set = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            // 初始条件，肯定可以拆分成空串
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) { 
                // 在该串中继续找子串，只要匹配即为true
                for (int j = 0; j <= i; j++) { 
                    if (dp[j] && set.contains(s.substring(j, i))) { 
                        dp[i] = true;
                    }
                }
            }
            return dp[s.length()];
        }
    }

#### 16.丑数2 ####

https://leetcode-cn.com/problems/ugly-number-ii

class Solution { 
        public int nthUglyNumber(int n) { 
            if (n < 1) { 
                throw new RuntimeException("n不可小于1");
            }
            int[] dp = new int[n];
            dp[0] = 1;
            int p2 = 0, p3 = 0, p5 =0;
            for (int i = 1; i < n; i++) { 
                int min = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
                if (min == dp[p2] * 2) { 
                    p2++;
                }
                if (min == dp[p3] * 3) { 
                    p3++;
                }
                if (min == dp[p5] * 5) { 
                    p5++;
                }
                dp[i] = min;
            }
            return dp[n - 1];
        }
    }

#### 17.完全平方数 ####

https://leetcode-cn.com/problems/perfect-squares

class Solution { 
        public int numSquares(int n) { 
            // dp[i]表示i含有的最小平方数个数
            // dp[i] = min(dp[i], dp[i - j^2]) (i - j^2 >=0)
            if (n <= 3) { 
                return n;
            }
            int[] dp = new int[n + 1];
            // 边界条件
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;
            for (int i = 4; i <= n; i++) { 
                // 默认所含有的完全平方数都为1的情况
                dp[i] = i;
                for (int j = 0; i - j * j >= 0; j++) { 
                    // 往前寻找完全平方数
                    // dp[i - j * j] + 1
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1); 
                }
            }
            return dp[n];
        }
    }

#### 18.三角形最小路径和 ####

https://leetcode-cn.com/problems/triangle

class Solution { 
        public int minimumTotal(List<List<Integer>> triangle) { 
            if (triangle == null || triangle.size() == 0) { 
                return 0;
            }
            // dp[i][j]表示i， j这个位置的最小路径和
            // dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
            // 边界条件，第一列和最后的斜边直接填充
            int n = triangle.size();
            int[][] dp = new int[n][n];
            dp[0][0] = triangle.get(0).get(0);
            for (int i = 1; i < n; i++) { 
                dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            }
            for (int i = 1; i < n; i++) { 
                dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
            }
            // 填充dp中间部分
            for (int i = 2; i < n; i++) { 
                List<Integer> list = triangle.get(i);
                // 填充该list中间部分
                for (int j = 1; j < list.size() - 1; j++) { 
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + list.get(j);
                }
            }
            // 寻找最后的路径最小和
            int res = dp[n - 1][0];
            for (int i = 1; i < n; i++) { 
                res = Math.min(res, dp[n - 1][i]);
            }
            return res;
        }
    }

#### 19.乘积最大子序列 ####

https://leetcode-cn.com/problems/maximum-product-subarray

class Solution { 
        public int maxProduct(int[] nums) { 
            int[] dp_max = new int[nums.length+1];
            int[] dp_min = new int[nums.length+1];
            if(nums.length == 0) return 0;
            int max = Integer.MIN_VALUE;
            // 由于存在负数，所以需要维护两个数组
            // dp_max[i] 指的是以第 i 个数结尾的 乘积最大 的连续子序列
            // dp_min[i] 指的是以第 i 个数结尾的 乘积最小 的连续子序列
            dp_max[0] = 1;
            dp_min[0] = 1;
            for (int i = 1;i <= nums.length;i++){ 
                // 如果数组的数是负数，那么会导致 max 变成 min，min 变成 max
                // 故需要交换dp 
                if(nums[i-1] < 0){ 
                    int temp = dp_min[i-1];
                    dp_min[i-1] = dp_max[i-1];
                    dp_max[i-1] = temp;
                }
                dp_min[i] = Math.min(nums[i-1],dp_min[i-1]*nums[i-1]);
                dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1]);
                max = Math.max(max,dp_max[i]);
            }
            return max;
        }
    }

### 五.二叉树 ###

#### 1.前序和后序重建二叉树 ####

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            return helper(pre, in, 0, pre.length - 1, 0, in.length - 1);
        }
        private TreeNode helper(int[] pre, int[] in, int preLeft, int preRight, int inLeft, int inRight) { 
            //
            if (preLeft > preRight || inLeft > inRight) { 
                return null;
            }
            // 由前序遍历序列获取根节点
            int rootValue = pre[preLeft];
            TreeNode root = new TreeNode(rootValue);   
            // 在中序遍历序列中，搜索出根节点的位置
            int index = findRootIndex(rootValue, in);
            // 通过根节点位置，在中序遍历序列中可划分出左子树和右子树的中序遍历序列
            // 在前序遍历中，可划分出左子树和右子树的前序遍历序列,继续递归地构建树
            // preLeft + index - inLeft：通过preLeft + 左子树节点数（index - inLeft）确定左子树前序遍历的右边界
            // preLeft + index - inLeft + 1:通过前序遍历序列的右边界+1确定中序遍历序列的左边界
            root.left = helper(pre, in, preLeft + 1, preLeft + index - inLeft, inLeft, index - 1);
            root.right = helper(pre, in, preLeft + index - inLeft + 1, preRight, index + 1, inRight);
            return root;
        }
        private int findRootIndex(int target, int[] array) { 
            for (int i = 0; i < array.length; i++) { 
                if (array[i] == target) { 
                    return i;
                }
            }
            return -1;
        }
         
    }

#### 2.序列化反序列化二叉树 ####

https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        String Serialize(TreeNode root) { 
            StringBuilder builder = new StringBuilder();
            return _Serialize(root, builder).toString();
        }
        private StringBuilder _Serialize(TreeNode root, StringBuilder builder) { 
            // 递归终止条件
            if (root == null) { 
                builder.append("#!");
                return builder;
            }
            // 使用前序的方式序列化
            builder.append(root.val + "!");
            _Serialize(root.left, builder);
            _Serialize(root.right, builder);
            return builder;
        }
        
        TreeNode Deserialize(String str) { 
           return _Deserialize(str.split("!"));
        }
        
        private int index = -1;
        private TreeNode _Deserialize(String[] strs) { 
            index++;
            if (index >= strs.length || "#".equals(strs[index])) { 
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(strs[index]));
            root.left = _Deserialize(strs);
            root.right = _Deserialize(strs);
            return root;
        }
    }

#### 3.二叉树的子结构 ####

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            if (root1 == null || root2 == null) { 
                return false;
            }
            boolean res = false;
            if (root1 != null && root2 != null) { 
                // 判断该位置是否为子结构
                res = check(root1, root2);
            }
            if (!res) { 
                // 在左子树中寻找
                res = HasSubtree(root1.left, root2);
            }
            if (!res) { 
                // 在右子树中寻找
                res = HasSubtree(root1.right, root2);
            }
            return res;
        }
        private boolean check(TreeNode root1, TreeNode root2) { 
            // 子结构判断条件
            if (root1 == null && root2 == null || root2 == null) { 
                return true;
            }
            if (root1 == null && root2 != null) { 
                return false;
            }
            if (root1.val != root2.val) { 
                return false;
            }
            // 再次校验左右子树是否都满足子结构
            return check(root1.left, root2.left) && check(root1.right, root2.right);
        }
    }

#### 4.二叉树镜像 ####

https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public void Mirror(TreeNode root) { 
            if (root == null) { 
                return;
            }
            Mirror(root.left);
            Mirror(root.right);
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

#### 5.从上往下打印二叉树 ####

https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 使用队列来存储节点 */
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { 
            ArrayList<Integer> res = new ArrayList<>();
            if (root == null) { 
                return res;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) { 
                TreeNode poll = queue.poll();
                if (poll.left != null) { 
                    queue.offer(poll.left);
                }
                if (poll.right != null) { 
                    queue.offer(poll.right);
                }
                // 添加层序遍历结果
                res.add(poll.val);
            }
            return res;
        }
    }

#### 6.验证二叉搜索树的后序遍历序列 ####

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        public boolean VerifySquenceOfBST(int [] sequence) { 
            // 两个特殊情况处理
             if (sequence.length == 0){ 
                return false;
            }
            if (sequence.length == 1){ 
                return true;
            }
            int left = 0, right = sequence.length - 1;
            return check(sequence, left, right);
        }
        private boolean check(int[] sequence, int left, int right) { 
            if (left >= right) { 
                return true;
            }
            // 根节点
            int root = sequence[right];
            // 划分节点
            int index = -1;
            // 从右往左找第一个比根节点小的节点，划分左右子树
            for (int i = right - 1; i >= left; i--) { 
                if (sequence[i] < root) { 
                    index = i;
                    break;
                }
            }
            for (int i = index; i >= left; i--) { 
                if (sequence[i] >= root) { 
                    return false;
                }
            }
            // 划分左右子树
            return check(sequence, left, index) && check(sequence, index + 1, right - 1);
        }
    }

#### 7.二叉搜索树转化双向链表 ####

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        /* 使用栈模拟中序遍历过程 */
        public TreeNode Convert(TreeNode pRootOfTree) { 
            if (pRootOfTree == null || pRootOfTree.left == null && pRootOfTree.right == null) { 
                return pRootOfTree;
            }
            Stack<TreeNode> stack  = new Stack<>();
            // 是第一个获取到的节点
            boolean first = true;
            TreeNode root = pRootOfTree, res = pRootOfTree, pre = null;
            while (!stack.isEmpty() || root != null) { 
                if (root != null) { 
                    stack.push(root);
                    root = root.left;
                } else { 
                    TreeNode pop = stack.pop();
                    root = pop.right;
                     
                    if (first) { 
                        res = pop;
                        pre = pop;
                        first = false;
                    } else { 
                        pre.right = pop;
                        pop.left = pre;
                        pre = pop;
                    }
                }
            }
            return res;
        }
    }

#### 8.平衡二叉树校验 ####

https://leetcode-cn.com/problems/balanced-binary-tree

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isBalanced(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            // 判断是否为平衡二叉树
            return getMaxDepth(root) != -1;
        }
        
        private int getMaxDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = getMaxDepth(root.left);
            int right = getMaxDepth(root.right);
            // 判断左右子树的深度是否为-1
            if (left == -1 || right == -1) { 
                return -1;
            }
            // 如果左右子树深度差值大于1则返回-1表示该树不是平衡二叉树，如果小于1则返回最大深度
            return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
        }
    }

#### 9.二叉树的深度 ####

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

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

#### 10.二叉树的中序下一节点 ####

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

public class Solution { 
        public TreeLinkNode GetNext(TreeLinkNode root)
        { 
            if (root == null) { 
                return null;
            }
            // 1.有右子树，找右子树最左
            if (root.right != null) { 
                return findMostLeft(root.right);
            } else { 
                // 2.3.无右子树，当当前节点是父节点的左子树时，父节点就是后继节点
                TreeLinkNode parent = root.next;
                while (parent != null && parent.left != root) { 
                    root = parent;
                    parent = parent.next;
                }
                return parent;
                
            }
        }
        private TreeLinkNode findMostLeft(TreeLinkNode root) { 
            if (root.left == null) { 
                return root;
            }
            return findMostLeft(root.left);
        }
    //--------------------------------------------------------------
        private List<TreeLinkNode> list = new ArrayList<>();
            
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        { 
            if (pNode == null) { 
                return null;
            }
            TreeLinkNode root = pNode;
            // 找到树的根节点
            while (root.next != null) { 
                root = root.next;
            }
            // 获取中序遍历结果集
            inOrder(root);
            for (int i = 0; i < list.size(); i++) { 
                if (list.get(i) == pNode) { 
                    // 返回下一个节点
                    return (i >= list.size() - 1) ? null : list.get(i + 1);
                }
            }
            return null;
        }
        
        private void inOrder(TreeLinkNode root) { 
            if (root == null) { 
                return;
            }
            inOrder(root.left);
            list.add(root);
            inOrder(root.right);
        }
    
    }

#### 11.之字形打印二叉树 ####

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

class Solution { 
        /* 层次遍历，带上深度条件 */
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) { 
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) { 
                return res;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int depth = 0;
            while (!queue.isEmpty()) { 
                ArrayList<Integer> oneRes = new ArrayList<>();
                int size = queue.size();
                for (int i = 0; i < size; i++) { 
                    TreeNode poll = queue.poll();
                    if (poll.left != null) { 
                         queue.offer(poll.left);
                    }
                    if (poll.right != null) { 
                        queue.offer(poll.right);
                    }
                    if ((depth & 1) == 0) { 
                        // 从左到右添加结果
                        oneRes.add(poll.val);
                    } else { 
                        // 从右到左添加结果
                        oneRes.add(0, poll.val);
                    }
                }
                res.add(oneRes);
                depth++;
            }
            return res;
        }
    }

#### 12.有序数组转化二叉搜索树 ####

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

class Solution { 
        public TreeNode sortedArrayToBST(int[] nums) {         
            return helper(nums);
        }
        /* 每次都取出数组的中间位置的值作为根节点，然后以此为分割取两边作为子树 */
        private TreeNode helper(int[] nums) { 
            if (nums.length == 0) { 
                return null;
            }
            if (nums.length == 1) { 
                return new TreeNode(nums[0]);
            }
            int len = nums.length;
            // 有序数组的中间节点作为根节点
            TreeNode root = new TreeNode(nums[len / 2]);
            root.left = helper(Arrays.copyOfRange(nums, 0, len / 2));
            root.right = helper(Arrays.copyOfRange(nums, len / 2 + 1, len));
            return root;
        }
    }

#### 13.路径总和 ####

https://leetcode-cn.com/problems/path-sum-ii

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        
        public List<List<Integer>> pathSum(TreeNode root, int sum) { 
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> oneRes = new ArrayList<>();
            _pathSum(root, sum, res, oneRes);
            return res;
        }
        /* 回溯搜索 */
        private void _pathSum(TreeNode root, int sum,  List<List<Integer>> res, List<Integer> oneRes) { 
            if (root == null) { 
                return;
            }
            // 回溯终止条件，遇到叶子节点
            if (root.left == null && root.right == null) { 
                if (sum == root.val) { 
                    oneRes.add(sum);
                    res.add(new ArrayList<Integer>(oneRes));
                }
                return;
            }
            // 左子树不为空，新开辟一个路径搜索
            if (root.left != null) { 
                List<Integer> temp = new ArrayList<>(oneRes);
                temp.add(root.val);
                _pathSum(root.left, sum - root.val, res, temp);
            }
            // 右子树不为空，新开辟一个路径搜索
            if (root.right != null) { 
                oneRes.add(root.val);
                _pathSum(root.right, sum - root.val, res, oneRes);
            }
            return;
        }
    }

#### 14.二叉搜索树第k小节点 ####

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

class Solution { 
    
        /* 中序遍历第k次即获取到了第k小的元素 */
        public int kthSmallest(TreeNode root, int k) { 
            Stack<TreeNode> stack = new Stack<>();
            int count = 0;
            // 中序遍历
            while (!stack.isEmpty() || root != null) { 
                if (root != null) { 
                    stack.push(root);
                    root = root.left;
                } else { 
                    // 弹出的节点为中序遍历的节点
                    TreeNode pop = stack.pop();
                    root = pop.right;
                    // 已经弹出了第k个节点
                    if (++count == k) { 
                        return pop.val;
                    }
                }
            }
            return -1;
        }
    }

#### 15.找树左下角的值 ####

https://leetcode-cn.com/problems/find-bottom-left-tree-value

class Solution { 
        /* 按层序遍历获取最后一层第一个节点的值即为最左节点值 */
        public int findBottomLeftValue(TreeNode root) { 
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int res = 0;
            while (!queue.isEmpty()) { 
                // 当前的队列容量即为下一层的节点数量
                int size = queue.size();
                for (int i = 0; i < size; i++) { 
                    TreeNode poll = queue.poll();
                    if (poll.left != null) { 
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) { 
                        queue.offer(poll.right);
                    }
                    // 该层的第一个节点即为树左下角的值（最后一次更新的）
                    if (i == 0) { 
                        res = poll.val;
                    }
                }
            }
            return res;
     }
    }

#### 16.最长同值路径（节点间最长路径） ####

https://leetcode-cn.com/problems/longest-univalue-path

class Solution { 
        private int res = 0;
        public int longestUnivaluePath(TreeNode root) { 
           helper(root);
           return res;
        }
        /* 考虑同值情况下的最长路径 */
        private int helper(TreeNode root) { 
           // 递归终止条件
           if (root == null) { 
               return 0;
           }
           // 获取左子树最长同值路径
           int left = helper(root.left);
           // 获取右子树最长同值路径
           int right = helper(root.right);
           int leftNum = 0;
           int rightNum = 0;
           // 判断是否同值，同值则组成一条路径，累加+1，不同则为0
           if (root.left != null && root.left.val == root.val) { 
               leftNum += left + 1;
           }
           if (root.right != null && root.right.val == root.val) { 
               rightNum += right + 1;
           }
           // 更新最长路径
           res = Math.max(res, leftNum + rightNum);
           // 返回其中一条路径
           return Math.max(leftNum, rightNum);
        }
        
        
        /* 不考虑同值情况下的最长路径 */
        private int helper(TreeNode root) { 
            // 递归终止条件
            if (root == null) { 
                return 0;
            }
            // 递归获取左右子节点的最长同值路经
            int left = helper(root.left);
            int right = helper(root.right);
            res = Math.max(res, left + right);
            return Math.max(left, right) + 1;
        }
    }

#### 17.二叉树最近公共祖先 ####

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

class Solution { 
    
        private TreeNode res = null;
    
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            helper(root, p, q);
            return res;
        }
    
        private boolean helper(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null) { 
                return false;
            }
            int left = helper(root.left, p, q) ? 1 : 0; // 查看左子树含不含p或q
            int right = helper(root.right, p, q) ? 1 : 0; // 查看右子树含不含p或q
            int mid = (root == p || root == q) ? 1 : 0; // 当前节点是否等于p或1
            // 当满足以下条件，说明root就是最近公共祖先
            // 1. left = 1, right = 1, mid = 0 在左子树和右子树中分别含有pq
            // 2. left = 1, right = 0, mid = 1 在左子树中含有p或q，且root = p或q
            // 3. left = 0, right = 1, mid = 1 在右子树中含有p或q，且root = p或q
            if (left + right + mid >= 2) { 
                res = root;
                return true;
            }
            // 当前至少有一边查找到了p或q
            return left + right + mid >= 1;
        }
    }

#### 18.二叉搜索树最近公共祖先 ####

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

#### 19.二叉树的右视图 ####

https://leetcode-cn.com/problems/binary-tree-right-side-view

class Solution { 
        /* 层序遍历，收集右侧节点值 */
        public List<Integer> rightSideView(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            if (root == null) { 
                return res;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) { 
                int size = queue.size();
                for (int i = 0; i < size; i++) { 
                    TreeNode poll = queue.poll();
                    // 已经是一层的最右边,收集结果
                    if (i == size - 1) { 
                        res.add(poll.val);
                    }
                    if (poll.left != null) { 
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) { 
                        queue.offer(poll.right);
                    }
                }
            }
            return res;
        }
    }

#### 20.左叶子之和 ####

https://leetcode-cn.com/problems/sum-of-left-leaves

class Solution { 
    
        private int res = 0;
    
        /* 采用前序遍历 + 左叶子结点flag标识 */
        public int sumOfLeftLeaves(TreeNode root) { 
            preOrder(root, false);
            return res;
        }
        private void preOrder(TreeNode root, boolean flag) { 
            if (root == null) { 
                return;
            }
            if (flag && root.left == null && root.right == null) { 
                // 左叶子节点
                res += root.val;
            }
            preOrder(root.left, true); // 左直接子树一定会有左叶子结点
            preOrder(root.right, false); // 右直接子树不存在左叶子节点
        }
    }

### 六.链表 ###

#### 1.反转链表 ####

https://leetcode-cn.com/problems/reverse-linked-list

class Solution { 
        public ListNode reverseList(ListNode head) { 
            if (head == null) { 
                return null;
            }
            ListNode pre = head, cur = head.next, later = null;
            while (cur != null) { 
                // 先记录好later的指针
                later = cur.next;
                // 反转
                cur.next = pre;
                // 后移一位
                pre = cur;
                cur = later;
            }
            head.next = null;
            return pre;
        }
        
        // 递归地反转
        public ListNode reverseList(ListNode head) {  
           return helper(null, head);
       }
        private ListNode helper(ListNode pre, ListNode cur) { 
            //递归终止条件
            if (cur == null) { 
                return pre;
            }
            //递归过程
            ListNode later = cur.next;
            cur.next = pre;
            return helper(cur, later);
        }
    }

#### 2.反转局部链表 ####

https://leetcode-cn.com/problems/reverse-linked-list-ii/

class Solution { 
        public ListNode reverseBetween(ListNode head, int m, int n) { 
            if (head == null || head.next == null || m == n) { 
                return head;
            }
            // 获取到m、m前一个节点、n、n后一个节点
            ListNode preM = null, M = head, N = head, laterN = null;
            ListNode counter = head;
            int count = 0;
            while (counter != null) { 
                count++;
                preM = count == m - 1 ? counter : preM;
                M = count == m ? counter : M;
                N = count == n ? counter : N;
                laterN = count == n + 1 ? counter : laterN;
                counter = counter.next;
            }
            // 连接preM和N
            if (preM != null) { 
                preM.next = N;
            }
            // 反转M到N之间的链表
            ListNode pre = M, cur = M.next, later = null;
            while (cur != laterN) { 
                // 记录后一个节点
                later = cur.next;
                // 反转
                cur.next = pre;
                // 后移
                pre = cur;
                cur = later;
            }
            // 连接M与laterN
            M.next = laterN;
            // 如果preM为null，说明是从head开始反转到N的，返回N即可；不为null则说明反转了中间部分，返回head
            return preM == null ? N : head;
        }
    }

#### 3.删除链表重复节点 ####

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

class Solution { 
        public ListNode deleteDuplicates(ListNode head) { 
            // 为null或只存在一个节点
            if (head == null || head.next == null) { 
                return head;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            // 定义pre、cur和later指针
            ListNode pre = dummy, cur = head, later = cur.next;
            while (cur != null && later != null) { 
                if (later.val == cur.val) { 
                    // 当later和cur相等，则让later向后走，直到不等，然后pre与later连接，跳过相等部分
                    while (later != null && later.val == cur.val) { 
                        later = later.next;
                    }
                    // 跳过相等部分
                    pre.next = later;
                    cur = later;
                    // later注意判空
                    later = later == null ? null : later.next;
                } else { 
                    // later与cur不想等，三者都后移一位
                    pre = pre.next;
                    cur = cur.next;
                    later = later.next;
                }
            }
            return dummy.next;
        }
    }

#### 4.链表中环的入口 ####

https://leetcode-cn.com/problems/linked-list-cycle-ii/

public class Solution { 
        /* 使用HashSet记录遍历过的节点，当出现了重复节点时即为环的入口 */
        public ListNode detectCycle(ListNode head) { 
            HashSet<ListNode> set = new HashSet<>();
            while (head != null) { 
                if (set.contains(head)) { 
                    return head;
                } else { 
                    set.add(head);
                    head = head.next;
                }
            }
            return head;
        }
    
    
        /* 使用快慢指针相遇找到环形链表的一点，然后从链表头开始于该节点一起往前走，链表头与该节点相遇即为环的入口 */
        public ListNode detectCycle(ListNode head) { 
            if (head == null) { 
                return null;
            }
            ListNode slow = head, fast = head;
            // 寻找环状链表中的一点
            while (true) { 
                if (slow == null || fast == null || fast.next == null) { 
                   // 不成环
                   return null;
                }
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) { 
                    // 相遇
                    break;
                }
            }
            ListNode p1 = head, p2 = slow;
            // 寻找链表头与slow相遇的点
            while (p1 != p2) { 
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }

#### 5.链表是否有环 ####

https://leetcode-cn.com/problems/linked-list-cycle

public class Solution { 
        public boolean hasCycle(ListNode head) { 
            if (head == null) { 
                return false;
            }
            ListNode slow = head, fast = head;
            while (true) { 
                if (slow == null || fast == null || fast.next == null) { 
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) { 
                    return true;
                }
            }
        }
    }

#### 6.相交链表公共节点 ####

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            // 先获取到headA和headB的长度，然后在进行长度的对其
            int len1 = 0, len2 = 0;
            ListNode counterA = headA, counterB = headB;
            while (counterA != null) { 
                len1++;
                counterA = counterA.next;
            }
            while (counterB != null) { 
                len2++;
                counterB = counterB.next;
            }
            // 头部对齐
            int x = Math.abs(len1 - len2);
            if (len1 > len2) { 
                for (int i = 0; i < x; i++) { 
                    headA = headA.next;
                }
            }
            if (len2 > len1) { 
                for (int i = 0; i < x; i++) { 
                    headB = headB.next;
                }
            }
            // 相遇则为起点
            while (headA != headB) { 
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }

#### 7.复杂链表的复制 ####

https://leetcode-cn.com/problems/copy-list-with-random-pointer

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */
    class Solution { 
    
        
        
    
        /* 使用HashMap存储旧节点对应新节点的映射，然后按照旧节点关系建立新节点的关系 */
        public Node copyRandomList(Node head) { 
            if (head == null) { 
                return null;
            }
            HashMap<Node, Node> map = new HashMap<>();
            Node cur = head;
            // 存储新旧节点映射关系
            while (cur != null) { 
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            // 根据旧节点建立新节点件关系
            boolean first = true;
            Node res = null;
            while (head != null) { 
                map.get(head).next = map.get(head.next);
                map.get(head).random = map.get(head.random);
                if (first) { 
                    res = map.get(head);
                    first = false;
                }
                head  = head.next;
            }
            return res;
        }
    }

#### 8.合并两个有序链表 ####

https://leetcode-cn.com/problems/merge-two-sorted-lists

class Solution { 
        /* 归并排序的mereg函数 */
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            ListNode dummy = new ListNode(-1);
            ListNode res = dummy;
            while (l1 != null && l2 != null) { 
                if (l1.val <= l2.val) { 
                    dummy.next = l1;
                    l1 = l1.next;
                } else { 
                    dummy.next = l2;
                    l2 = l2.next;
                }
                dummy = dummy.next;
            }
            if (l1 != null) { 
                dummy.next = l1;
            }
            if (l2 != null) { 
                dummy.next = l2;
            }
            return res.next;
        }
    }

#### 9.删除链表倒数第k个节点 ####

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
            if (head == null) { 
                return null;
            }
            // 让fast节点比slow先走n步
            ListNode slow = head, fast = head;
            for (int i = 0; i < n; i++) { 
                fast = (fast == null) ? null : fast.next;
            }
            // 删除倒数第N个节点
            ListNode pre = null;
            while (fast != null) { 
                pre = slow;
                slow = slow.next;
                fast = fast.next;
            }
            // 判断是否删除的是头节点
            if (pre == null) { 
                return head.next;
            }
            // 非头节点
            pre.next = slow.next;
            return head;
        }
    }

#### 10.两数相加 ####

https://leetcode-cn.com/problems/add-two-numbers

class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            int x = 0; // 进位
            // 1.双方都不为空都情况，累加并带上进位
            while (l1 != null && l2 != null) { 
                int sum = l1.val + l2.val + x; // 考虑进位
                x = sum / 10; // 获取新的进位
                int val = sum % 10; // 获取新的节点值
                cur.next = new ListNode(val);
                cur = cur.next;
                l1 = l1.next;
                l2 = l2.next;
            }
            // 2.有一者为空的情况，只加上不为空的一方
            while (l1 != null) { 
                int sum = l1.val + x;
                x = sum / 10;
                int val = sum % 10;
                cur.next = new ListNode(val);
                cur = cur.next;
                l1 = l1.next;
            }
            while (l2 != null) { 
                int sum = l2.val + x;
                x = sum / 10;
                int val = sum % 10;
                cur.next = new ListNode(val);
                cur = cur.next;
                l2 = l2.next;
            }
            // 3.最后判断是否发生溢出
            if (x == 1) { 
                cur.next = new ListNode(1);
            }
            return dummy.next;
        }
    }

#### 11.将有序链表转化为二叉搜索树 ####

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        /* 确定中间的节点作为根节点，不断地递归即可（类似于从前序和中序构造二叉树，不过这里直接从中序的中间节点取值） */
        public TreeNode sortedListToBST(ListNode head) { 
            return helper(head);
        }
        private TreeNode helper(ListNode head) { 
            if (head == null) { 
                return null;
            }
            if (head.next == null) { 
                return new TreeNode(head.val);
            }
            // 快慢指针确定中间节点以及中间节点前一个节点
            ListNode slow = head, fast = head, pre = null;
            while (slow != null && fast != null && fast.next != null) { 
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            // slow即为根节点
            TreeNode root = new TreeNode(slow.val);
            // 获取到右区间
            ListNode right = slow.next;
            // 断链
            pre.next = null;
            slow.next = null;
            // 递归构建左右子树
            root.left = helper(head);
            root.right = helper(right);
            return root;
        }
    }

### 七.栈 ###

#### 1.用两个栈实现队列 ####

https://leetcode-cn.com/problems/implement-queue-using-stacks

class MyQueue { 
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;
    
        /** Initialize your data structure here. */
        public MyQueue() { 
            stack1 = new Stack<>(); // 中转栈
            stack2 = new Stack<>(); // 值栈
        }
        
        /** Push element x to the back of queue. */
        public void push(int x) { 
            move(stack2, stack1);
            stack1.push(x);
            move(stack1, stack2);
        }
        private void move(Stack<Integer> s1, Stack<Integer> s2) { 
            while (!s1.isEmpty()) { 
                s2.push(s1.pop());
            }
        }
        
        /** Removes the element from in front of queue and returns that element. */
        public int pop() { 
            return stack2.pop();
        }
        
        /** Get the front element. */
        public int peek() { 
            return stack2.peek();
        }
        
        /** Returns whether the queue is empty. */
        public boolean empty() { 
            return stack2.isEmpty();
        }
    }

#### 2.含有getMin的栈 ####

https://leetcode-cn.com/problems/min-stack/

class MinStack { 
        private Stack<Integer> stack;
        private Stack<Integer> minStack;
    
        /** initialize your data structure here. */
        public MinStack() { 
            stack = new Stack<>();
            minStack = new Stack<>();
        }
        
        public void push(int x) { 
            stack.push(x);
            // 更新minStack使得其栈头最小
            if (minStack.isEmpty() || !minStack.isEmpty() && x <= minStack.peek()) { 
                minStack.push(x);
            }
        }
        
        public void pop() { 
            int pop = stack.pop();
            // 如果弹出了当前最小值，删去minStack栈头
            if (pop == minStack.peek()) { 
                minStack.pop();    
            }
        }
        
        public int top() { 
            return stack.peek();
        }
        
        public int getMin() { 
            return minStack.peek();
        }
    }
    
    /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

#### 3.有效括号 ####

https://leetcode-cn.com/problems/valid-parentheses

class Solution { 
        /* 使用栈来做匹配 */
        public boolean isValid(String s) { 
            if ("".equals(s.trim())) { 
                return true;
            }
            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 (c == '(' || c == '{' || c == '[') { 
                    stack.push(c);
                }
                // 校验
                if (c == ')' || c == '}' || c == ']') { 
                    // 没有左括号可匹配或弹出不匹配返回falsea
                    if (stack.isEmpty() || c != map.get(stack.pop())) { 
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

#### 4.下一个更大元素 ####

https://leetcode-cn.com/problems/next-greater-element-i

class Solution { 
        public int[] nextGreaterElement(int[] nums1, int[] nums2) { 
            // 先使用单调栈获取到nums2中每个元素对应的下一个更大元素存储至HashMap中
            Stack<Integer> stack = new Stack<>(); // 由上之下递增
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums2.length; i++) { 
                while (!stack.isEmpty() && nums2[i] > stack.peek()) { 
                    // 不满足单调栈
                    map.put(stack.pop(), nums2[i]);
                }
                stack.push(nums2[i]);
            }
            // stack中剩下的即为找不到下一个更大元素的
            while (!stack.isEmpty()) { 
                map.put(stack.pop(), -1);
            }
            // 遍历nums1，使用map获取对应元素的下一个更大元素
            for (int i = 0; i < nums1.length; i++) { 
                nums1[i] = map.get(nums1[i]);
            }
            return nums1;
        }
    }

#### 5.每日温度 ####

https://leetcode-cn.com/problems/daily-temperatures/

class Solution { 
        /* 使用单调栈来记录某个元素索引的下一个最大元素索引，之后相建减即为天数 */
        public int[] dailyTemperatures(int[] nums) { 
            int[] res = new int[nums.length];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < nums.length; i++) { 
                while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { 
                    // 不满足单调栈，弹出
                    int index = stack.pop();
                    // 计算天数
                    res[index] = i - index;
                }
                // 满足单调栈结构
                stack.push(i);
            }
            return res;
        }
    }

#### 6.验证栈序列 ####

https://leetcode-cn.com/problems/validate-stack-sequences

class Solution { 
        public boolean validateStackSequences(int[] pushed, int[] popped) { 
            if (pushed.length != popped.length) { 
                return false;
            }
            Stack<Integer> stack = new Stack<>();
            int index = 0; // 当前匹配到的弹出序列位置
            for (int i = 0; i < pushed.length; i++) { 
                stack.push(pushed[i]);
                // 开始匹配
                while (!stack.isEmpty() && stack.peek() == popped[index]) { 
                    // 弹出以表示匹配
                    stack.pop();
                    // 索引++，表示匹配
                    index++;
                }
            }
            // 匹配完则说明完全匹配
            return stack.isEmpty();
        }
    }

#### 7.最长有效括号 ####

https://leetcode-cn.com/problems/longest-valid-parentheses/

### 八.其他 ###

#### 1.36进制的加法与整形转化 ####

/* * @Author ARong * @Description 36进制的正整数相加，返回十进制结果 * @Date 2020/2/17 11:45 上午 * @Param [a, b] * @return long **/
            private long plus(String a, String b) { 
                String value36bit = get36BitPlus(a, b);
                System.out.println(value36bit);
                long value10bit = get10BitValue(value36bit);
                System.out.println(value10bit);
                return value10bit;
            }
    
        /* * @Author ARong * @Description 将36进制转化为10进制 * @Date 2020/2/17 12:13 下午 * @Param [value36bit] * @return long **/
        private long get10BitValue(String value36bit) { 
            // 这里不考虑正负
            long res = 0;
            char[] chars = value36bit.toCharArray();
            int n = chars.length;
            for (int i = n - 1; i >= 0; i--) { 
                int up = n - i - 1;
                res += getInt(chars[i]) * Math.pow(36, up);
            }
            return res;
        }
    
        /* * @Author ARong * @Description 36位字符串相加 * @Date 2020/2/17 12:12 下午 * @Param [a, b] * @return java.lang.String **/
        private String get36BitPlus(String a, String b) { 
            StringBuilder res = new StringBuilder();
            int x = 0; // 进位
            // 36进制相加
            char[] chars1 = a.toCharArray();
            char[] chars2 = b.toCharArray();
            int n1 = chars1.length;
            int n2 = chars2.length;
            int cur1 = n1 - 1, cur2 = n2 - 1;
            // 两者都有位
            while (cur1 >= 0 && cur2 >= 0) { 
                int sum = getInt(chars1[cur1--]) + getInt(chars2[cur2--]) + x;
                x = sum / 36; // 进位
                sum = sum % 36; // 考虑溢出
    
                res.insert(0, getChar(sum)); // 添加36位计算结果
            }
            // chars1有位
            while (cur1 >= 0) { 
                int sum = getInt(chars1[cur1--]) + x;
                x = sum / 36; // 进位
                sum = sum % 36; // 考虑溢出
    
                res.insert(0, getChar(sum)); // 添加36位计算结果
            }
            // chars2有位
            while (cur2 >= 0) { 
                int sum = getInt(chars2[cur2--]) + x;
                x = sum / 36; // 进位
                sum = sum % 36; // 考虑溢出
    
                res.insert(0, getChar(sum)); // 添加36位计算结果
            }
            // 判断最后是否溢出
            if (x > 0) { 
                res.insert(0, getChar(x));
            }
            return res.toString();
        }
    
        /* * @Author ARong * @Description 将数字转化为36位 * @Date 2020/2/17 1:07 下午 * @Param [num] * @return char **/
        private char getChar(int num) { 
            if (num >= 0 && num <= 9) { 
                // '0'的ascii码为48
                int n = 48 + num;
                return (char)n;
            }
            if (num >= 10 && num <= 35) { 
                // 'a'的ascii码为97
                int n = 97 + (num - 10);
                return (char)n;
            }
            return '0';
        }
    
        /* * @Author ARong * @Description 通过字符获取十进制 * @Date 2020/2/17 1:06 下午 * @Param [c] * @return int **/
        private int getInt(char c) { 
            if (c >= '0' && c <= '9') { 
                return c - '0';
            }
            if (c >= 'a' && c <= 'z') { 
                return 10 + (c - 'a');
            }
            return -1;
        }

#### 2.（SQL）排名排序 ####

https://leetcode-cn.com/problems/rank-scores/

# 第一种解法
    select s1.Score,
    # 查询比s1.Score高的分数的去重数量，即为当前分数的排名
    (select count(distinct s2.Score) from Scores s2 where s2.Score >= s1.Score) as Rank
    from Scores s1
    # 注意降序排序
    order by s1.Score desc
    
    
    # 第二种解法，MySQL 8之后可以使用窗口函数来统计排名，主要有RANK()/DENSE_RANK()/ROW_NUMBER()
    select s1.Score, dense_rank(order by s1.Score DESC)  as Rank
    from Score s1

#### 3.（SQL）第二高的薪水 ####

https://leetcode-cn.com/problems/second-highest-salary/

select 
    # ifnull(xx, null)，当xx为null时，返回null
    ifnull(
    # 使用limit 1，1限制查找第1行开始的第一个数据，即第二高的排名
    (select distinct e.Salary from Employee e order by e.Salary desc limit 1,1),
    null)  
    as SecondHighestSalary