---
# System prepended metadata

title: leetcode

---

# leetcode
## 排序

<img src="https://images2018.cnblogs.com/blog/849589/201804/849589-20180402133438219-1946132192.png" alt="img" style="zoom:60%;" />

### 冒泡排序 BubbleSort  O(n²)

> 一次比较两个元素，如果顺序错误就交换回来

1. 比较相邻的元素，如果第一个比第二个大，就交换
2. 对每一对相邻元素作同样工作，从开始第一对到结尾最后一对，
3. 针对所有元素重复以上步骤，除了最后一个
4. 重复1-3，直到完成

~~~java
public void static BubbleSort(int[] arr){
    int temp;//临时变量
    boolean flag;//标志位，优化后的冒泡用
    for(int i=0;i<arr.length-1;i++){
        flag = true;
        for(int j=arr.length-1;j>i;j--){
            if(arr[j] < arr[j-1]){
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
                flag = false;// 走到这里说明顺序没排好
            }
        }
        if(flag) break; // 如果遍历标志位没有变化，说明顺序排好，直接退出
    }
}
~~~

### 选择排序 SelctionSort    O(n²)

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

```java
public static void SelctionSortMain(int [] arr){
    // 这里arr.length-1是因为不需要检查最后一个
    for (int i = 0; i < arr.length - 1; i++) {
        // 最小的下标
        int minIndex = i;
        // 这里i+1是因为不需要检查自己
        for (int j = i + 1; j < arr.length; j++) {
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        // 如果最小的下标不是i，说明后面有更小的，置换
        if(minIndex != i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
```

### 插入排序 InsertionSort  O(n²)

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

```java
public static void InsertSort(int [] arr){
    //这里=1是因为已排序序列最少一个
    for (int i = 1; i < arr.length; i++) {
        // 这是临时存最小的值，默认i是最小的
        int temp = arr[i];
        // 遍历标志参数，j之前的是已排序的，之后是未排序的
        int j = i;
        // 临时存最小的值，与前一个值进行比较
        while (j > 0 && temp < arr[j - 1]) {
            // 如果前一个值大，吧前面的大值赋给小值
            arr[j] = arr[j - 1];
            // 已排序的列表前推以为
            j--;
        }
        // 如果值改变，吧前面的大值改为最小的值
        if(j!=i){
            //这时候的j是已排序的，比最小值还小的值的下标
            arr[j] = temp;
        }
    }
}
```

### 希尔排序 ShellSort  O(n2)

按照设定的间隔，将数组分为若干份，进行插入排序，也叫**缩小增量排序**。

```java
public static void shellSort(int[] arr) {
    // 这里的d是指针步进,
    int d = arr.length / 2;
    while (d >= 1) {
        // 这里指针从后半段开始
        for (int i = d; i < arr.length; i++) {
            int rt = arr[i];
            // 这里j按步进走
            for (int j = i - d; j >= 0; j -= d) {
                if (rt < arr[j]) {
                    arr[j + d] = arr[j];
                    arr[j] = rt;
                } else break;
            }
        }
        // 每走一遍间隔减半
        d /= 2;
    }
}
```

### 并归排序

> 归并排序 - 采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素， 再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。

### 快排

> 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
>
> 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
>
> - 从数列中挑出一个元素，称为 “基准”（pivot）；
> - 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
> - 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

~~~java
static void qSort(int[] arr, int s, int e) {
        int left = s, right = e;
        if (left < right) {
            int temp = arr[left];
            while (left < right) {
                while (left < right && arr[right] >= temp) right--;
                if (left < right) arr[left] = arr[right];
                while (left < right && arr[left] < temp) left++;
                if (left < right) arr[right] = arr[left];
            }
            arr[left] = temp;
            qSort(arr, s, left);
            qSort(arr, left + 1, e);
        }
    }
~~~





## 数组

### [704. 二分查找](https://leetcode-cn.com/problems/binary-search)

> 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

注意边界问题，牢记区间定义

```java
// nums = [-1,0,3,2,9 ,12,0,1,2,3], target = -1
public static int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right){// 当右下标小于或等于左下标时停止
        int middle = (left+(right-left))/2; 
        if(target < nums[middle]){// 当目标值小于中位值时
            right = middle -1  // 目前中位值为9，middle为4，4已经被判断，所以middle-1
        }else if(target > nums[middle]){
            left = middle + 1 // 4已经被判断，middle+1
        }else{
            return middle;
        }
    }
    return -1;
}
```

###  [27. 移除元素](https://leetcode-cn.com/problems/remove-element)

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

>给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
>
>不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。
>
>元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

~~~java
// nums = [-1,0,3,2,9,12,0,1,2,3], target = 2
public static int removeElement(int[] nums, int val) {
	int slowIndex = 0;// 定义一个慢指针
    int fastIndex; // 定义一个快指针
    for(fastIndex = 0; fastIndex < nums.length; fastIndex++){// 遍历
        if(nums[fastIndex] != val){ // 快指针指向了一个非目标元素时
            // 如果没有跳过，这步无所谓；如果中间有目标元素，会被替换成目标元素的下一个元素，保证慢指针前永远正确
            nums[slowIndex] = nums[fastIndex]; 
            slowIndex ++; // 慢指针+1
        }
    }
    return slowIndex;
}

~~~

### [977. 有序数组的平方](https://leetcode-cn.com/problems/squares-of-a-sorted-array)

> 给你一个按 非递减顺序(可能重复的递增排序) 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序

~~~java
//nums = [-4,-1,0,3,10]    
public int[] sortedSquares(int[] nums) {
	int left = 0;
    int right = nums.length -1;
    int index = nums.length -1;
    int[] answer = new int[nums.length];
    while (left <= right){
        if(nums[left]*nums[left] >= nums[right]*nums[right]){
            answer[index--] = nums[left]*nums[left++];
        }else{
            answer[index--] = nums[right]*nums[right--];
        }
    }
    return answer;
}
~~~

###  [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum)

**滑动窗口**：就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果.

> 给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

