力扣总结笔记

1.二分查找：704

补充：

数组下标都是从0开始的。
数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

查找目标值target，返回该值的数组元素的下标。

二分法适用于已经排好序的数组，定义两个变量，一个left,一个right,则mid = left + ((right - left) >> 1)

1.针对左闭右闭算法 [left,right]

如果 target==arr[mid],中间值正好等于要查找的值，则返回下标，return mid;

如果 target<arr[mid],要找的值小于中间的值，则再往数组的小端找，right=mid-1;

如果 target>arr[mid],要找的值大于中间的值，则再往数组的大端找，left=mid+1;

注意:

1
2
3

while(right >= left)

int right = nums.length - 1;

2.针对左闭右开算法 [left, right）

如果 target==arr[mid],中间值正好等于要查找的值，则返回下标，return mid;

如果 target<arr[mid],要找的值小于中间的值，则再往数组的小端找，right=mid;

如果 target>arr[mid],要找的值大于中间的值，则再往数组的大端找，left=mid+1;

注意：

1
2
3

while(right > left)

int right = nums.length;

2.移除元素：27

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组(目标元素就是要移除的元素)
慢指针：指向更新之后新数组下标的位置

public int removeElement(int[] nums, int val) {
      int slowIndex = 0;
      for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
          if(nums[fastIndex] != val){
              nums[slowIndex++] = nums[fastIndex];
          }
      }
      return slowIndex;
  }

3.有序数组的平方：977

双指针法:

数组是有序的，但是负数平方之后可能成为最大数,那么数组平方的最大值就在数组的两端，不是最左边就是最右边。

此时可以考虑双指针法了，left指向起始位置，right指向终止位置。

定义一个新数组result，和原来A数组一样的大小，让index指向result数组终止位置。

如果A[left] * A[left] < A[right] * A[right] 那么result[index--] = A[right] * A[right]; right--;

如果A[left] * A[left] >= A[right] * A[right] 那么result[k--] = A[left] * A[left]; left++;

public int[] sortedSquares(int[] nums) {
     int right = nums.length - 1;
     int left = 0;
     int[] result = new int[nums.length];
     int index = nums.length - 1;
     while (right <= left){
         if(nums[right] * nums[right] > nums[left] * nums[left]){
             result[index--] = nums[right] * nums[right];
             right--;
         }
         else {
             result[index--] = nums[left] * nums[left];
             left++;
         }
     }
     return result;
 }

4.长度最小的子数组：209

滑动窗口：双指针法

(1)在本题中实现滑动窗口，主要确定如下三点：

窗口内是什么？就是满足其和 ≥ target 的长度最小的连续子数组。
如何移动窗口的起始位置？如果当前窗口的值大于target了，窗口就要向前移动了
如何移动窗口的结束位置？窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

(2) 补充的知识点：

Integer.MAX_VALUE表示int数据类型的最大取值数：2 147 483 647
Integer.MIN_VALUE表示int数据类型的最小取值数：-2 147 483 648

(3)代码实现：

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

5.螺旋矩阵II: 59

模拟顺时针画矩阵的过程:坚持循环不变量原则。

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

实现代码：

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;

        while (loop++ < n / 2) { // 判断边界后，loop从1开始
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }

            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }

            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }

            // 模拟左侧从下到上
            for (; i >= loop; i--) {//在一轮循环中，loop为1
                res[i][j] = count++;
            }
            start++;
        }

        if (n % 2 == 1) {//当为奇数时候，将最后一个数填充进去。
            res[start][start] = count;
        }

        return res;
    }
}

补充的知识点：

1. i，j常识

1	int x[i][j] i表示行 j表示列

2. for循环的执行顺序

for(int i =0; i<5;i++){
// 循环体
}
执行顺序解抛
执行的顺序如下：
第一步： i=0 初始化值
第二步： i<5 进行条件判断，如果为真，则继续执行
第三步：执行循环体的内容
第四步： i++ 变量i自增
第五步：回到第二步，条件判断为真，则执行循环体内容，再到i++一直循环，
直到第二步的判断条件为假，则退出该循环

6.搜索插入位置：35

思路：

目标值在数组所有元素之前
目标值等于数组中某一个元素
目标值插入数组中的位置
目标值在数组所有元素之后

二分法：

1.看到题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

代码实现：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        
        // 定义target在左闭右闭的区间，[low, high]
        int low = 0;
        int high = n - 1;

        while (low <= high) { // 当low==high，区间[low, high]依然有效
            int mid = low + (high - low) / 2; // 防止溢出
            if (nums[mid] > target) {
                high = mid - 1; // target 在左区间，所以[low, mid - 1]
            } else if (nums[mid] < target) {
                low = mid + 1; // target 在右区间，所以[mid + 1, high]
            } else {
                // 1. 目标值等于数组中某一个元素  return mid;
                return mid;
            }
        }
        // 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 return right + 1;
        return high + 1;
    }
}