~~~java
    //target = 7, nums = [2,3,1,2,4,3]    public static int minSubArrayLen(int target, int[] nums) {        int left = 0;        int sum = 0;        int lon = 100000; //题目中nums最长为10^5        for (int right = 0; right <= nums.length -1 ; right++) {            sum += nums[right]; // 获取从0到右边框的全部值的和            while (sum >= target){ // 如果大于目标值 进入                // 取最小lon，+1是因为right和left为坐标，+1取长度                lon = Math.min(lon, right - left + 1);                sum -= nums[left++];// 在全部值中减去0到左边框的值            }        }        return lon == 100000 ? 0 : lon;    }
~~~

### [59. 螺旋矩阵 II](https://leetcode-cn.com/problems/spiral-matrix-ii)

> 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

~~~java
// n = 3public static int[][] generateMatrix(int n) {    	/*            1,2,3            8,9,4            7,6,5         */    int[][] res = new int[n][n];    // 坐标    int startX = 0;    int startY = 0;    int offset = 1;//偏移量    int loop = n/2;//循环次数    int count = 1;// 计数    while (loop>0){        //创建遍历用坐标用初始坐标赋值        int i = startX;        int j = startY;        //固定x轴，遍历y轴，并少遍历offset位（向左偏移一位）        for (;j<startY+n-offset;j++){            //x轴可以是初始坐标            res[startX][j] = count++;        }        //固定y轴，遍历x轴，并少遍历offset位（上偏移一位）        for(;i<startX+n-offset;i++){            //y轴需要是结尾坐标            res[i][j] = count++;        }        //再次固定x轴，遍历y轴，并少遍历offset位（向右偏移一位）        for(;j>startY;j--){            //x需要结尾坐标，y需要遍历坐标            res[i][j] = count++;        }        //再次固定y轴，遍历x轴，并少遍历offset位（向右偏移一位）        for(;i>startX;i--){            //x需要遍历坐标，y需要遍结尾坐标            res[i][j] = count++;        }        //x,y坐标各加一，从（1，1）开始        startX++;        startY++;        //循环次数减一        loop--;        //一次偏移两位，因为外层左侧和右侧各需偏移一次一，只需要之前放四个，现在只需要放两个        offset+=2;    }    //如果不是偶数，需要插入中心数    if (n%2 != 0) {        int mid = n/2;        res[mid][mid] = count;    }    return res;}
~~~

## 链表

### 力扣创建的节点

```java
class ListNode {    int val;    ListNode next;    ListNode() {}    ListNode(int val) { this.val = val; }    ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
```

### [24. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs)

> 终止条件：链表剩余节点不足2；返回值：处理好的链表
>
> 本级递归做什么：将两个节点交换

```java
    public static ListNode swapPairs(ListNode head) {        // 一共为三个节点 head-》 head2（next）-》 待排链表        // 为空终止        if(head==null||head.next==null) return head;        // 将节点的下一个节点储存为2号节点        ListNode head2 = head.next;        // 节点的next指向待排链表，待排链表从head2的指向节点开始        head.next = swapPairs(head2.next);        // head2的next指向头节点，到此节点调换完成        head2.next = head;        // 此时为head2-》 head -》 待排，返回head2        return head2;    }
```



### [203. 移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements)

> 删除链表中等于给定值 val 的所有节点。

```java
//ListNode{val=2, next=ListNode{val=3, next=ListNode{val=4, next=null}}}public static ListNode removeElements(ListNode head, int val) {        if (head==null)return head;// 如果为空，直接抛出        ListNode virtual = new ListNode(-1,head);// 在链表前插入虚拟节点        ListNode pro = virtual;// 创建一个带虚拟节点的临时链表        while (head!=null){// 参数为空时停止            if (head.val == val){//判断链表参数的val是否等于目标值                // 将当前链表参数的指针，赋值给临时链表的指针                pro.next = head.next;            }else {                // 因为目标参数比临时链表少一位，所以赋值等于临时链表指向第二个节点                pro = head;            }            // head删除第一个元素，最终一个元素为null            head = head.next;        }        return virtual.next;// 返回去掉虚拟链表的链表}
```

### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list)

> 创建一个返回列表，一个待排链表，一个临时存储