7.在排序数组中查找元素的第一个和最后一个位置：34

寻找target在数组里的左右边界，有如下三种情况：

情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为1或者数组{3, 4, 5},target为9，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,5,7},target为4，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

寻找右边界

int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

寻找左边界

int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }

处理三种情况

class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}

8.有效的完全数平方

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==0||num==1){
            return true;
        }
        long i = 0;
        long j = num/2;
        while(i<=j){
            long mid = i+(j-i)/2;
            long sq = mid*mid;
            if(sq>num){
                j = mid -1;
            }
            else if(sq == num){
                return true;
            }
            else{
                i = mid + 1;
            }
        }
        return false;
    }
}

9. x 的平方根

k*k<=X, l=k

k*k>X,r=k-1

class Solution {
public int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = l + (r - l) / 2 + 1;//+1避免死循环
            if ((long)mid*mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

10.移动零

快慢指针解决： 快指针遇到0之后，快指针++，慢指针不动。遇到非零数字，将快指针的下表赋值给慢指针，快指针和慢指针都++

最后将数组中空余的位置的都设置为0；

图解：

f f f f f f———快指针

0 3 4 6 0 7

3 4 6 7 0 0

s s s s———–慢指针

代码实现如下：

class Solution {
    public void moveZeroes(int[] nums) {
        int fast = 0, slow=0;
        while (fast<nums.length){
            if(nums[fast]==0){
                fast++;
            }else {
                nums[slow++] = nums[fast++];
            }
        }
        for (int i = slow;i<nums.length;i++){
            nums[i] = 0;
        }
    }
}

11.删除有序数组的重复项

右指针指向的值等于左指针指向的值，左指针不动，右指针右移一步；

如果右指针指向的值不等于左指针指向的值，左右指针往前右移一步，然后右指针指向的值赋给左值针。

class Solution {
  public int removeDuplicates(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int left = 0;
        for(int right = 1;right < nums.length; right++){
            if(nums[right]!=nums[left]){
                nums[++left]=nums[right];
            }
        }
        return left+1;
    }
}

12.水果成篮

移动窗口解决：定义i,j

用map数组储存

key:数组中的数

value:数组的下标

代码实现：

class Solution {
    public int totalFruit(int[] tree) {
        int max = 1;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();//定义map数组
        int j=0;

        for(int i=0;i<tree.length;i++){
            map.put(tree[i], i);
            if(map.size() >2){
               int minIndex = tree.length - 1;
               for(int fruit : map.values()){//遍历map中的value
                   if(fruit < minIndex){//当fruit小于minIndex时
                       minIndex = fruit;//将fruit赋值给minIndex
                   }
               }

               map.remove(tree[minIndex]);//移除下标为minIndex的map
               j = minIndex+1;
            }

            max = Math.max(max, i-j+1);
        }
        return max;
    }
}

13.螺旋矩阵

第 1 个：从左向右

1
2
3

for (int j = i; j < n-i; j++) {
    list.add(matrix[i][j]);
}

第 2 个：从上往下

1
2
3

for (int j = i+1; j < m-i; j++) {
    list.add(matrix[j][(n-1)-i]);
}

第 3 个：从右往左，如果这一层只有1行，那么第一个循环已经将该行打印了，这里就不需要打印了，即（m-1-i ）!= i

1
2
3

for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--) {
    list.add(matrix[(m-1)-i][j]);
}

第4个：从下往上，如果这一层只有1列，那么第2个循环已经将该列打印了，这里不需要打印，即(n-1-i) != i

for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {
    list.add(matrix[j][i]);
}

代码实现：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0)
    		return list;
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0; 

        //统计矩阵从外向内的层数，如果矩阵非空，那么它的层数至少为1层
        int count = (Math.min(m, n)+1)/2;
        //从外部向内部遍历，逐层打印数据
        while(i < count) {
        	for (int j = i; j < n-i; j++) {
				list.add(matrix[i][j]);
			}
        	for (int j = i+1; j < m-i; j++) {
				list.add(matrix[j][(n-1)-i]);
			}
        	
        	for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--) {
				list.add(matrix[(m-1)-i][j]);
			}
        	for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {
				list.add(matrix[j][i]);
			}
        	i++;
        }    
        return list;
    }
}

14.移除链表元素

我们要删除某个节点必须要知道这个节点的上一个节点，可以设置一个虚拟头结点位置为cur，指针cur指向虚拟头节点，如果要删除链表中某个节点，就执行:cur.next=cur.next.next,最后返回返回deumy.next.

代码实现:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dumny = new ListNode(-1);
        dumny.next = head;
        ListNode cur = dumny;
        while (cur.next!=null){
            if(cur.next.val==val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dumny.next;
    }
}

15.设计链表

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点

代码实现：

// 自定义结构体
class ListNode {
    int val;
    ListNode next;// 后驱节点
    ListNode() {}
    ListNode(int val){this.val = val;}
}
class MyLinkedList {
    int size;
    ListNode dummy;
    public MyLinkedList() {// 初始化链表
        size = 0;
        dummy = new ListNode(-1);
    }
    
    /*
        获取链表中第 index 个节点的值。如果索引无效，则返回-1
    */
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = dummy;
        for(int i = 0; i <= index; i ++){// 因为我们加了虚拟头节点
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    /*
        在链表中的第 index 个节点之前添加值为 val  的节点。
        思路：找到要插入位置的前驱
     */
    public void addAtIndex(int index, int val) {
        if(index > size) {// 大于链表长度直接返回
            return ;
        }
        if(index < 0){// 小于0头插
            index = 0;
        }

        // 链表长度加1
        size ++;
        // 找到前驱
        ListNode pre = dummy;
        for(int i = 0; i < index; i ++){
            pre = pre.next;
        }
        // 创建新节点
        ListNode AddNewNode = new ListNode(val);
        AddNewNode.next = pre.next;// 放前面
        pre.next = AddNewNode;
    }

    /*
        如果索引 index 有效，则删除链表中的第 index 个节点
    */
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return ;
        }
        size --;
        ListNode pre = dummy;
        for(int i = 0; i < index; i ++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}

16.反转链表

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，因为开始反转的时候cur->next就改变值了。

接下来，就是循环走如下代码逻辑了，继续向后移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

指向谁就等于谁

代码实现：

//双指针
class Solution {
       public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);//将prev置为null，cur置为head
    }
    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        return reverse(cur, temp);// prev = cur; cur = temp;
    }
}

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

1.如下图所示:

先将cur虚拟头节点指向节点2，其次节点2指向节点1，最后节点1指向节点3，交换链表之前将节点1和节点3用临时节点记录，之后完成步骤一二三，第一轮交换完成后，cur往后移动二位，准备下一轮交换，最后返回cur.next即头节点。

代码实现：

//虚拟头节点
class Solution {
 public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);//设置一个虚拟头节点
        dummy.next = head;//将虚拟头节点指向head，这样方便后续操作。
        ListNode cur = dummy;//用cur临时指针来代替虚拟头节点
     
        while(cur.next!=null&&cur.next.next!=null){//分别排除偶数和奇数
            ListNode temp = cur.next;//记录临时节点
            ListNode temp1 = cur.next.next.next;//记录临时节点
            
            cur.next = cur.next.next;//步骤一
            cur.next.next = temp;//步骤二
            temp.next = temp1;//步骤三
            
            cur = cur.next.next;//cur移动两位，准备下一轮交换
        }
        return dummy.next;//返回头节点
    }
}

// 递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }
}

18.删除链表的倒数第N个节点

思路：

1.循环遍历，只要快慢指针相差 n 个结点即可

2.因为删除某个节点，需要知道这个节点的上一个节点，fastIndex要执行n+1步的位置来判断，所以fastIndex.next指向null，循环结束，这时候slow在删除节点的上一个节点，执行删除操作。

代码实现：

class Solution {
   public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummmyNode = new ListNode(0);//创建虚拟头节点
        dummmyNode.next = head;//让虚拟头节点的next指向head
        ListNode fastIndex = dummmyNode;//定义快指针
        ListNode slowIndex = dummmyNode;//定义慢指针
        for(int i = 0;i < n;i++){//循环遍历，只要快慢指针相差 n 个结点即可
            fastIndex = fastIndex.next;
        }
        while (fastIndex.next!=null){//因为删除某个节点，需要知道这个节点的上一个节点，slow才能指向删除节点的上一个节点
            fastIndex = fastIndex.next;//快指针后移
            slowIndex = slowIndex.next;//慢指针后移
        }
        slowIndex.next = slowIndex.next.next;//删除第n个节点
        return dummmyNode.next;//返回头节点
    }
}

19.链表相交

1.假定链表相交:

两个指针分别走a+b+c步一定会相遇，即遍历完本链表后，继续遍历另一个链表，直到最后两者相遇，相遇节点为题目的两个链表相交的起始节点。如下图所示

2.链表不相交

a,b 分别代表两个链表的长度，则两个指针分别走 a+b+c步后都变成 null，这里c等于0，因为两个链表没有相交的节点。

注意：交点不是数值相等，而是指针相等。

代码实现：

public class Solution {
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;//定义指针curA指向headA
        ListNode curB = headB;//定义指针curB指向headB
        while(curA != curB){//当指针不等时
            if(curA==null) curA = headB;//判断curA是否指向空，指向空则指向另一个链表的头节点。
            else curA = curA.next;//不指向空则继续后移。
            
            if(curB==null) curB = headA;//判断curB是否指向空，指向空则指向另一个链表的头节点。
            else curB = curB.next;//不指向空则继续后移。
        }
        return curA;
    }
}

20.环形链表II

快慢指针：

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

1	(x + y) * 2 = x + y + n (y + z) 经过化简之后 x = (n - 1) (y + z) + z