~~~java
    public static ListNode reverseList(ListNode head) {        //prev作为返回的列表，prev加        ListNode prev = null;        // cur作为初始列表，cur减        ListNode cur = head;        // temp作为临时存储，存一下变换的节点        ListNode temp = null;        // 初始节点为空，说明走完了，停止        while (cur != null){            // 临时节点存储为初始节点的next指针，这里是待排的            temp = cur.next;            // 初始节点的next指针指向返回的,这时已经反转好了            cur.next = prev;            // 将反转好的给返回列表            prev = cur;            // cur还原为待排的            cur = temp;        }        return prev;    }
~~~

### [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list)

> 双指针法

~~~java
public ListNode removeNthFromEnd(ListNode head, int n) {        // 设置头节点，方便处理        ListNode listNode = new ListNode(-1, head);        // 创建双指针        ListNode fast = listNode;        ListNode slow = listNode;        // 快指针先走n步        while (n >= 0){            fast = fast.next;            n--;        }        // 双指针同时走，快指针因为先走了n步，慢指针正好剩余n个节点        while (fast != null){            fast = fast.next;            slow = slow.next;        }        //慢指针的下一个节点就是要删除的节点，这里省略一步释放        slow.next = slow.next.next;        // 因为slow为listNode的引用，所以指针修改后，listNode同步修改        // 因为listNode添加了虚拟头节点，所以返回next节点        return listNode.next;    }
~~~



### [面试题 02.07. 链表相交](https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci)

> 给你两个单链表的头节点 `headA` 和 `headB` ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 `null` 
>
> 快慢指针，链表叠加，如果循环，总会相遇

~~~java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        // 创建两个临时列表        ListNode curA = headA;        ListNode curB = headB;        // 如果两个链表相等，程序退出，最多遍历a+b的长度        while (curA != curB){            // 如果a遍历完，遍历b，如果都为空，说明没有相交，退出            curA = (curA == null ? headB : curA.next);            curB = (curB == null ? headA : curB.next);        }        // 因为ab相等，所以随便返回        return curA;    }
~~~

### [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii)

> 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `null`。
>
> 快慢指针相遇说明有环，从头节点到相遇节点中间的点是入口

~~~java
    public static ListNode detectCycle(ListNode head) {        // 创建快慢指针        ListNode fast = head;        ListNode slow = head;        // 如果快指针走完了，说明没有环        while (fast != null && fast.next != null){            // 快的走两步，慢的走一步            fast = fast.next.next;            slow = slow.next;            // 如果快慢相遇了说明有环            if (slow == fast) {                // 创建两个下标指针，分别指向头节点和相遇节点                ListNode index1 = head;                ListNode index2 = fast;                // 同时走一步，相遇的点就是环形链表的入环点                while (index1 != index2) {                    index1 = index1.next;                    index2 = index2.next;                }                return index1;            }        }        return null;    }
~~~

## 哈希

### [242. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram)

> 创建hash数组

~~~java
    public static boolean isAnagram(String s, String t) {        // 创建一个列表用作hash映射        int[] record = new int[26];        // 将string转为char列表，按照asc2码存入hash表，位置有则+1        for(char a : s.toCharArray()){            record[a - 'a']++;        }        // 第二个string位置有则-1        for(char b : t.toCharArray()){            record[b -'a']--;        }        // 遍历hash列表，如果没有减完返回false        for(int c : record){            if (c != 0) {                return false;            }        }        return true;    }
~~~

### [349. 两个数组的交集](https://leetcode-cn.com/problems/intersection-of-two-arrays)

> 创建set哈希数组

~~~java
   public static int[] intersection(int[] nums1, int[] nums2) {        // 创建两个set数组        Set<Integer> set1 = new HashSet<>();        Set<Integer> resSet = new HashSet<>();        // 将数组1一个个插入set数组1，这里完成去重        for (int a : nums1) {            set1.add(a);        }        //将数组2一个个插入set数组2        for (int b : nums2) {            // 如果数组1不存在这个数就不插入了            if(set1.contains(b)){                resSet.add(b);            }        }        // 创建返回用的数组，长度为set数组2的长度        int[] res = new int[resSet.size()];        int index = 0;        // 一个个插入后返回        for (int c : resSet) {            res[index++] = c;        }        return res;    }
~~~

### [202. 快乐数](https://leetcode-cn.com/problems/happy-number)

> 只需存一下，用hashset

~~~java
    public static boolean isHappy(int n) {        // 创建hashset数组        Set<Integer> sumSet = new HashSet<>();        // 如果set数组里存在目标参数 或者等于1，终止        while (!sumSet.contains(n) && n != 1) {            // 先插入一下set数组            sumSet.add(n);            // 调用算数的方法            n = getSum(n);        }        // 如果是1返回true        return n == 1;    }    public static int getSum(int n) {        // 创建返回参数        int res = 0;        // 可能存在多位数情况，所以需要逐位乘方        while (n > 0){            // 获取参数 末尾的数            int one = n % 10;            // 乘方            res += one * one;            // 去除尾数            n = n / 10;        }        return res;    }
~~~

### [1. 两数之和](https://leetcode-cn.com/problems/two-sum)

> 需要存下标和数，用hashmap

~~~java
    public static int[] twoSum(int[] nums, int target) {        // 创建返回列表        int[] res = new int[2];        // 创建hashmap        Map<Integer,Integer> map = new HashMap<>();        // 遍历输入数组        for (int i = 0; i < nums.length; i++) {            // 目标值减去数组各个参数，得到key值            int temp = target - nums[i];            // 判断key值是否存在            if(map.containsKey(temp)){                // 如果存在，放入key对应的value值，和当前下标                res[0] = i;                res[1] = map.get(temp);            }else {                // 如果不在，数组种遍历的参数和下标放入hashmap                map.put(nums[i], i);            }        }        return res;    }
~~~

### [454. 四数相加 II](https://leetcode-cn.com/problems/4sum-ii)

> 存储两个值，和数和value，value用于计算

~~~java
    public static int[] twoSum(int[] nums, int target) {        // 创建返回列表        int[] res = new int[2];        // 创建hashmap        Map<Integer,Integer> map = new HashMap<>();        // 遍历输入数组        for (int i = 0; i < nums.length; i++) {            // 目标值减去数组各个参数，得到key值            int temp = target - nums[i];            // 判断key值是否存在            if(map.containsKey(temp)){                // 如果存在，放入key对应的value值，和当前下标                res[0] = i;                res[1] = map.get(temp);            }else {                // 如果不在，数组种遍历的参数和下标放入hashmap                map.put(nums[i], i);            }        }        return res;    }
~~~

### [383. 赎金信](https://leetcode-cn.com/problems/ransom-note)

> 创建定长的hashlist

~~~java
    public boolean canConstruct(String ransomNote, String magazine) {        // 创建一个列表用作hash映射        int[] record = new int[26];        // 将string转为char列表，按照asc2码存入hash表，位置有则+1        for(char a : magazine.toCharArray()){            record[a - 'a']++;        }        // 第二个string位置有则-1        for(char b : ransomNote.toCharArray()){            record[b -'a']--;        }        // 遍历hash列表，如果没有减完返回false        for(int c : record){            if (c < 0) {                return false;            }        }        return true;    }
~~~

### [15. 三数之和](https://leetcode-cn.com/problems/3sum)

> for循环固定一个指针+双指针法
>
> 四数之和外层多家一个for循环，内层从i+1开始
>
> 同理，五数之和，六数之和也增加相应fou循环

~~~java
public static List<List<Integer>> threeSum(int[] nums) {        /*            三指针法，最左和最右+移动指针，            如果三指针的值相加大于0，需要减小指针，所以最右向左移动一格，            反之最左向右移动，如果指针相遇，停止        */        List<List<Integer>> res = new ArrayList<>();        Arrays.sort(nums);        // 最左指针位置调整        for (int left = 0; left < nums.length; left++) {            // 题目要求三数之和大于0，因为数组从小到大，当最左指针大于0，不可能成立            if (nums[left] > 0) {                return res;            }            // 如果数和上一个数相同，放弃本次循环，因为数值相同，结果也相同            if (left > 0 && nums[left] == nums[left - 1]) {                continue;            }            // 中指针是左指针加1，右指针在最右            int middle = left + 1;            int right = nums.length - 1;            // 如果右指针与中指针相遇，循环结束            while (right > middle){                // 计算三个指针值的和                int sum = nums[left] + nums[middle] + nums[right];                // 和比目标值大                if (sum > 0) {                    // 最右向左移动一格,减小和值                    right--;                // 和比目标值小                } else if (sum < 0) {                    // 中间向右移动一格，增加和值                    middle++;                } else {                    // 将和为目标值的三个数放入list中，并添加到返回数组                    res.add(Arrays.asList(nums[left], nums[middle], nums[right]));                    // 如果当前值的下一个值与 当前值相等，忽略下一个值                    while (right > middle && nums[right] == nums[right - 1]) right--;                    while (right > middle && nums[middle] == nums[middle + 1]) middle++;                    // 正常移动一位                    right--;                    middle++;                }            }        }        return res;    }
~~~

## 字符串

### [344. 反转字符串](https://leetcode-cn.com/problems/reverse-string)

> 双指针法

```java
public static void reverseString(char[] s) {    // 定义头尾两个指针    int left = 0;    int right = s.length - 1;    // 如果左指针小于右指针，正常执行    while (left < right) {        // 指向的值换位，这里可以用异或 ^        char temp = s[left];        s[left] = s[right];        s[right] = temp;        // 左右指针移动        left++;        right--;    }}
```

### [541. 反转字符串 II](https://leetcode-cn.com/problems/reverse-string-ii)

> 控制遍历间隔即可

```java
public static String reverseStr(String s, int k) {    // 将字符串拆分成字符数组    char[] chars = s.toCharArray();    // 题目要求每计数至2k，就反转前k个字符，所以这里遍历间隔为2k    for (int i = 0; i < s.length(); i += 2 * k) {        // 创建双指针        int start = i;        // 因为只反转前k个字符，如果不满足k，取相应长度反转        int ent = Math.min(s.length() - 1, start + k - 1);        // 如果左指针不小于右指针，遍历结束        while (start < ent) {            // 指向的值换位，这里可以用异或 ^            char temp = chars[start];            chars[start] = chars[ent];            chars[ent] = temp;            // 左右指针移动            start++;            ent--;        }    }    // 将字符列表转为字符串输出    return new String(chars);}
```

### [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)

> 创建StringBuilder可扩数组，方便扩充空格

~~~java
public static String replaceSpace(String s) {        // 创建可变字符串        StringBuilder str = new StringBuilder();        // 遍历字符串，如果字符为空格，可变字符串增加两位        for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) == ' ') {                str.append("  ");            }        }        // 左指针获得初始字符串末尾下表        int left = s.length() - 1;        // 源字符串和可变相加        s += str.toString();        // 右指针获得扩长后字符串末尾下表        int right = s.length() -1;        // 创建字符列表方便插入修改        char[] ch = s.toCharArray();        // 指针小于0结束        while (left >= 0) {            // 如果指针指向空格，字符列表按位依次添加%20，反之复制            if(s.charAt(left) == ' '){                ch[right--] = '0';                ch[right--] = '2';                ch[right] = '%';            }else {                ch[right] = s.charAt(left);            }            left--;            right--;        }        return String.valueOf(ch);    }
~~~

### [151. 翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)

~~~java
public String reverseWords(String s) {    // 倒放，从后往前将单词放入字符，完成反转    int left = s.length() - 1;    int right ;    StringBuilder res = new StringBuilder();    while (left >= 0){        // 从后往前找到第一个非空格的下标        while (left >= 0 && s.charAt(left) == ' ') left--;        // 如果这时候等于-1，说明已经没有单词了        if(left < 0) break;        // 下标赋值给指针2，这时2指向从后往前第一个单词右侧        right = left;        // 指针1找到当前单词的左边界        while (left >= 0 && s.charAt(left) != ' ') left--;        // 将字符串两个范围内的字符依次放入返回字符，完成倒排        res.append(s, left + 1, right + 1);        // 讲放入的字符后面加空格        res.append(' ');    }    // 空格是普加，所以需要删除字符串最后一位空格    res.deleteCharAt(res.length()-1);    return new String(res);}
~~~

### [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

> 使用库函数可以直接切片+拼接

~~~java
    public static String reverseLeftWords(String s, int n) {        // lrloseumgh -> umghlrlose n为前n位数，下标位n-1        StringBuilder sb = new StringBuilder(s);        int len = s.length() -1;        // 先翻转要移到后面的字符 lrloseumgh -> esolrlumgh        reverseString(sb, 0, n-1);        // 再反转移到前面的字符 esolrlumgh -> esolrlhgmu        reverseString(sb, n, len);        // 整体翻转 esolrlhgmu -> umghlrlose 完成        reverseString(sb,0,len);        return sb.toString();    }    public static void reverseString(StringBuilder sb, int start, int end) {        // 正常换位        while (start < end) {            char ch = sb.charAt(start);            sb.setCharAt(start++, sb.charAt(end));            sb.setCharAt(end--,ch);        }    }
~~~

### [28. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)

#### kmp

主要用于字符串的匹配上，

- 文本串：长字符串，待匹配的母串，如aabaabaaf
- 模式串：短字符串，未处理的子串，如aabaaf
- 前缀：不包含最后一个字符的所有以第一个字符开头的连续**子串**
  - 如：a,aa,aab,aaba,aabaa
  - 前缀表：010120
  - next，右移：-101012
  - **最长相等的前缀** : aa
- **后缀**：不包含第一个字符的所有以第一个字符开头的连续**子串**
  - 如：abaaf,baaf,aaf,af,f
  - 后缀表：00120

> KMP 经典题目。

~~~java
public static int strStr(String haystack, String needle) {        if (needle.length() == 0) return 0;        int[] next = new int[needle.length()];        getNext(next, needle);        // next选择开头为-1，这里也为-1        int j = -1;        // 母字符串逐位遍历        for (int i = 0; i < haystack.length(); i++) {            // 如果正常遍历出错，记录出错的指针            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {                // 利用next数组，将出错的指针回退至与之前相等的下标                j = next[j];//-1，-1，0，0，1，2，-1            }            //此处正常遍历，同i一起逐位比较            if (haystack.charAt(i) == needle.charAt(j + 1)) j++;// 如果相同，指针+1                        // 如果指针长度同待查字串相等，说明匹配完成            if (j == needle.length() - 1) {                // i此时是从0开始的下标，+1变为长度                return (i + 1 - needle.length());            }        }        return -1;    }    public static void getNext(int[] next, String s) {        /*        i指向后缀起始位置，j指向前缀起始位置             i   因为前缀不包括第一个字符，所以从s[1]开始             v            abaabac            ^            j    因为后缀是不包括最后一个字符，所以可以从s[0]开始，         */        int j = -1;// j从-1开始,防止极端情况s全部相等，也指从待排字符串头开始        next[0] = j;// 因为前缀指针指不到s[0]，所以由j赋值        // 前缀指针需要走完整个字符串        for (int i = 1; i < s.length(); i++) {            // 防止j退到-1后s[-1]报错，j小于0循环终止            // 如果前缀的开头指针指向的值，同后缀指针j的下一位指向的值不相等            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) j = next[j];// j后退至j<0，或指向的相同的值为止            // 如果前缀的开头指针指向的值，同后缀指针j的下一位指向的值相等            if (s.charAt(i) == s.charAt(j + 1)) j++;// j再往后挪一位            // 与前缀相等的下标j赋值给next数组的i位            next[i] = j;        }    }
~~~

### [459. 重复的子字符串](https://leetcode-cn.com/problems/repeated-substring-pattern/)

> len % (len - nextLen) == 0 && next[len - 1] >= 0 核心代码

```java
public static boolean repeatedSubstringPattern(String s) {    // 经典kmp算法    int len = s.length();    int[] next = new int[len];    int j = -1;    next[0] = j;    for (int i = 1; i < len; i++) {        while (j>=0 && s.charAt(i) != s.charAt(j+1)){            j = next[j];        }        if (s.charAt(i) == s.charAt(j + 1)) {            j++;        }        next[i] = j;    }    // 计算next数组中最后一位值，因为初始从-1开始，所以这里加1    int nextLen = next[len - 1] + 1;    //            nextLen的值为重复长度的值，总长度减去重复长度，得到值为-1的长度    // 如果循环重复，那么总长度必定能整除值为-1的长度    //                                   这里屏蔽末尾等于-1的值，这种情况比不可能重复    return len % (len - nextLen) == 0 && next[len - 1] >= 0;}
```

## 栈与队列

### [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)

~~~java
class MyQueue {    Stack<Integer> stack1;    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) {        // 直接调用push方法        stack1.push(x);    }        /** Removes the element from in front of queue and returns that element. */    public int pop() {          // 放到出栈的栈后，移除并返回          dumpStack1();        return stack2.pop();    }        /** Get the front element. */    public int peek() {        // 直接返回一下        dumpStack1();        return stack2.peek();    }        /** Returns whether the queue is empty. */    public boolean empty() {        return stack1.isEmpty() && stack2.isEmpty();    }    // 如果stack2为空，那么将stack1中的元素全部放到stack2中    private void dumpStack1(){        if (stack2.isEmpty()){            while (!stack1.isEmpty()){                stack2.push(stack1.pop());            }        }    }}
~~~

### [225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)

~~~java
class MyStack {    Queue<Integer> queue;    /** Initialize your data structure here. */    public MyStack() {        // 创建一个队列        queue = new LinkedList<Integer>();    }        /** Push element x onto stack. */    public void push(int x) {        // 获取列表中的元素数        int n = queue.size();        // 将x从后插入        queue.offer(x);        // 将x前的元素从头依次删除，并插入x后        for (int i = 0; i < n; i++) {            queue.offer(queue.poll());        }    }        /** Removes the element on top of the stack and returns that element. */    public int pop() {        // poll获取并删除列表的头        return queue.poll();    }        /** Get the top element. */    public int top() {        // peek获取列表的头，但不删除        return queue.peek();    }        /** Returns whether the stack is empty. */    public boolean empty() {        // 判断是否为空        return queue.isEmpty();    }}
~~~

### [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)

~~~java
public static boolean isValid(String s) {    char ch;    Stack<Character> stack = new Stack<Character>();    for (int i = 0; i < s.length(); i++) {        ch = s.charAt(i);        // 插入反向的        if (ch == '(') {            stack.push(')');        } else if (ch == '[') {            stack.push(']');        } else if (ch == '{') {            stack.push('}');            // 如果栈内元素不是上面的三个，而且已经为空了，说明多余了左边符号，返回false            // 这里拿出第一个元素检查一下，不是一对直接返回false            // 用或来判断，一假都假        } else if (stack.empty() || stack.peek() != ch) {            return false;        } else {            // 走到这里说明是一对，弹出一个            stack.pop();        }    }    return stack.isEmpty();}
~~~

### [1047. 删除字符串中的所有相邻重复项](https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/)

~~~java
// 方法一，StringBuilder处理public String removeDuplicates(String s) {    StringBuilder sb = new StringBuilder(s);    for(int i = 0;i<sb.length()-1;i++){        if(sb.charAt(i)==sb.charAt(i+1)){            sb.delete(i,i+2);            i = i-2==-2?i-1:i-2;        }    }    return sb.toString();}// 方法二，使用栈public static String removeDuplicates(String s) {    Stack<Character> stack = new Stack<Character>();    for (int i = 0; i < s.length(); i++) {        if (!stack.empty() && stack.peek() == s.charAt(i)) {            stack.pop();        }else {            stack.push(s.charAt(i));        }    }    // 这里将栈转为字符串    StringBuilder res = new StringBuilder();    while (!stack.empty()){        res.insert(0, stack.pop());    }    return res.toString();}
~~~

### [150. 逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)

~~~java
public static int evalRPN(String[] tokens) {        Stack<Integer> stack = new Stack<>();        int res = 0, one, two;        for (String str : tokens) {            switch (str) {                case "+":                    one = stack.pop();                    two = stack.pop();                    res = two + one;                    stack.push(res);                    break;                case "-":                    one = stack.pop();                    two = stack.pop();                    res = two - one;                    stack.push(res);                    break;                case "*":                    one = stack.pop();                    two = stack.pop();                    res = two * one;                    stack.push(res);                    break;                case "/":                    one = stack.pop();                    two = stack.pop();                    res = two / one;                    stack.push(res);                    break;                default:                    res = Integer.parseInt(str);                    stack.push(res);                    break;            }        }        return res;    }
~~~

### [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)

~~~java
class Solution {    public static int[] maxSlidingWindow(int[] nums, int k) {        if (nums.length == 1 || k == 1) {            return nums;        }        // 返回值数组的长度为输入数组的长度-k+1        int len = nums.length - k + 1;        int[] res = new int[len];        int num = 0;        myQueue myQueue = new myQueue();        for (int i = 0; i < k; i++) {            // 先将输入数组的前k元素插入队列，因为此时不用平移            myQueue.add(nums[i]);        }        // 这里直接存放首位，因为首位必定为最大值        res[num++] = myQueue.peek();        // 从k开始遍历，因为已经放过k了        for (int i = k; i < nums.length; i++) {            // 这里减去k是因为限制最大值存活的时间            // 最大为k次，最后原数组剩余的k个元素不用管            myQueue.poll(nums[i - k]);            // 这里循环添加数组中的值            myQueue.add(nums[i]);            // 每一次移动就有一个最大值，必定是第一个            res[num++] = myQueue.peek();        }        // 返回        return res;    }}class myQueue{    Deque<Integer> deque = new LinkedList<Integer>();    void poll(int val) {        // 如果元素同栈顶相等，删除这个元素        if (!deque.isEmpty() && val == deque.peek()) {            deque.poll();        }    }    void add(int val){        // 添加的时候，如果比队列尾部元素大，那么删除队列尾部所有比之小的元素        // 保证队列是递减的        while (!deque.isEmpty() && val > deque.getLast()) {            deque.removeLast();        }        // 删完了，或者不比顶部大，添加        deque.add(val);    }    // 这里正常    int peek() {        return deque.peek();    }}
~~~

### [347. 前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/)

~~~java
public static int[] topKFrequent(int[] nums, int k) {        int[] res = new int[k];        HashMap<Integer, Integer> hashMap = new HashMap<>();        for (int num : nums) {            // 将数组放入map，如果重复value+1            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);        }        // 通过map.entrySet转为Set类型，方便迭代        Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();        // PriorityQueue 通过排序二叉树实现的小顶堆队列，默认队顶为最小值        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());        //迭代参数        for (Map.Entry<Integer, Integer> entry : entries) {            // 放入小顶堆队列中            queue.offer(entry);            // 如果队列长度超过目标值，删除队首，此时队首为最小值            if (queue.size() > k) {                queue.poll();            }        }        for (int i = k - 1; i >= 0; i--) {            // 将队列值，遍历插入返回数组中            res[i] = queue.poll().getKey();        }        return res;    }
~~~



## 树

### 力扣创建的树

```java
public class TreeNode {     int val;     TreeNode left;     TreeNode right;     TreeNode() {}     TreeNode(int val) { this.val = val; }     TreeNode(int val, TreeNode left, TreeNode right) {         this.val = val;         this.left = left;         this.right = right;     } }
```

### [144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)

> 递归

~~~java
    public List<Integer> preorderTraversal(TreeNode root) {        List<Integer> res = new LinkedList<>();        getValue(root, res);        return res;    }    public static void getValue(TreeNode root, List<Integer> res) {        if (root == null) {            return;        }        res.add(root.val);// 先放入，再迭代左，再右        getValue(root.left, res);        getValue(root.right, res);    }
~~~

> 迭代

~~~java
public List<Integer> preorderTraversal(TreeNode root) {    List<Integer> res = new ArrayList<>();    if(root == null) return res;    Stack<TreeNode> stack = new Stack<>();    // 先将根节点放入    stack.push(root);    while (!stack.isEmpty()){        // 弹出节点的val放入返回数组        // 因为先放右后放左,所以一定先弹左，后弹右，        // 弹完后转到父节点的右兄弟节点继续弹        TreeNode node = stack.pop();        res.add(node.val);        if (node.right != null) {            stack.push(node.right);        }        if (node.left != null) {            stack.push(node.left);        }    }    return res;}
~~~

### [145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)

> 递归

~~~java
    public static void getValue(TreeNode root, List<Integer> res) {        if (root == null) {            return;        }        getValue(root.left, res);// 先迭代左，再右，再放入        getValue(root.right, res);        res.add(root.val);    }
~~~

> 迭代

~~~java
/* 后序：LRD ， 前序：DLR 所以按前序的方法将DRL插入队列，再翻转数组，即可*/public List<Integer> postorderTraversal(TreeNode root) {    List<Integer> res = new ArrayList<>();    if(root == null) return res;    Stack<TreeNode> stack = new Stack<>();    stack.push(root);    while (!stack.empty()){        TreeNode node = stack.pop();        res.add(node.val);        if (node.left != null) {            stack.push(node.left);        }        if (node.right != null) {            stack.push(node.right);        }    }    Collections.reverse(res);// 调用Collections工具类翻转ArrayList数组    return res;}
~~~

### [94. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)

> 递归

~~~java
    public static void getValue(TreeNode root, List<Integer> res) {        if (root == null) {            return;        }        getValue(root.left, res);// 先迭代左，再放入，再右        res.add(root.val);        getValue(root.right, res);    }
~~~

> 迭代

~~~java
public static List<Integer> inorderTraversal(TreeNode root) {    List<Integer> res = new ArrayList<>();    Stack<TreeNode> stack = new Stack<>();    // 复制树方便处理    TreeNode cur = root;    // 如果栈空了或者树空了，停止    while (cur != null || !stack.isEmpty()){        // 这里是遍历左树，如果左树为空了，走else        if(cur != null){            // 将树压入，指针指向树的左子节点            stack.push(cur);            cur = cur.left;        }else {            // 如果左树空了，开始弹出指针            cur = stack.pop();            // 这里弹出的val为最左            res.add(cur.val);            // 开始逐级将指针指向右树            cur = cur.right;        }    }    return res;}
~~~

### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

> BFS，广度优先搜索

~~~java
public static List<List<Integer>> levelOrder(TreeNode root) {    List<List<Integer>> res = new ArrayList<>();    if (root == null) return res;    //使用队列辅助    Queue<TreeNode> queue = new LinkedList<>();    // 先将主节点放入队列中    queue.add(root);    // 如果队列不空执行，空了说明广度搜索结束    while (!queue.isEmpty()) {        // 创建二维数组里面的数组        List<Integer> temp = new ArrayList<>();        // 存储此时队列的长度        int len = queue.size();        // 如果长度不为0        while (len > 0) {            // 弹出队列顶部元素            TreeNode node = queue.poll();            // 将元素的value放入里数组            temp.add(node.val);            // 采用先左后右，往队列里放节点            if (node.left != null) queue.add(node.left);            if (node.right != null) queue.add(node.right);            // 走到这里说明队列元素弹出了，长度减1            len--;        }        //返回数组中放入数组        res.add(temp);    }    return res;}
~~~

### [226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)

终止条件：节点为空  返回值 ：反转后的树

当前节点：镜像反转

~~~java
public static TreeNode invertTree(TreeNode root) {    if(root == null) return null;    invertTree(root.left);    invertTree(root.right);    TreeNode pre = root.left;    root.left = root.right;    root.right = pre;    return root;}// 很简单，不多说了
~~~

### [111. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree)

> 终止条件：节点为空   返回值：深度
>
> 当前节点： 遍历节点，深度加1

~~~java
public static int minDepth(TreeNode root) {    // 节点为空 返回深度0    if(root == null) return 0;    // 左子树递归，用于计算深度    int left = minDepth(root.left);    // 右子树递归，用于计算深度    int right = minDepth(root.right);    // 如果左右子树都非0，取最小深度+1    if(left != 0 && right != 0 ) return Math.min(left,right) + 1;    // 如果左子树为0，取右子树深度+1    if(left == 0) return right + 1;    // 如果右子树为0，取左子树深度+1，    // 原 if(right == 0) return left + 1，如下为简写    return left + 1;}
~~~

### [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree)

> 终止条件：树深度为0；返回值：最大深度
>
> 本级递归做什么：在root左右子树选最大的，再加1

```java
    public static 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;    }
```

### [101. 对称二叉树](https://leetcode-cn.com/problems/symmetric-tree)

> 本级做什么：判断当前节点镜像位是否相等
>
> 终止条件：节点为null 返回值：是否对称

~~~java
public static boolean isSymmetric(TreeNode root) {    // 要求镜像对比，将树分叉，方便比较    return isSymmetricSon(root.left, root.right);}public static boolean isSymmetricSon(TreeNode leftRoot, TreeNode rightRoot) {    // 当前节点及镜像节点都为空时，程序true，表示堆成    if(leftRoot == null && rightRoot == null){        return true;    }    // 有一个为空，返回false，不对称    if(leftRoot == null || rightRoot == null){        return false;    }    // val不一样，不对称    if(leftRoot.val != rightRoot.val){        return false;    }    // 做递归,进行下一层判断，左树左和右树右    boolean leftR = isSymmetricSon(leftRoot.left,rightRoot.right);    // 做递归,进行下一层判断，左树右和右树左    boolean rightL = isSymmetricSon(leftRoot.right,rightRoot.left);    // 有一个为false 就为false    return leftR && rightL;}
~~~

### [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree)

> 终止条件：子节点为空，返回值：节点的深度和是否平衡
>
> 本级做什么：判断是否平衡或深度是否大于1

```java
// 自定义一个返回类static class IsDept{    // 布尔用来返回最终结果    boolean isT;    // 用来记录深度    int dept;    // 构造方法    public IsDept(int dept,boolean isT){        this.isT = isT;        this.dept = dept;    }}// 此方法为题目所给public static boolean isBalanced(TreeNode root) {    //  返回自定义方法的布尔值    return IsRootDept(root).isT;}public static IsDept IsRootDept(TreeNode root){    // 如果节点为空返回默认值    if(root==null){        return new IsDept(0, true);    }    // 递归节点的左右子节点，返回规定格式    IsDept left = IsRootDept(root.left);    IsDept right = IsRootDept(root.right);    // 计算左右子节点个最大深度是否大于1，是则返回false    if(Math.abs(left.dept-right.dept) > 1){        return new IsDept(0, false);    }    // 看是左数或右数是否为平衡二叉树，有一个不是返回false    // false来源为上一步计算深度是否大于1，如果都不大与1，返回默认值    if(!left.isT || !right.isT){        return new IsDept(0, false);    }    // 如果当前节点为平衡二叉树，深度根据左或右子节点最大深度+1    return new IsDept(Math.max(left.dept,right.dept) + 1,true);}
```

### [257. 二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/)

~~~java
//递归static List<String>  list = new ArrayList<>();public static List<String> binaryTreePaths(TreeNode root) {    if (root == null) return list;    process(root,"");    return list;}public static void process(TreeNode root, String cur) {    if(root == null) return;    // 字符串拼接    cur += String.valueOf(root.val);    // 如果左右节点没了，再往里放    if (root.left == null && root.right == null) {        list.add(cur);    }    // 递归加箭头    process(root.left,cur + "->");    process(root.right,cur + "->");}//栈与队列public static List<String> binaryTreePaths(TreeNode root) {    List<String> list = new ArrayList<>();    if (root == null) return list;    Stack<Object> stack = new Stack<>();    // 将节点和路径放入栈    stack.push(root);    stack.push(root.val + "");    while (!stack.isEmpty()){        // 将节点和路径依次弹出        String value = (String) stack.pop();        TreeNode node = (TreeNode) stack.pop();        // 如果找到叶子节点，放入返回数组        if(node.right == null && node.left == null) {            list.add(value);        }        // 左右依次放入，放的时候插入-》符合        if (node.left != null) {            stack.push(node.left);            stack.push(value + "->" + node.left.val);        }        if (node.right != null) {            stack.push(node.right);            stack.push(value + "->" + node.right.val);        }    }    return list;}
~~~

### [404. 左叶子之和](https://leetcode-cn.com/problems/sum-of-left-leaves/)

~~~java
// 迭代public static int sumOfLeftLeaves(TreeNode root) {    Stack<TreeNode> stack = new Stack<>();    stack.push(root);    int res = 0;    while (!stack.isEmpty()){        TreeNode node = stack.pop();        // 判断该节点是否为左叶子节点，需要判断他的左左节点和左右节点是否存在        if(node.left != null && node.left.left == null && node.left.right == null) {            res += node.left.val;        }        if (node.right != null) {            stack.push(node.right);        }        if (node.left != null) {            stack.push(node.left);        }    }    return res;}
~~~

### [98. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)

~~~java
// 预先设定一个空节点，用来存valuepublic TreeNode max;public boolean isValidBST(TreeNode root) {    // 采用中序遍历，如果节点为空说明走完了，返回true    if (root == null) {        return true;    }    // 如果左节点不是空，返回false    boolean left = isValidBST(root.left);    if(!left) return false;    // 如果临时节点的值 大于 当前节点的值，不满足搜索树条件，返回false    if (max != null && max.val >= root.val) return false;    // 将当前左节点赋给临时节点    max = root;    // 迭代右节点，可直接返回值    return isValidBST(root.right);}
~~~

### [114. 二叉树展开为链表](https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)

~~~java
public void flatten(TreeNode root) {    // 思路：前序遍历，左节点的值全部移到右节点，先存一下左节点的值，将左节点插入他的中节点和中节点的右节点之间    // 如果为空结束    while (root != null) {        // 节点的左节点为空跳过        if (root.left != null) {            // 将当前节点的左节点存起来            TreeNode prep = root.left;            // 创建临时树            TreeNode cur = prep;            // 指针指向右节点的末尾            while (cur.right != null) {                cur = cur.right;            }            // 将根节点的右节点赋值给末尾节点的右节点            // 即中心节点左节点插入他的中节点和中节点的右节点之间            cur.right = root.right;            // 将左制空            root.left = null;            // 此时中心节点的右节点为当前树的左节点            root.right = prep;        }        // 继续从右节点遍历        root = root.right;    }}
~~~

### [二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

~~~java

~~~





### TODO

## 回溯算法

## 动态规划

### 动规五部曲

1. 确定dp数组以及下标的含义如dp[i]，dp\[i][j]，dp[[i]]等
2. 确定递推公式
3. dp数组如何初始化（递推公式无法确定的值，一般0，1）
4. 确定遍历顺序，（从前往后还是从后往前还是怎么地）
5. 举例推导dp数组，（手动举例）

### [509. 斐波那契数](https://leetcode-cn.com/problems/fibonacci-number/)

1. 一维数组dp[i]
2. dp[i] = dp[i-1]+dp[i-2]
3. dp[0]=0 dp[1]=1
4. 从0到n
5. dp[0] = 0 ,dp[1]=1,dp[2]=1,dp[3]=2,dp[4]=3,dp[5]=5,dp[6]=8,dp[7]=13

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

### [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)

1. dp[1]
2. dp[n] = dp[n-1]+dp[1]
3. dp[1]=1 dp[2]=1
4. 从1到n
5. dp[3]=3 dp[4]=5

~~~java
public int climbStairs(int n) {    if(n <= 1)  return n;    int[] dp = new int[n + 1];    // 不考虑为0的情况    dp[1] = 1;    dp[2] = 2;    for (int i = 3; i <= n; i++) {        // 逐个步进        dp[i] = dp[i - 1] + dp[i-2];    }    return dp[n];}
~~~

### [746. 使用最小花费爬楼梯](https://leetcode-cn.com/problems/min-cost-climbing-stairs/)

1. 一维数组 dp[i]
2. dp[i] = min(dp[i-1],dp[i-2])+cost[i]
3. 初始化dp[0] = cost[0]，dp[1]=cost[1]
4. 从0到cost.lenght
5. 因为最多走两步，所以取倒数两位的最小值

~~~java
public int minCostClimbingStairs(int[] cost) {    if (cost.length <= 0) return 0;    if (cost.length == 1) return cost[0];    int[] dp = new int[cost.length];    dp[0] = cost[0];    dp[1] = cost[1];    for (int i = 2; i <= cost.length-1; i++) {        // 计算最小花费，需要取花费最小的方法走        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];    }    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
~~~

### [63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)

1. 二维数组dp\[i][j]
2. dp\[i][j] = dp\[i-1][j]+dp\[i][j-1] 切ij不等于1才行
3. dp\[0][0]=0
4. 从左到右一层一层
5. 不好算

~~~java
public int uniquePathsWithObstacles(int[][] obstacleGrid) {    int x = obstacleGrid.length;    int y = obstacleGrid[0].length;    int[][] dp = new int[x][y];    // 溜着墙走，因为需要计算i-1的值，如果等于1这条路不通，这步是初始化    for (int i = 0; i < y; i++) {        if (obstacleGrid[0][i] == 1) break;        dp[0][i] = 1;    }    for (int i = 0; i < x; i++) {        if (obstacleGrid[i][0] == 1) break;        dp[i][0] = 1;    }    // 按从左往右从上往下依次走，遇到石头跳过这次方法    for (int i = 1; i < x; i++) {        for (int j = 1; j < y; j++) {            if (obstacleGrid[i][j] == 1) continue;            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];        }    }    // 计算到目标点的条数    return dp[x - 1][y - 1];}
~~~

### [343. 整数拆分](https://leetcode-cn.com/problems/integer-break/)

1. 一维数组dp[i]，这里dp[i]是最大乘积
2. dp[i] = max(dp[i] , max( dp[i-j] x dp[j] ) )
3. 因为最小值为2，所有dp[2]=1
4. 从前到后
5. dp[10]=36

~~~java
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    if (n <= 2) return 1;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i - 1; j++) {
            // 这里i是目标值n，(n-x)乘x，就是目标值拆分后的成绩，如果这个n-x后还能再减，
            // 即n-x-y，那一定曾经出现过，直接获取dp[n-x]的值
            int a = Math.max(j * (i - j), j * dp[i - j]);
            // 遍历当前i的所有可能的和的乘积，将最大的放入dp
            dp[i] = Math.max(dp[i], a);
        }
    }
    return dp[n];
}
~~~

### [96. 不同的二叉搜索树](https://leetcode-cn.com/problems/unique-binary-search-trees/)

1. 一维数组：dp[n]：头节点为n时的bfs数量
2. 