因为快指针一定会在慢指针没走一圈，就会追赶到。当两个指针相遇时，在相遇节点处，定义一个指针index1，在头结点处定一个指针index2，index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，index1 指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

21.有效的字母异位词

思路：定义一个数组叫做record用来上记录字符串里字符出现的次数，需要把字符映射到数组也就是哈希表的索引下标上，遍历s数组的字母个数执行++，遍历t数组的字母个数–，最后遍历26个字母，要是最后record数组中的元素全为0，说明两个串的字母完全一样，反之有问题。

补充一个知识点：

1
2
3

charAt()是JAVA中常用的字符串方法，其作用返回一个字符串的指定位置的字符，索引是从[0,length-1].比如：

str.charAt(0)检索str中的第一个字符,str.charAt(str.length()-1)检索最后一个字符

代码实现:

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

22.两个数组的交集

思路:

先将nums1数组里边的元素放进HashSet中，之后HashSet判断包不包含nums2中的元素，如果包含就放到resSet中，最终转化为数组输出

代码实现：

class Solution{
    public int[] intersection(int[] nums1, int[] nums2){
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set = new HashSet<>(); //用来存放遍历的第一个数组中的元素（无重复元素）
        Set<Integer> resSet = new HashSet<>(); //用来存放结果数组
        
        for(int i : nums1){
            set.add(i);
        }
        for(int i : nums2){
            if(set.contains(i)){
                resSet.add(i);
            }
        }
        return resSet.stream().mapToInt(x -> x).toArray();//将HashSet转化为数组输出
    }
}

23.快乐数

通过哈希判重：

这道题目使用哈希法，来判断这个res是否重复出现，如果重复了就是return false，否则一直找到sum为1为止，则返回true

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

        private int getnextNumber(int n){
            int res = 0;
            while (n>0){
                int i = n%10;
                res+=i*i;
                n = n/10;
            }
            return res;
        }
}

24.两数之和

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

对于每一个x，我们判断哈希表中是否存在target-x，若存在，则返回哈希表里的value和x的value
反之将x的插入哈希表即可

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

25.四数相加

本题解题步骤：

首先定义一个 hashMap，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
最后返回统计值 count 就可以了

class Solution {
   public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int temp;
        int res = 0;
        for (int i : nums1) {
            for (int j : nums2) {
                temp = i + j;
                if(hashMap.containsKey(temp)){
                    hashMap.put(temp, hashMap.get(temp)+1);
                }else {
                    hashMap.put(temp,1);
                }
                
            }
        }
        for (int i : nums3) {
            for (int j : nums4) {
                temp = i+j;
                if(hashMap.containsKey(0-temp)){
                    res+= hashMap.get(0-temp);
                }
            }
        }
        return res;
    }
}

26.赎金信

思路：

用哈希映射数组来解决这道问题，首先先定义个数组，遍历magazine字符串，哈希映射来求出每个字符出现的次数以及位置，遍历ranomNote的字符串，在record里对应的字符个数做–操作

实现代码：哈希解法

class Solution {
  public boolean canConstruct(String ransomNote, String magazine) {
    int [] record = new int[26];
    for (char c : magazine.toCharArray()) {
        record[ c -'a'] += 1;
    }
    for (char c : ransomNote.toCharArray()) {
        record[c - 'a'] -= 1;
    }
    for (int i : record) {
        if(i < 0){
            return false;
        }
    }
    return true;
}
}

27.三数之和

思路：本题采用双指针方法来解决，因为涉及到去重，所以哈希法比较麻烦。先让i指向第一个元素，left指向i+1个元素，right指向最后一个元素，通过判断三者数的和sum

sum>0,则右指针向左移

sum<0,则左指针向右移

sum=0，则添加集合中

去重操作：

判断i是否重复，就判断nums[i]==nums[i-1];,i+1的则是在数组中判重，就会丢失目标的集合。

判断left，right是否重复，right: nums[right]==nums[right-1] left: nums[left]==nums[left+1];

代码实现：双指针

 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                return result;
            }
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (right>left){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (right>left && nums[right]==nums[right-1]) {
                        right--;
                    }
                    while (right>left && nums[left]==nums[left+1]) {
                        left++;
                    }
                    right--;
                    left++;

                }
            }
        }
        return result;
    }

}

28.四数之和

思路：在三数之和的基础上，本题由一个确定的0，变成了一个目标值target

但是有一些细节需要注意，例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

用二层for循环，之后用long类型计算sum，以免数值越界。

代码实现：双指针

class Solution {
  public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {

            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
}
}

29.字符串反转

class Solution {
    public void reverseString(char[] s) {
        int i = 0;
        int j = s.length - 1;
        while(j>i){
            char temp = s[j];
            s[j] = s[i];
            s[i] = temp;
            i++;
            j--;
        }
    }
}

30.替换空格

思路：开一个buffer 的StringBuffer来记录答案，遍历原串，遇到空格则往后拼加%20，反之将字符往后拼加

public StringBuffer append(String str)
可以把任意类型添加到字符串缓冲区里面,并返回字符串缓冲区本身

实现代码：

class Solution {
    public String replaceSpace(String s) {

        StringBuffer res = new StringBuffer();
        for(Character c : s.toCharArray()){
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

31. 反转字符串II

思路：由于每次都是2k的区间对前k个翻转，因此我们枚举的时候，以2k为枚举区间长度，注意下边的具体要求即可

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

实现代码：

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i+=2*k){
            if(i+k<=ch.length){
                reverse(ch,i,i+k-1);
                continue;
            }
            reverse(ch,i,ch.length-1);
        }
        return new String(ch);
    }
    public void reverse(char[] ch,int i,int j){
        for(;i<j;i++,j--){
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
        }
    }
}

32.剑指II.左旋转字符串

思路：用字符串拼接

代码实现：

class Solution {
    public String reverseLeftWords(String s, int n) {
        String result ="";
        int m = s.length();
        for(int i = n;i < m;i++){
            result += (s.charAt(i));
        }
        for(int i = 0;i < n;i++){
            result += (s.charAt(i));
        } 
        return result;
    }
}

33.翻转字符串里的单词

解题思路：

移除多余空格
将整个字符串反转
将每个单词反转

例子：

源字符串为：”the sky is blue “
移除多余空格 : “the sky is blue”
字符串反转：”eulb si yks eht”
单词反转：”blue is sky the”

代码实现：

class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

34.实现 `strStr()`

思路：前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串****

代码实现：

class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

35.重复的子字符串

步骤一：因为这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同。

步骤二：因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。

步骤三：因为这是相等的前缀和后缀，t[2] 与 k[2]相同，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。

步骤四：循环往复。

所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。

正是因为最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.equals("")) return false;

        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];

        // 构造 next 数组过程，j从0开始(空格)，i从2开始
        for (int i = 2, j = 0; i <= len; i++) {
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
            // 匹配成功，j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            return true;
        }
        return false;
    }
}

双指针专题

36.移除元素

思路：快慢指针，分别设置两个指针，快指针遍历需要的数组，将需要的数组付给slow指向的数组

实现代码：

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

37.反转字符串

实现代码：

class Solution {
    public void reverseString(char[] s) {
        int j = s.length-1;
        int i = 0;
        while(j>i){
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
}

38.替换空格

实现代码：

class Solution {
    public String replaceSpace(String s) {

        StringBuffer res = new StringBuffer();
        for(Character c : s.toCharArray()){//由字符串转换成字符串数组
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();//由字符串数组转换成字符串
    }
}

栈和队列专题

栈：先进后出,是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

队列：先进先出,是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

1.用栈实现队列

java中栈的方法

判空: empty()
添加元素: push
弹出栈顶元素: pop()
获取栈顶元素: peek()

思路：队列是先进先出，而栈是先进后出，我们可以通过两个栈来模拟队列。

将所有元素放入入栈中
将入栈中的所有元素弹出，压入出栈中，此时出栈的出栈顺序即达到了模拟队列的效果（先进先出）

代码实现：

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        dumpstackIn();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty()&&stackOut.isEmpty();
    }
     private void dumpstackIn(){
         if(stackOut.isEmpty()){
             while(!stackIn.isEmpty()){
                 stackOut.push(stackIn.pop());
             }
         }
     }
}

2.用队列实现栈

java中队列的方法:

判空: isEmpty()
添加元素: offer()
弹出栈顶元素 poll()
获取栈顶元素 peek()

思路：一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时在去弹出元素就是栈的顺序。

代码实现：

class MyStack {

    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    //每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
    public void push(int x) {
        queue.offer(x);
        int size = queue.size()-1;
        //移动除了 A 的其它数
        while (size-- > 0)
            queue.offer(queue.poll());
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

3.有效的括号

思路：括号匹配有三种失败的情况：

左括号多余

({[]}()
括号未多余，但不匹配

[()[
右括号多余

({[]})))

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出动手之前分析好题目的重要性。

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

代码实现：

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 !=0){
            return false;
        }
        Stack<Character> stk = new Stack<>();
        for(int i=0;i<n;i++){
            char ch = s.charAt(i);
            if(ch=='(') stk.push(')');
            else if(ch=='[') stk.push(']');
            else if(ch=='{') stk.push('}');
            else if(stk.empty()||ch!=stk.peek()) return false;
            else stk.pop();                                                              
        } 
        return stk.empty();
    }
}

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

思路：

用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作

当栈为空或者此时的元素和栈顶元素不匹配, 则将当前元素入栈
匹配, 则弹出栈顶元素
最后通过字符串拼接返回

最后栈内剩余的元素就是答案

代码实现：

class Solution {
    public String removeDuplicates(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for(int i=0;i<s.length();i++){
            char ch =s.charAt(i);
            if(deque.isEmpty()||deque.peek()!=ch){
                deque.push(ch);
            }else{
                deque.pop();
            }
        }
        String str = "";
        while(!deque.isEmpty()){
            str = deque.pop()+str;
        }
        return str;
    }
}

5. 逆波兰表达式求值

逆波兰表达式：其实就是二叉树的后续遍历（后缀表达式）

思路：栈模拟

遇到数字加入栈
遇到操作字符弹出栈顶两个元素，进行对应操作即可

注意：在做减法以及除法时，要注意pop出来的顺序，先放进的-后放进的，先放进的/后放进的，后pop出来的-先pop出来的，后pop出来的/先pop出来的

class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (String s : tokens) {
            if("+".equals(s)) {
                deque .push(deque .pop() + deque .pop());
            } else if("-".equals(s)) {
                int temp1 = deque .pop();
                int temp2 = deque .pop();
                deque .push(temp2-temp1);
            } else if("*".equals(s)) {
                deque .push(deque .pop() * deque .pop());
            } else if("/".equals(s)){
                int temp1 = deque .pop();
                int temp2 = deque .pop();
                deque .push(temp2 / temp1);
            }else {
                deque .push(Integer.valueOf(s));
            }
        }
        return deque .pop();
    }
}

6.滑动窗口最大值

思路：设计单调队列的时候，pop，和push操作要保持如下规则：

pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

//利用双端队列手动实现单调队列
/**
 * 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
 * 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
 */
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

7. 前 K 个高频元素

关于堆：

如果面试题中要求求出一个动态数据集中的最大值或者最小值，那么一般可以考虑使用优先队列（堆）来解决问题
Java 中优先队列（堆） PriorityQueue 的默认情况下是一个最小堆，如果要使用最大堆，那么在调用构造函数时就需要传入 Comparator 的实现类自定义比较排序的规则。 PriorityQueue 实现了接口 Queue，常用函数有：

offer(e)：将元素 e 放入堆中
poll()：删除堆顶元素
peek()：返回位于堆顶的元素，但该元素并不出堆，还在堆中

思路：优先队列

我们可以通过优先队列维护这k个前 K 个高频元素（限制堆的大小为k），维护的依据是元素的出现次数，为此我们可以用一个map对元素和其出现次数进行绑定，维护一个小根堆，重写的排序规则就是根据map的entry对象中的出现次数进行排序（小根堆）。

当我们遍历map集合时，若队列未满，则将entry直接入堆，若满了，则比较当前元素的出现次数是否 >堆顶元素，是则弹出堆顶元素然后当前元素入堆即可！最终堆中的这k个元素即为前 K 个高频元素。

实现代码：

 //解法2：基于小顶堆实现
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小顶堆只需要维持k个元素有序
            if(pq.size()<k){//小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

二叉树专题

一.递归遍历

通用方法：遍历每一个节点时候，用长方形来代表每个节点，之后每个格子来代表执行语句，以此来表示递归。

二叉树定义：

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;
    }

}

递归三部曲：

1.确定递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

前序遍历：

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

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

中序遍历：

// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}

后序遍历

// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}

二.迭代实现

1.前序遍历

思路：用栈模拟前序遍历过程，由于是栈（先进后出）

根节点先栈
当栈不为空，右孩子先入栈，然后左孩子再入栈（后进先出）

栈模拟：根左右 —> 根右左

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

2.中序遍历

思路：

处理：将元素放进result数组中
访问：遍历节点

中：左根右

迭代法：

定义一个指针指向根节点，当节点不为空或者栈不为空时一直循环
当指针不为空时，当前节点入栈，一直循环遍历左儿子，如此往复直到p指针指向空——-（模拟一直左递归的过程）
当指针为空时，栈顶元素出栈，指针指向了出栈的节点,p = stk.pop()，节点值val加入result（模拟遍历中根的过程，记录答案），然后指针p移动到当前节点的右儿子（模拟遍历中右的过程），为下一次（左根右做好准备）

遍历左儿子为空时，弹出栈中元素。遍历右儿子为空时，继续弹出栈中元素。

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

3.后序遍历

思路：

看后序遍历，前序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中。

根左右 —> 由入栈顺序根右左得到
那么根右左 —> 由入栈顺序根左得到

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

4.层序遍历二叉树

思路：队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。对头先入队，当队列不为空时，（遍历此时队列中的所有元素）对头元素逐一出队（队头出），加入答案（每一层），的元素，然后将该元素的左右儿子入队（队尾入），当前层遍历完后，将这层的答案记录，进入下一层。直到最后队列为空。每次遍历层的时候，需要记录队列的大小，以便需要弹出多少元素。

代码实现:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itList = new ArrayList<Integer>();
            int len = queue.size();
            while(len>0){
                TreeNode tmpNode = queue.poll();
                itList.add(tmpNode.val);
                if(tmpNode.left!=null) queue.add(tmpNode.left);
                if(tmpNode.right!=null) queue.add(tmpNode.right);
                len--;
            }
            result.add(itList);
        }
        return result;
    }
}

5.翻转二叉树

递归三部曲：

1.确定递归函数的参数和返回值：返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数

2.确定终止条件：当前节点为空的时候，就返回

3.确定单层递归的逻辑：因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树

思路：递归实现

如果根节点不为空，那么就要交换其左右子树（即使左右子树是空节点也没关系）
递归交换左右子树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        dfs(root);
        return root;
    }
    public static void dfs(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        dfs(root.left);
        dfs(root.right);
    }
}

思路二:BFS

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }
    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

6.对称二叉树

递归：同时遍历左右子树，左右子树是否完全对称

两个根节点的值要相等
左边的左子树和右边的右子树对称
左边的右子树和右边的左子树对称

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    private boolean compare(TreeNode left,TreeNode right){
        if(left==null&&right!=null){
            return false;
        }
        else if(left!=null&&right==null){
            return false;
        }
        else if(left==null&&right==null){
            return true;
        }
        else if(left.val!=right.val){
            return false;
        }
        boolean compareOutside = compare(left.left,right.right);
        boolean compareInside = compare(left.right,right.left);
        return compareInside&&compareOutside;
    }
}

7.二叉树最大的深度

思路：dfs，前序遍历统计最大深度即可

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

8.二叉树的最小深度

思路：

左子树为空，右子树不为空，最小深度就是右子树的深度+1；

左子树不为空，右子树为空，最小深度就是左子树的深度+1；

代码实现：

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

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

1.通用递归法

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

2.迭代法

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

3.针对完全二叉树的解法

class Solution {
    /**
     * 针对完全二叉树的解法
     *
     * 满二叉树的结点数为：2^depth - 1
     */
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (leftDepth == rightDepth) {// 左子树是满二叉树
            // 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
            return (1 << leftDepth) + countNodes(root.right);
        } else {// 右子树是满二叉树
            return (1 << rightDepth) + countNodes(root.left);
        }
    }

    private int getDepth(TreeNode root) {
        int depth = 0;
        while (root != null) {
            root = root.left;
            depth++;
        }
        return depth;
    }
}

10.平衡二叉树

求高度：后序—自底向上

求深度：前序—自上向下

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

补充：

思路：

使用后序，分别求出左右子树高度差，来判断左右子树高度差的绝对值是否大于1，大于1的话就不是平衡二叉树。只有知道左右子树的高度，才能来判断是否为平衡二叉树，所以遍历顺序是左右中。选择后序遍历。

1.递归法

代码实现：

class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

2.迭代法

代码实现：

class Solution {
   /**
     * 迭代法，效率较低，计算高度时会重复遍历
     * 时间复杂度：O(n^2)
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root!= null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右结点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre) {
                // 比较左右子树的高度差，输出
                if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下，没有要遍历的结点了
            } else {
                root = inNode.right;// 右结点还没遍历，遍历右结点
            }
        }
        return true;
    }

11.二叉树的所有路径

思路：

根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径，求所有路径，就是暴力搜索每一种可能，我们可以用深度优先搜索实现（前序遍历），由于要递归枚举每一种可能，注意回溯恢复现场即可！

递归函数函数参数以及返回值
确定递归终止条件
确定单层递归逻辑

class Solution {
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root, "", res);
        return res;
    }
    public void dfs(TreeNode root, String path, List<String> list){
        if(root == null){
            return ;
        }
        //递归出口：如果是叶子节点，说明是一条路径，加入res集合
        if(root.left == null && root.right == null){
            list.add(path + root.val);
            return ;
        }
        
        // 当递归到递归出口（叶子节点）后就会回溯，自带的
        
        dfs(root.left, path + root.val + "->", list);
        dfs(root.right, path + root.val + "->", list);
    }
}

12.左叶子之和

思路：dfs（前序遍历求和即可），求和的条件是节点为左叶子节点

代码实现：

递归

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;  // 中
        return sum;
    }
}

迭代

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<> ();
        stack.add(root);
        int result = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null && node.left.left == null && node.left.right == null) {
                result += node.left.val;
            }
            if (node.right != null) stack.add(node.right);
            if (node.left != null) stack.add(node.left);
        }
        return result;
    }
}

13.找树的左下角的值

思路：按照先左后右的顺序遍历子树，最先搜索到的最深的结点即所求的结点。

代码实现：

递归法

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,1);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

迭代法

//迭代法
class Solution {

    public int findBottomLeftValue(TreeNode root) {
        Queue<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 (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}

14.路径总和I

思路：dfs从根节点遍历到叶子节点，判断这条路径是否符合要求即可。

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

15.路径总和II

思路：dfs

class solution {
    public List<List<Integer>> pathsum(TreeNode root, int targetsum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; // 非空判断

        List<Integer> path = new LinkedList<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

解法二：迭代法

// 解法2
class Solution {
    List<List<Integer>> result;
    LinkedList<Integer> path;
    public List<List<Integer>> pathSum (TreeNode root,int targetSum) {
        result = new LinkedList<>();
        path = new LinkedList<>();
        travesal(root, targetSum);
        return result;
    }
    private void travesal(TreeNode root,  int count) {
        if (root == null) return;
        path.offer(root.val);
        count -= root.val;
        if (root.left == null && root.right == null && count == 0) {
            result.add(new LinkedList<>(path));
        }
        travesal(root.left, count);
        travesal(root.right, count);
        path.removeLast(); // 回溯
    }
}

16.路径总和III

**双重DFS**：我们遍历每一个节点，从这个节点开始计算它的子树满足要求的路径。

我们访问每一个节点 node，检测以node 为起始节点（头节点）且向下延深的路径有多少种（第二次dfs判断左右子树是否右满足的情况）。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。

class Solution {
    int res = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        long longTargetSum = targetSum;
        dfs(root, longTargetSum);// 每一个根节点都要dfs判断
        // 为下一次dfs做好准备
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return res;
    }
    public void dfs(TreeNode root, long sum){
        if(root == null){
            return ;
        }
        sum -= root.val;
        if(sum == 0){
            rse ++;
            // 这里不能return !! 下面可能还要答案集
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
}

17.从中序与后序遍历序列构造二叉树

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

思路：

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间

代码实现：

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

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

题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

思路看上一题即可

代码实现：

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,  
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);
        return root;
    }
}

19.最大二叉树

力扣题目地址

思路

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。

递归三部曲

确定递归函数的参数和返回值

参数就是传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

确定终止条件

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

确定单层递归的逻辑

先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。
最大值所在的下标左区间构造左子树，这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
最大值所在的下标右区间构造右子树，判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length);
    }

    public TreeNode dfs(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = dfs(nums, leftIndex, maxIndex);
        root.right = dfs(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

20.合并二叉树

力扣题目链接

递归三部曲

1.确定递归函数的参数和返回值：

首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

2.确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

3.确定单层递归的逻辑：

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

代码实现：dfs方式

class Solution {
    // 递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

21.二叉搜索树中的搜索

力扣题目地址

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

代码实现

DFS

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null||root.val==val) return root;
        TreeNode res = null;
        if(val>root.val) res = searchBST(root.right,val);
        if(val<root.val) res = searchBST(root.left,val);
        return res;
    }
}

迭代法

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

22.验证二叉搜索树

力扣题目链接

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

二叉搜索树的中序遍历是个有序的数组，可以利用这个特性，来判断是否是二叉搜索树，中序遍历，验证遍历的元素是不是从小到大

代码实现:

class Solution {
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean left = isValidBST(root.left);
        if(root.val<=prev){
            return false;
        }
        prev = root.val;
        boolean right = isValidBST(root.right);
        return right&&left;
    }
}

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

力扣题目链接

中序遍历：中序遍历之后就是一个有序的数组

双指针法实现代码

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

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

力扣题目链接

递归三部曲：

确定递归函数参数以及返回值
确定终止条件

终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

确定单层递归的逻辑

代码实现：

`dfs`

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

迭代法

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

        return newRoot;
    }
}

力扣总结笔记

1.二分查找：704

2.移除元素：27

双指针法

3.有序数组的平方：977

双指针法:

4.长度最小的子数组：209

5.螺旋矩阵II: 59

6.搜索插入位置：35

二分法：

7.在排序数组中查找元素的第一个和最后一个位置：34

寻找右边界

寻找左边界

处理三种情况

8.有效的完全数平方

9. x 的平方根

10.移动零

11.删除有序数组的重复项

12.水果成篮

13.螺旋矩阵

14.移除链表元素

15.设计链表

16.反转链表

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

18.删除链表的倒数第N个节点

19.链表相交

20.环形链表II

21.有效的字母异位词

22.两个数组的交集

23.快乐数

24.两数之和

25.四数相加

26.赎金信

27.三数之和

28.四数之和

29.字符串反转

30.替换空格

31. 反转字符串II

32.剑指II.左旋转字符串

33.翻转字符串里的单词

34.实现 strStr()

35.重复的子字符串

双指针专题

36.移除元素

37.反转字符串

38.替换空格

栈和队列专题

1.用栈实现队列

2.用队列实现栈

3.有效的括号

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

5. 逆波兰表达式求值

6.滑动窗口最大值

7. 前 K 个高频元素

二叉树专题

一.递归遍历

通用方法：遍历每一个节点时候，用长方形来代表每个节点，之后每个格子来代表执行语句，以此来表示递归。

二叉树定义：

递归三部曲：

前序遍历：

中序遍历：

后序遍历

二.迭代实现

1.前序遍历

2.中序遍历

3.后序遍历

4.层序遍历二叉树

5.翻转二叉树

6.对称二叉树

7.二叉树最大的深度

8.二叉树的最小深度

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

10.平衡二叉树

1.递归法

2.迭代法

11.二叉树的所有路径

12.左叶子之和

13.找树的左下角的值

14.路径总和I

15.路径总和II

34.实现 `strStr()`

`dfs`