代码随想录算法刷题记录

代码随想录刷题记录

Ⅰ 数组

1.1 二分查找

704. 二分查找

public static int search(int[] nums, int target) {
      int left = 0, right = nums.length - 1;

      while (left <= right) {
          int mid = (left + right) / 2;
          if (nums[mid] == target)
              return mid;
          if (nums[mid] < target)
              left = mid + 1;
          if (nums[mid] > target)
              right = mid - 1;
      }

      return -1;
  }

35. 搜索插入位置

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

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

public static int[] searchRange(int[] nums, int target) {
    // 数组不存在或者为空
    if (nums == null || nums.length == 0) return new int[]{-1, -1};
    
    // target在数组左右边界之外
    int left = nums[0], right = nums[nums.length - 1];
    if (target > right || target < left)
        return new int[]{-1, -1};
    
    // target在数组左右边界之内
    int resLeft = searchLeft(nums, target);   //寻找左边界
    int resRight = searchRight(nums, target); //寻找右边界
    return new int[]{resLeft, resRight};
}

// 寻找左边界
public static int searchLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) { //找到target的时候，记录当前的左边界，继续寻找左边界的左边是否还有target
            res = mid;
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
}

// 寻找右边界
public static int searchRight(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (target > nums[mid]) { //找到target的时候，记录当前的右边界，继续寻找右边界的右边是否还有target
            left = mid + 1;
        } else if (target < nums[mid]) {
            right = mid - 1;
        } else {
            res = mid;
            left = mid + 1;
        }
    }
    return res;
}

69. x 的平方根

// 二分查找寻找平方根
public static int mySqrt(int x) {
    if (x == 0 || x == 1) return x;

    // 平方根不会大于二分之一的X
    int left = 1, right = x / 2, ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 此时的target = x/mid，判断 mid 是否与 x/mid 相等即可
        if (mid <= x / mid) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ans;
}

367. 有效的完全平方数

// 基本的二分查找
public static boolean isPerfectSquare(int num) {
    if (num == 1) return true;
    long left = 1, right = num / 2;

    while (left <= right) {
        long mid = left + (right - left) / 2;
        if (mid * mid == num)
            return true;
        else if (mid * mid < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

1.2 双指针

27. 移除元素

// 双指针
public static int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

26. 删除有序数组中的重复项

// 双指针
  public static int removeDuplicates(int[] nums) {
      int slow = 1, cur = nums[0]; // 慢指针记录返回的数组

      // 快指针判断当前元素是否重复
      for (int fast = 1; fast < nums.length; fast++) {
          if (nums[fast] != cur) {
              nums[slow] = nums[fast];
              slow++;
              cur = nums[fast];
          }
      }
      return slow;
  }

283. 移动零

// 双指针实现
public static void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    // 将后面的元素[slow, nums.length)填充为0
    Arrays.fill(nums, slow, nums.length, 0);
}

844. 比较含退格的字符串

我自己写的，不是很优雅，全是if-else。。。

// 使用双指针从后往前遍历 + 计数退格符的方式模拟最终字符
 public static boolean backspaceCompare(String s, String t) {

     int countS = 0, countT = 0; // 记录 s、t 中待删除的字符数量
     int pointS = s.length() - 1, pointT = t.length() - 1; // 分别指向两个字符串的尾部

     // 不断向前移动两个指针，直到比较结束
     while (true) {

         // 处理字符串 s
         while (pointS >= 0) {
             if (s.charAt(pointS) == '#') {
                 countS++; // 遇到退格符，待删除字符数量增加
                 pointS--; // 指针左移
             } else {
                 if (countS > 0) { // 遇到普通字符，但前面有退格符未处理，就跳过该字符
                     pointS--;
                     countS--; // 消耗一个退格符
                 } else break; // 没有退格符可用，说明当前字符是有效字符，停止处理 s
             }
         }

         // 处理字符串 t
         while (pointT >= 0) {
             if (t.charAt(pointT) == '#') {
                 countT++;
                 pointT--;
             } else {
                 if (countT > 0) {
                     pointT--;
                     countT--;
                 } else break;
             }
         }

         // 两个指针同时到头，说明两个字符串同时结束 → 匹配成功
         if (pointS < 0 && pointT < 0)
             break;

         // 一个结束一个没结束 → 不相等
         if ((pointS < 0 && pointT >= 0) || (pointS >= 0 && pointT < 0))
             return false;

         // 比较两个当前有效字符是否相同
         if (s.charAt(pointS) != t.charAt(pointT))
             return false;
         else {
             // 若相同，继续往前比较
             pointS--;
             pointT--;
         }
     }

     // 最终检查两个指针是否都走到 -1
     if (pointS == -1 && pointT == -1)
         return true;
     return false;
 }

977. 有序数组的平方

双指针从左从右找平方的最大值，依次录入到新建数组最后一位即可
（我还以为必须要在这个原数组中进行操作呢….没想到可以新建一个数组，，，这就简单多了）

// 双指针分别记录数组的左右端元素，谁的平方更大，谁就赋入新建数组的最后一个元素
 public static int[] sortedSquares(int[] nums) {
     int left = 0, right = nums.length - 1;
     int[] array = new int[nums.length]; //新创建一个数组用于记录结果
     int point = right; 

     // 将更大的平方的值赋值到新数组的最后一个位置
     while (point >= 0) {
         if (nums[left] * nums[left] <= nums[right] * nums[right]) {
             array[point] = nums[right] * nums[right];
             right--;
         } else {
             array[point] = nums[left] * nums[left];
             left++;
         }
         point--;
     }

     return array;
 }

1.3 滑动窗口

209. 长度最小的子数组

滑动窗口，先移动结束位置找到大于target的窗口，再移动初始位置逐步缩小窗口，从而找到最小窗口

// 滑动窗口
// 从初始位置开始滑动遍历找到总和大于target的结束位置
// 然后再逐步移动初始位置缩小窗口，找到总和大于target的最小窗口
public static int minSubArrayLen(int target, int[] nums) {
    int i = 0, sum = 0, len = Integer.MAX_VALUE;

    for (int j = 0; j < nums.length; j++) { // 移动窗口的结束位置
        sum += nums[j];
        while (sum >= target) { // 移动窗口的初始位置
            len = Math.min(len, j - i + 1); // 记录最小窗口的长度
            sum -= nums[i];
            i++;
        }
    }

    return len == Integer.MAX_VALUE ? 0 : len;
}

904. 水果成篮

滑动窗口思想：先移动窗口的结束位置，再寻找初始位置
使用哈希表HashMap存储: (水果的种类, 该种类的个数)

// 找一个最长连续子数组，满足子数组中至多有两种数字
public static int totalFruit(int[] fruits) {
    // 哈希表存储<水果的种类, 该种类的个数>
    Map<Integer, Integer> map = new HashMap<>();

    int left = 0, res = 0;

    // 滑动窗口用结束位置(窗口的右边界)做循环
    for (int right = 0; right < fruits.length; right++) {
        map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);

        // 此时种类大于2个，就要重新确定开始位置(窗口的左边界)
        while (map.size() > 2) {
            res = Math.max(res, right - left);

            map.put(fruits[left], map.get(fruits[left]) - 1);
            if (map.get(fruits[left]) == 0) {
                map.remove(fruits[left]); // 移除表中个数为0的种类，让哈希表中只有两个种类
            }
            left++;
        }
    }
    res = Math.max(res, fruits.length - left);
    return res;
}

76. 最小覆盖子串

滑动窗口：先移动右边界，当条件满足时，再缩小左边界
使用两个哈希表分别存放字符串 t 和滑动窗口的字符串 window
使用flag记录当前窗口是否已包含 t 的全部字符要求

/**
   * 滑动窗口：先移动右边界，当条件满足时，再缩小左边界
   * 使用两个哈希表分别存放字符串 t 和 滑动窗口的字符串 window
   */
  public static String minWindow(String s, String t) {
      int len = Integer.MAX_VALUE, left = 0, flag = 0, resLeft = 0;
      Map<Character, Integer> map = new HashMap<>();
      Map<Character, Integer> window = new HashMap<>();

      // 初始化 map 为 t 中字符出现次数
      for (char c : t.toCharArray()) {
          map.put(c, map.getOrDefault(c, 0) + 1);
      }

      for (int right = 0; right < s.length(); right++) {
          char c = s.charAt(right);
          if (map.containsKey(c)) {
              window.put(c, window.getOrDefault(c, 0) + 1);
              if (window.get(c).equals(map.get(c))) {
                  flag++; // 当前字符满足要求
              }
          }

          // 尝试收缩左边界
          while (flag == map.size()) {
              if (right - left + 1 < len) {
                  len = right - left + 1;
                  resLeft = left;
              }

              char d = s.charAt(left);
              if (map.containsKey(d)) {
                  if (window.get(d).equals(map.get(d))) {
                      flag--; // 当前字符不再满足
                  }
                  window.put(d, window.get(d) - 1);
              }
              left++;
          }
      }

      return len == Integer.MAX_VALUE ? "" : s.substring(resLeft, resLeft + len);
  }

1.4 螺旋矩阵（模拟）

59. 螺旋矩阵 II

模拟：用上下左右边界对数组的赋值进行限制

// 模拟：用上下左右边界对数组的赋值进行限制
public static int[][] generateMatrix(int n) {
    int[][] array = new int[n][n];
    int num = 1;
    int left = 0, right = n - 1;
    int top = 0, bottom = n - 1;

    while (left <= right && top <= bottom) {

        // → 向右
        for (int y = left; y <= right; y++) {
            array[top][y] = num++;
        }
        top++;

        // ↓ 向下
        for (int x = top; x <= bottom; x++) {
            array[x][right] = num++;
        }
        right--;

        // ← 向左
        if (top <= bottom) { // 判断
            for (int y = right; y >= left; y--) {
                array[bottom][y] = num++;
            }
            bottom--;
        }

        // ↑ 向上
        if (left <= right) { // 判断
            for (int x = bottom; x >= top; x--) {
                array[x][left] = num++;
            }
            left++;
        }
    }

    return array;
}

54. 螺旋矩阵

模拟

public static List<Integer> spiralOrder(int[][] matrix) {
      List<Integer> list = new ArrayList<>();
      int m = matrix.length, n = matrix[0].length;
      int left = 0, right = n - 1, top = 0, bottom = m - 1;
      
      while (left <= right && top <= bottom) {
          for (int j = left; j <= right; j++) { // 从左到右
              list.add(matrix[top][j]);
          }
          top++;
          
          for (int i = top; i <= bottom; i++) { // 从上到下
              list.add(matrix[i][right]);
          }
          right--;

          // 因为先前 top 改变了，所以要判断一下
          if (top <= bottom) {
              for (int j = right; j >= left; j--) { // 从右到左
                  list.add(matrix[bottom][j]);
              }
              bottom--;
          }

          // 因为先前 right 改变了，所以要判断一下
          if (left <= right) {
              for (int i = bottom; i >= top; i--) { // 从下到上
                  list.add(matrix[i][left]);
              }
              left++;
          }

      }
      return list;
  }

1.5 前缀和

58. 区间和

前缀和：用一个数组统计从0到i的元素的总和：
preSum[i] = array[0] +...+ array[i]

区间和[a,b] = preSum[b] - preSum[a-1]

public class Kama58 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] array = new int[n];
        int[] preSum = new int[n];

        // 前缀和
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
            preSum[i] = array[i];
            if (i > 0) {
                preSum[i] = preSum[i - 1] + array[i];
            }
        }

        while (sc.hasNext()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int sum;
            if (a == 0) {
                sum = preSum[b];
            } else {
                sum = preSum[b] - preSum[a - 1];
            }
            System.out.println(sum);
        }
    }
}

44. 开发商购买土地

前缀和

分别统计前n行的前缀和以及前m列的前缀和
然后分别模拟切割找出最小值

public class Kama44 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] array = new int[n][m];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                array[i][j] = sc.nextInt();

        // 统计前 n 行的前缀和
        int[] preSumRows = new int[n];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < m; j++) {
                sum += array[i][j];
            }
            if (i == 0) {
                preSumRows[i] = sum;
            } else {
                preSumRows[i] = preSumRows[i - 1] + sum;
            }
        }

        // 对行进行遍历切割，找出最小差距
        for (int i = 0; i < n - 1; i++) {
            min = Math.min(min, Math.abs(preSumRows[n - 1] - 2 * preSumRows[i]));
        }

        // 统计前 m 列的前缀和
        int[] preSumColumns = new int[m];
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                sum += array[j][i];
            }
            if (i == 0) {
                preSumColumns[i] = sum;
            } else {
                preSumColumns[i] = preSumColumns[i - 1] + sum;
            }
        }

        // 对列进行遍历切割，找出最小差距
        for (int i = 0; i < m - 1; i++) {
            min = Math.min(min, Math.abs(preSumColumns[m - 1] - 2 * preSumColumns[i]));
        }

        System.out.println(min);
    }
}

Ⅱ 链表

2.1 删除链表节点

203. 移除链表元素

使用虚拟头结点

public static ListNode removeElements(ListNode head, int val) {
      ListNode dummy = new ListNode(0); // 虚拟头结点
      dummy.next = head;
      ListNode cur = dummy;

      while (cur.next != null) {
          if (cur.next.val == val) {
              cur.next = cur.next.next;
          } else {
              cur = cur.next;
          }
      }
      return dummy.next;
  }

2.2 模拟链表的增删查操作

707. 设计链表

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

我使用的是双向链表

要有size字段表示链表节点的个数
创建虚拟头结点head和虚拟尾结点tail

public class MyLinkedList {

    // 双向链表内部类
    class ListNode {
        int val;
        ListNode next, prev;

        public ListNode() {}
        public ListNode(int val) {
            this.val = val;
        }
    }

    // 记录链表容量大小
    private int size;
    // 创建虚拟头尾节点
    private ListNode head, tail;

    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        this.head.next = tail;
        this.tail.prev = head;
    }

    // 获取链表中下标为 index 的节点的值
    public int get(int index) {
        if (index >= size || index < 0) {
            return -1;
        }
        ListNode cur = head.next;
        while (index >= 0) {
            if (index == 0) {
                return cur.val;
            }
            cur = cur.next;
            index--;
        }
        return -1;
    }

    // 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
        size++;
    }

    // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
        node.prev = tail.prev;
        size++;
    }

    // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    public void addAtIndex(int index, int val) {
        if (index > size || index < 0)
            return;

        ListNode cur = head;
        ListNode node = new ListNode(val);

        while (index >= 0) {
            if (index == 0) {
                node.next = cur.next;
                cur.next.prev = node;
                cur.next = node;
                node.prev = cur;
                break;
            }
            index--;
            cur = cur.next;
        }

        size++;
    }

    // 删除链表中下标为 index 的节点
    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }

        ListNode cur = head;
        while (index >= 0) {
            if (index == 0) {
                cur.next.next.prev = cur;
                cur.next = cur.next.next;
                break;
            }
            index--;
            cur = cur.next;
        }
        size--;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        System.out.println(myLinkedList.get(1));          // 返回 2
        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
        System.out.println(myLinkedList.get(1));             // 返回 3
    }
}

2.3 反转链表

206. 反转链表

public static ListNode reverseList(ListNode head) {
      ListNode cur = null;
      while (head != null) {
          ListNode nextNode = head.next;
          head.next = cur;
          cur = head;
          head = nextNode;
      }
      return cur;
  }

2.4 两两交换链表中的节点

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

public static ListNode swapPairs(ListNode head) {
      ListNode dummy = new ListNode(0); // 虚拟头结点
      dummy.next = head;
      ListNode cur = dummy;

      while (cur.next != null && cur.next.next != null) {
          ListNode first = cur.next; // 要交换的第一个节点
          ListNode end = cur.next.next;  // 要交换的第二个节点

          first.next = end.next;
          cur.next = end;
          end.next = first;
          cur = first;
      }
      return dummy.next;
  }

2.5 快慢指针 - 删除链表的倒数第 N 个结点

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

快慢指针：先让fast移动n+1步，然后fast和slow同时移动，当fast==null时，此时slow的下一个节点就是要删除的节点
要创建一个虚拟头结点，快慢指针指向dummy节点

public static ListNode removeNthFromEnd(ListNode head, int n) {
     // 创建虚拟头结点
     ListNode dummy = new ListNode(0);
     dummy.next = head;
     ListNode slow = dummy;
     ListNode fast = dummy;

     // fast要移动n+1步
     while (n >= 0) {
         fast = fast.next;
         n--;
     }
     while (fast != null) {
         slow = slow.next;
         fast = fast.next;
     }
     // 此时slow的下一个节点就是要删除的节点
     slow.next = slow.next.next;

     return dummy.next;
 }

2.6 链表相交

面试题 02.07. 链表相交

list1和list2分别指向headA和headB，都往后移动，当list1/list2到终点null时，反过头来跑headB/headA，他们在某个位置一定会相交

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode list1 = headA;
      ListNode list2 = headB;

      while (list1 != list2) {
          if (list1 == null)
              list1 = headB;
          else list1 = list1.next;
          if (list2 == null)
              list2 = headA;
          else list2 = list2.next;
      }

      return list1;
  }

2.7 环形链表

142. 环形链表 II

使用快慢指针在链表中遍历，fast移动两步，slow移动一步，若二者最终相遇，则说明链表中存在环
当快慢指针相遇后，让一个指针从头结点出发、另一个从相遇点出发同步前进，二者再次相遇的位置即为环的入口节点

public static ListNode detectCycle(ListNode head) {
       ListNode slow = head, fast = head;
       while (fast != null && fast.next != null) {
           fast = fast.next.next;
           slow = slow.next;
           // 找到快慢指针相遇处，判断是否有环
           if (slow == fast) {
               ListNode cur = head;
               // 有环的话，头结点和slow同时往后移动，他们相遇的节点就是环入口
               while (cur != slow) {
                   cur = cur.next;
                   slow = slow.next;
               }
               return slow;
           }
       }
       return null;
   }

Ⅲ 哈希表

3.1 字母异位词

两个字符串排序后相同就称为字母异位词

242. 有效的字母异位词

先用哈希表统计字符串 s 中每个字符的出现次数
再遍历字符串 t 逐一抵消计数
最终通过剩余未抵消的字符种类数是否为 0 判断两个字符串是否为异位词

public static boolean isAnagram(String s, String t) {
     if (s.length() != t.length())
         return false;

     Map<Character, Integer> map = new HashMap<>();
     for (int i = 0; i < s.length(); i++) {
         map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
     }

     int flag = map.size();
     for (int i = 0; i < t.length(); i++) {
         if (map.containsKey(t.charAt(i))) {
             map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
             if (map.get(t.charAt(i)) == 0) {
                 flag--;
             }
         }
     }
     return flag == 0;
 }

383. 赎金信

和上面一题一模一样的算法思想

public static boolean canConstruct(String ransomNote, String magazine) {
     Map<Character, Integer> map = new HashMap<>();
     for (int i = 0; i < ransomNote.length(); i++) {
         map.put(ransomNote.charAt(i), map.getOrDefault(ransomNote.charAt(i), 0) + 1);
     }

     int flag = map.size();
     for (int i = 0; i < magazine.length(); i++) {
         if (map.containsKey(magazine.charAt(i))) {
             map.put(magazine.charAt(i), map.get(magazine.charAt(i)) - 1);
             if (map.get(magazine.charAt(i)) == 0) {
                 flag--;
             }
         }
     }
     return flag == 0;
 }

49. 字母异位词分组

map存储：<字符串，与该字符串相同的所有字母异位词>
将每个字符串转换为字符数组并排序，把排序后的字符串作为 key
再用 HashMap 将排序结果相同的字符串分到同一个 List 中

public static List<List<String>> groupAnagrams(String[] strs) {
     List<List<String>> res = new ArrayList<>();

     // map存储：<字符串，与该字符串相同的所有字母异位词>
     Map<String, List<String>> map = new HashMap<>();

     for (String str : strs) {
         char[] chars = str.toCharArray();
         Arrays.sort(chars); // 对字符串排序，方便比较是否相同
         String sortStr = new String(chars);

         if (map.containsKey(sortStr)) {
             List<String> list = map.get(sortStr);
             list.add(str);
         } else {
             List<String> list1 = new ArrayList<>();
             list1.add(str);
             map.put(sortStr, list1);
         }
     }

     for (List<String> list : map.values()) {
         res.add(list);
     }
     return res;
 }

438. 找到字符串中所有字母异位词

方法1：固定长度滑动窗口 + Arrays.sort()

固定长度滑动窗口枚举字符串 s 中所有长度等于 p 的子串，并对每个子串和 p 分别进行字符排序后进行比较

public static List<Integer> findAnagrams(String s, String p) {
     List<Integer> list = new ArrayList<>();
     int start = p.length();
     char[] charsP = p.toCharArray();
     Arrays.sort(charsP);

     for (int i = start; i <= s.length(); i++) {
         String str = s.substring(i - p.length(), i);

         char[] chars = str.toCharArray();
         Arrays.sort(chars);

         if (Arrays.equals(chars, charsP)) {
             list.add(i - p.length());
         }
     }
     return list;
 }

方法2：HashMap + 滑动窗口

两个HashMap:
- 一个记录模式串 p 中各字符的频次
- 一个是滑动窗口：在 s 中移动窗口并记录窗口内字符频次
再用valid记录两个Map的相同字符的个数，用于判断两个Map是否相同

public static List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) return res;

    // 1. 统计 p 中每个字符的出现次数
    Map<Character, Integer> need = new HashMap<>();
    for (char c : p.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    // 2. 滑动窗口
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int valid = 0;  // 记录满足 need 的字符个数

    while (right < s.length()) {
        // 3. 扩大窗口
        char c = s.charAt(right);
        right++;

        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        // 4. 当窗口大小 == p.length()时，开始判断并收缩
        while (right - left >= p.length()) {
            if (valid == need.size()) {
                res.add(left);
            }

            char d = s.charAt(left);
            left++;

            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return res;
}

3.2 数组的交集

349. 两个数组的交集

使用Set集合去重
找出两个集合相同的元素即可

public static int[] intersection(int[] nums1, int[] nums2) {
      // 使用HashSet集合去重
      Set<Integer> set1 = new HashSet<>();
      Set<Integer> set2 = new HashSet<>();
      for (int i = 0; i < nums1.length; i++) {
          set1.add(nums1[i]);
      }
      for (int i = 0; i < nums2.length; i++) {
          set2.add(nums2[i]);
      }

      // 找出set1集合中在set2集合中没有的元素，并删除它
      Iterator<Integer> it = set1.iterator();
      while (it.hasNext()) {
          Integer num = it.next();
          if (!set2.contains(num)) {
              it.remove();
          }
      }

      int[] res = new int[set1.size()];
      int i = 0;
      for (Integer num : set1) {
          res[i] = num;
          i++;
      }
      return res;
  }

350. 两个数组的交集 II

用两个HashMap

分别记录数组中每个数字出现的次数
再找到交集的数字以及最小出现的次数

public static int[] intersect(int[] nums1, int[] nums2) {
      Map<Integer, Integer> map1 = new HashMap<>();
      Map<Integer, Integer> map2 = new HashMap<>();

      for (int i = 0; i < nums1.length; i++) {
          map1.put(nums1[i], map1.getOrDefault(nums1[i], 0) + 1);
      }
      for (int i = 0; i < nums2.length; i++) {
          map2.put(nums2[i], map2.getOrDefault(nums2[i], 0) + 1);
      }

      List<Integer> list = new ArrayList<>();
      for (Integer num : map1.keySet()) {
          if (map2.containsKey(num)) {
              int sum = Math.min(map1.get(num), map2.get(num));
              while (sum > 0) {
                  list.add(num);
                  sum--;
              }
          }
      }
      return list.stream().mapToInt(Integer::intValue).toArray();
  }

优化：用一个HashMap

先用 HashMap 统计其中一个数组中每个元素的出现次数
然后遍历另一个数组，若当前元素在Map中仍有剩余次数，则加入结果并将对应次数减一，从而得到按次数计算的交集

public static int[] intersect(int[] nums1, int[] nums2) {
      Map<Integer, Integer> map = new HashMap<>();
      // 统计 nums1 频次
      for (int num : nums1) {
          map.put(num, map.getOrDefault(num, 0) + 1);
      }

      List<Integer> list = new ArrayList<>();
      // 遍历 nums2，直接在 map 中“消耗”
      for (int num : nums2) {
          if (map.containsKey(num) && map.get(num) > 0) {
              list.add(num);
              map.put(num, map.get(num) - 1);
          }
      }

      return list.stream().mapToInt(Integer::intValue).toArray();
  }

3.3 快乐数

202. 快乐数

两种情况：

循环求和，最终为1，返回ture
求和的过程中，sum会重复出现，返回false

所以用HashSet判断sum是否已经出现

// 2,4,16,37,58,89,145,42,20,4
public static boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    while (true) {
        if (n == 1)
            return true;
        if (set.contains(n)) {
            return false;
        } else {
            set.add(n);
            n = getSum(n);
        }
    }
}

// 获取每个数的平方和
public static int getSum(int n) {
    int sum = 0;

    while (n > 9) {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }

    sum += n * n;
    return sum;
}

3.4 两数之和/四数相加

用哈希表

1. 两数之和

用一个HashMap存数组元素和下标，比较哈希表中是否存在target - nums[i]即可

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

454. 四数相加 II

先求nums1和nums2的和放入HashMap中，并记录同一个和的个数
- HashMap: <nums1+nums2的两数之和, 同一个和的个数>
再计算nums3和nums4的两数之和，并从哈希表中找到相加为0的key，从而得到总数

public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    int res = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            map.put(nums1[i] + nums2[j], map.getOrDefault(nums1[i] + nums2[j], 0) + 1);
        }
    }

    for (int i = 0; i < nums3.length; i++) {
        for (int j = 0; j < nums4.length; j++) {
            if (map.containsKey(-(nums3[i] + nums4[j]))) {
                res += map.get(-(nums3[i] + nums4[j]));
            }
        }
    }
    return res;
}

3.5 双指针

15. 三数之和

先对数组排序，然后固定一个数 nums[i]。
用左右双指针 left、right 在 i 右侧寻找另外两个数，根据三数之和判断指针移动方向（和大于0→右指针左移，和小于0→左指针右移）。
当三数之和为 0 时加入答案，并跳过所有重复值，继续移动双指针寻找下一组解

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复的 i
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1;
        int right = nums.length - 1;

        // 双指针
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 跳过重复的 left/right
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
}

18. 四数之和

和上面三数之和题目类似，多加一层循环就行了

主要注意去重操作

public static List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();  
    
    for (int i = 0; i < nums.length; i++) {
        // 剪枝处理
        if (nums[i] > target && nums[i] >= 0) {
            break;
        }
        // 对nums[i]去重
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length; j++) {
            // 第二级剪枝
            if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                break;	// 注意是break到上一级for循环，如果直接return result;会有遗漏
            }
            // 对nums[j]去重
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                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]));
                    // 对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;
}

Ⅳ 字符串

4.1 反转字符串

344. 反转字符串

public static void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        swap(s, left, right);
        left++;
        right--;
    }
}

public static void swap(char[] s, int i, int j) {
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

541. 反转字符串 II

每2k个字符为一段分块处理字符串，对于每一段：

只反转前k个字符
如果剩余不足k个字符，则把剩余全部反转

public static String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();

    for (int start = 0; start < s.length(); start += 2 * k) {
        int left = start, right = 0;
        if (s.length() - start < k)
            right = s.length() - 1;
        else right = start + k - 1;

        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    return new String(chars);
}

151. 反转字符串中的单词

先找出所有的单词，存入到strings[]字符串数组中
再从后往前遍历strings[]，用StringBuilder()依次添加单词和空格

public static String reverseWords(String s) {
    StringBuilder sb = new StringBuilder(s);
    String[] strings = new String[s.length()];
    int left = 0, right = 0, i = 0, j = 0;
    
    // 找出每个字符串存入到strings[]数组中
    while (i < s.length()) {
        if (s.charAt(i) == ' ') {
            i++;
            continue;
        }
        left = i;
        while (i < s.length() && s.charAt(i) != ' ') {
            right = i;
            i++;
        }
        String word = sb.substring(left, right + 1);
        strings[j] = word;
        j++;
    }
    
    // 从后往前拼接结果的字符串
    sb = new StringBuilder();
    for (int k = j - 1; k >= 0; k--) {
        sb.append(strings[k]);
        if (k != 0) {
            sb.append(" ");
        }
    }
    
    return sb.toString();
}

55. 右旋字符串

方法1：使用StringBuilder
方法2：三次反转
- reverse(chars,0,s.length()-1)
- reverse(chars,0,k-1)
- reverse(chars,k,s.length()-1)

import java.util.Scanner;

public class Kama55 {
    public static void main(String[] args) {
        String s;
        int k;
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        s = sc.next();
        System.out.println(reverseRight1(s, k));
    }

    // 使用StringBuilder()
    public static String reverseRight(String s, int k) {
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(s.length() - k, s.length())).append(s.substring(0, s.length() - k));
        return sb.toString();
    }

    // 三次反转
    public static String reverseRight1(String s, int k) {
        char[] chars = s.toCharArray();
        reverse(chars, 0, s.length() - 1);
        reverse(chars, 0, k - 1);
        reverse(chars, k, s.length() - 1);
        return new String(chars);

    }

    public static void reverse(char[] chars, int i, int j) {
        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
    }
}

4.2 替换字符串

54. 替换数字

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String s;
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        System.out.println(reverseNumber(s));
    }

    public static String reverseNumber(String s) {
        StringBuilder sb = new StringBuilder(s);

        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) >= '0' && sb.charAt(i) <= '9') {
                StringBuilder sb1 = new StringBuilder(sb.substring(0, i));
                StringBuilder sb2 = new StringBuilder(sb.substring(i + 1, sb.length()));
                sb = sb1.append("number").append(sb2);
                i += 5;
            }
        }
        return sb.toString();
    }
}

4.3 匹配字符串

28. 找出字符串中第一个匹配项的下标

两层循环暴力解法
KMP算法（不会）

// 两层循环暴力解法
public static int strStr(String haystack, String needle) {
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        int j = 0;
        while (j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) {
            j++;
        }
        if (j == needle.length()) return i;
    }
    return -1;
}

459. 重复的子字符串

如果一个字符串可以由其某个子串重复多次构成，那么把它自身拼接一次 (s + s) 后，中间部分一定包含原字符串

(s + s) 中去掉开头一个字符、去掉结尾一个字符之后，原来的 s 依然会出现一次。

1
2
3

public static boolean repeatedSubstringPattern(String s) {
    return (s + s).substring(1, 2 * s.length() - 1).contains(s);
}

Ⅴ 栈与队列

5.1 栈/队列的相互转换

232. 用栈实现队列

两个栈

一个栈存储队列元素
当元素要出队时，让stack1依次压入stack2，此时stack2就是队头元素

public class MyQueue {

    Deque<Integer> stack1;
    Deque<Integer> stack2;

    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
        int res = stack2.pop();
        while (!stack2.isEmpty())
            stack1.push(stack2.pop());
        return res;
    }

    public int peek() {
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
        int res = stack2.peek();
        while (!stack2.isEmpty())
            stack1.push(stack2.pop());
        return res;
    }

    public boolean empty() {
        if (stack1.isEmpty())
            return true;
        return false;
    }

    public static void main(String[] args) {
        MyQueue obj = new MyQueue();
        obj.push(1);
        obj.push(2);
        obj.push(3);
        int param_2 = obj.pop();
        int param_3 = obj.peek();
        boolean param_4 = obj.empty();
        System.out.println(param_2);
        System.out.println(param_3);
        System.out.println(param_4);
    }
}

225. 用队列实现栈

只对队列最后一个元素操作就行

public class MyStack {

    Deque<Integer> queue;

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

    public void push(int x) {
        queue.addLast(x);
    }

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

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

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

    public static void main(String[] args) {
        MyStack obj = new MyStack();
        obj.push(1);
        obj.push(2);
        obj.push(3);
        int param_2 = obj.pop();
        int param_3 = obj.top();
        boolean param_4 = obj.empty();
        System.out.println(param_2);
        System.out.println(param_3);
        System.out.println(param_4);
    }
}

5.2 栈

20. 有效的括号

用栈模拟即可

是左括号就压入栈中
是右括号就与栈顶元素比较是否匹配

public static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (c == '(' || c == '[' || c == '{')
            stack.push(c);
        else if (stack.isEmpty() || (c == ')' && stack.pop() != '(') || (c == ']' && stack.pop() != '[') || (c == '}' && stack.pop() != '{'))
            return false;
    }
    return stack.isEmpty();
}

150. 逆波兰表达式求值

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

public static int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String str : tokens) {
        // 判断是不是单字符运算符
        if (str.length() == 1 && "+-*/".contains(str)) {
            int num2 = stack.pop();
            int num1 = stack.pop();
            switch (str.charAt(0)) {
                case '+': stack.push(num1 + num2); break;
                case '-': stack.push(num1 - num2); break;
                case '*': stack.push(num1 * num2); break;
                case '/': stack.push(num1 / num2); break; 
            }
        } else {
            stack.push(Integer.parseInt(str));
        }
    }
    return stack.pop();
}

5.3 队列

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

使用队列去重

队尾元素与新来的元素进行比较，相同就去重

public static String removeDuplicates(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    
    // 使用队列去重
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!deque.isEmpty() && deque.peekLast() == c) {
            deque.pollLast();
            continue;
        }
        deque.addLast(c);
    }

    // 将队列元素转换成字符串
    StringBuilder sb = new StringBuilder();
    while (!deque.isEmpty()) {
        sb.append(deque.pollFirst());
    }
    return sb.toString();
}

5.4 单调队列

239. 滑动窗口最大值

维护一个单调队列，存储的是数组的索引而不是值

队头保证是最大值
- 删除队头过期元素
- 删除队尾比当前元素小的，然后当前元素再加入队尾

public static int[] maxSlidingWindow(int[] nums, int k) {
     Deque<Integer> deque = new ArrayDeque<>();
     int[] res = new int[nums.length - k + 1];
     int idx = 0;

     for (int i = 0; i < nums.length; i++) {

         // 删除队头最大值的过期元素
         while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
             deque.pollFirst();
         }

         // 删除队尾所有比当前元素小的
         while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
             deque.pollLast();
         }

         // 将当前元素加入队尾
         deque.offerLast(i);

         if (i >= k - 1) {
             res[idx++] = nums[deque.peekFirst()];
         }
     }
     return res;
 }

5.5 优先级队列（堆）

347. 前 K 个高频元素

使用哈希表统计频率
使用小顶堆保留大的频率的值

public static int[] topKFrequent(int[] nums, int k) {
     Map<Integer, Integer> map = new HashMap<>();
     PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));

     // 统计频率
     for (int num : nums) {
         map.put(num, map.getOrDefault(num, 0) + 1);
     }

     // 只保留大的频率
     for (Integer key : map.keySet()) {
         if (pq.size() < k) {
             pq.offer(key);
         } else if (map.get(key) > map.get(pq.peek())) {
             pq.poll();
             pq.offer(key);
         }
     }

     int[] res = new int[k];
     int index = 0;
     while (!pq.isEmpty()) {
         res[index++] = pq.poll();
     }
     return res;
 }

Ⅵ 二叉树

6.1 二叉树的递归遍历

递归遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

144. 二叉树的前序遍历

// 前序遍历
 public static List<Integer> preorderTraversal(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     preorder(root, list);
     return list;
 }

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

145. 二叉树的后序遍历

// 后序遍历
public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    postorder(root, list);
    return list;
}

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

94. 二叉树的中序遍历

// 中序遍历
public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    inorder(root, list);
    return list;
}

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

6.2 二叉树的层序遍历

102. 二叉树的层序遍历

使用队列存储每层的结点，使用size记录当前层结点的个数，循环出队层中的结点，入队下一层左右子树的结点，直到队空为止

public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            list.add(queue.poll().val);
            size--;
        }
        result.add(list);
    }

    return result;
}

107. 二叉树的层序遍历 II

正常层序遍历后，加一个反转就行

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            list.add(queue.poll().val);
            size--;
        }
        result.add(list);
    }

    // 正常层序遍历后，加一个反转就行
    Collections.reverse(result);

    return result;
}

199. 二叉树的右视图

也就是二叉树的层序遍历，只输出每一层的最后一个元素

public static List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            if (size == 1)
                result.add(queue.peek().val);
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            queue.poll();
            size--;
        }
    }
    return result;
}

637. 二叉树的层平均值

层序遍历计算每层的总和/个数

public static List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        long size = queue.size();
        long sum = 0, num = size;

        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            sum += queue.poll().val;
            size--;
        }
        result.add((double) sum / num);
    }
    return result;
}

429. N 叉树的层序遍历

思路跟层序遍历一样，只不过这次队列入队的是当前结点的所有孩子（而不只是左右孩子）

public static List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Node> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            if (queue.peek().children != null) {
                for (Node kid : queue.peek().children)
                    queue.offer(kid);
            }
            list.add(queue.poll().val);
            size--;
        }
        result.add(list);
    }

    return result;
}

515. 在每个树行中找最大值

public static List<Integer> largestValues(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        int max = Integer.MIN_VALUE;

        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            max = Math.max(max, queue.poll().val);
            size--;
        }
        result.add(max);
    }

    return result;
}

116. 填充每个节点的下一个右侧节点指针

层序遍历+为每个结点添加next指针

public static PerfectNode connect(PerfectNode root) {
     Deque<PerfectNode> queue = new ArrayDeque<>();
     if (root != null)
         queue.offer(root);

     while (!queue.isEmpty()) {
         int size = queue.size();
         while (size > 0) {
             if (queue.peek().left != null)
                 queue.offer(queue.peek().left);
             if (queue.peek().right != null)
                 queue.offer(queue.peek().right);
             if (size == 1) {
                 queue.peek().next = null;
                 queue.poll();
             } else {
                 PerfectNode temp = queue.poll();
                 temp.next = queue.peek();
             }
             size--;
         }
     }
     return root;
 }

104. 二叉树的最大深度

层序遍历：最大深度就是二叉树的层数
递归遍历

// 递归遍历
public static int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}

// 层序遍历：最大深度就是二叉树的层数
public static int maxDepth1(TreeNode root) {
    int result = 0;
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            queue.poll();
            size--;
        }
        result++;
    }
    return result;
}

111. 二叉树的最小深度

层序遍历: 遍历的时候有一个结点没有左右子节点，则返回
递归遍历

// 递归遍历
public static int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return 1;
    if (root.left == null && root.right != null)
        return minDepth(root.right) + 1;
    if (root.right == null && root.left != null)
        return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

// 层序遍历,遍历的时候有一个结点没有左右子节点，则返回
public static int minDepth1(TreeNode root) {
    int result = 0;
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            if (queue.peek().left == null && queue.peek().right == null)
                return result + 1;
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            queue.poll();
            size--;
        }
        result++;
    }
    return result;
}

6.3 翻转二叉树

226. 翻转二叉树

前序遍历交换左右子孩子

// 前序遍历交换左右子孩子
public static TreeNode invertTree(TreeNode root) {
    if (root == null)
        return root;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

6.4 对称二叉树

101. 对称二叉树

左右子树都为NULL，则为TRUE
左右子树都不为NULL && 左右子树的值相等 && 左子树的左子树与右子树的右子树对称 && 左子树的右子树与右子树的左子树对称，则为TRUE

public static boolean isSymmetric(TreeNode root) {
     if (root == null)
         return true;
     return isSym(root.left, root.right);
 }

 public static boolean isSym(TreeNode left, TreeNode right) {
     // 左右子树都为NULL，则为TRUE
     if (left == null && right == null)
         return true;
     
     // 左右子树都不为NULL && 左右子树的值相等 && 左子树的左子树与右子树的右子树对称 && 左子树的右子树与右子树的左子树对称，则为TRUE
     if (left != null && right != null && left.val == right.val && isSym(left.left, right.right) && isSym(left.right, right.left))
         return true;
     return false;
 }

100. 相同的树

两树都为NULL，则为TURE
两树都不为NULL && 两树的结点的值相等 && 两树的左子树相等 && 两树的右子树相等，则为TRUE

public static boolean isSameTree(TreeNode p, TreeNode q) {
    // 两树都为NULL，则为TURE
    if (p == null && q == null)
        return true;
    
    // 两树都不为NULL && 两树的结点的值相等 && 两树的左子树相等 && 两树的右子树相等，则为TRUE
    if (p != null && q != null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
        return true;
    return false;
}

572. 另一棵树的子树

前序遍历root的每个结点与subRoot比较，看是否相同

// 前序遍历root的每个结点与subRoot比较，看是否相同
 public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
     if (root == null) return false;
     if (isSame(root, subRoot))
         return true;
     return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
 }

 public static boolean isSame(TreeNode p, TreeNode q) {
     // 两树都为NULL，则为TURE
     if (p == null && q == null)
         return true;

     // 两树都不为NULL && 两树的结点的值相等 && 两树的左子树相等 && 两树的右子树相等，则为TRUE
     if (p != null && q != null && p.val == q.val && isSame(p.left, q.left) && isSame(p.right, q.right))
         return true;
     return false;
 }

6.5 二叉树的最大最小深度

104. 二叉树的最大深度

层序遍历：最大深度就是二叉树的层数
递归遍历

// 递归遍历
public static int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}

// 层序遍历：最大深度就是二叉树的层数
public static int maxDepth1(TreeNode root) {
    int result = 0;
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            queue.poll();
            size--;
        }
        result++;
    }
    return result;
}

559. N 叉树的最大深度

public static int maxDepth(Node root) {
    if (root == null)
        return 0;

    int depth = 0;
    for (Node kid : root.children) {
        depth = Math.max(depth, maxDepth(kid));
    }
    return depth + 1;
}

111. 二叉树的最小深度

层序遍历: 遍历的时候有一个结点没有左右子节点，则返回
递归遍历

// 递归遍历
public static int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return 1;
    if (root.left == null && root.right != null)
        return minDepth(root.right) + 1;
    if (root.right == null && root.left != null)
        return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

// 层序遍历,遍历的时候有一个结点没有左右子节点，则返回
public static int minDepth1(TreeNode root) {
    int result = 0;
    Deque<TreeNode> queue = new ArrayDeque<>();

    if (root != null)
        queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            if (queue.peek().left == null && queue.peek().right == null)
                return result + 1;
            if (queue.peek().left != null)
                queue.offer(queue.peek().left);
            if (queue.peek().right != null)
                queue.offer(queue.peek().right);
            queue.poll();
            size--;
        }
        result++;
    }
    return result;
}

6.6 完全二叉树的节点个数

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

直接遍历所有的节点，每遍历一个节点+1

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

6.7 平衡二叉树

110. 平衡二叉树

里层递归求每个节点的高度
外层递归求当前节点左右子节点高度差是否小于二，然后前序遍历

public static boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

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

6.8 递归+回溯

257. 二叉树的所有路径

回溯

public static List<String> binaryTreePaths(TreeNode root) {
      List<String> result = new ArrayList<>();
      List<Integer> list = new ArrayList<>();
      if (root == null)
          return result;
      treePaths(root, list, result);
      return result;
  }

  public static void treePaths(TreeNode root, List<Integer> list, List<String> res) {
      list.add(root.val);

      // 如果当前是叶子节点
      if (root.left == null && root.right == null) {
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < list.size() - 1; i++) {
              sb.append(list.get(i)).append("->");
          }
          sb.append(list.getLast());
          res.add(new String(sb));
      }

      // 左子树递归
      if (root.left != null) {
          treePaths(root.left, list, res);
      }

      // 右子树递归
      if (root.right != null) {
          treePaths(root.right, list, res);
      }

      // 回溯删除最后一个元素
      list.removeLast();
  }

6.9 其他题目

404. 左叶子之和

public static int sumOfLeftLeaves(TreeNode root) {
    if (root == null)
        return 0;
    return sumOfLeaves(root, 0);
}

public static int sumOfLeaves(TreeNode root, int sum) {
    if (root == null)
        return 0;
    if (root.left != null && root.left.left == null && root.left.right == null)
        sum += root.left.val;
    sum += sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    return sum;
}

513. 找树左下角的值

BFS
层序遍历：记录最后一层最左边的元素

public static int findBottomLeftValue(TreeNode root) {
     Deque<TreeNode> queue = new ArrayDeque<>();
     queue.add(root);
     int res = 0;
     while (!queue.isEmpty()) {
         int size = queue.size();
         int count = size;
         while (size > 0) {
             if (size == count)
                 res = queue.peek().val;
             if (queue.peek().left != null)
                 queue.add(queue.peek().left);
             if (queue.peek().right != null)
                 queue.add(queue.peek().right);
             queue.poll();
             size--;
         }
     }
     return res;
 }

112. 路径总和

用一个sum记录到达叶子节点时的和

public static boolean hasPathSum(TreeNode root, int targetSum) {
      return hasSum(root, targetSum, 0);
  }

  public static boolean hasSum(TreeNode root, int targetSum, int sum) {
      if (root == null)
          return false;
      
      sum += root.val;
      // 到达叶子节点
      if (root.left == null && root.right == null && targetSum == sum) {
          return true;
      }
      return hasSum(root.left, targetSum, sum) || hasSum(root.right, targetSum, sum);
  }

113. 路径总和 II

回溯

public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
     List<List<Integer>> res = new ArrayList<>();
     findPath(root, targetSum, res, new ArrayList<>());
     return res;
 }

 public static void findPath(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> list) {
     if (root == null)
         return;

     list.add(root.val);
     int sum = 0;
     for (int num : list)
         sum += num;
     if (root.left == null && root.right == null && sum == targetSum) {
         res.add(new ArrayList<>(list));
     }

     findPath(root.left, targetSum, res, list);
     findPath(root.right, targetSum, res, list);
     list.removeLast(); // 记得回溯
 }

6.10 根据指定条件构造二叉树

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

中序定区间长，后序找根建树


static int postIndex;
static Map<Integer, Integer> inorderIndexMap = new HashMap<>();

public static TreeNode buildTree(int[] inorder, int[] postorder) {
    postIndex = postorder.length - 1;

    for (int i = 0; i < inorder.length; i++) {
        inorderIndexMap.put(inorder[i], i);
    }

    return build(inorder, postorder, 0, inorder.length - 1);
}

// 中序定区间长，后序找根建树
private static TreeNode build(int[] inorder, int[] postorder, int inLeft, int inRight) {
    if (inLeft > inRight) return null;

    int rootVal = postorder[postIndex--];
    TreeNode root = new TreeNode(rootVal);

    int index = inorderIndexMap.get(rootVal);

    // 先构右子树，再构左子树
    root.right = build(inorder, postorder, index + 1, inRight);
    root.left = build(inorder, postorder, inLeft, index - 1);

    return root;
}

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

前序找根建树，中序定左右子树区间

static Map<Integer, Integer> map;
static int prev;

public static TreeNode buildTree(int[] preorder, int[] inorder) {
    map = new HashMap<>();
    prev = 0;
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }

    return build(preorder, inorder, 0, inorder.length - 1);
}

public static TreeNode build(int[] preorder, int[] inorder, int left, int right) {
    if (left > right)
        return null;

    TreeNode root = new TreeNode(preorder[prev]);
    int index = map.get(preorder[prev]);
    prev++;
    
    root.left = build(preorder, inorder, left, index - 1);
    root.right = build(preorder, inorder, index + 1, right);

    return root;
}

654. 最大二叉树

先找出最大值构造根节点
递归构造左子树
递归构造右子树

public static TreeNode constructMaximumBinaryTree(int[] nums) {
    return construct(nums, 0, nums.length - 1);
}

public static TreeNode construct(int[] nums, int left, int right) {
    if (left > right)
        return null;
    
    int max = Integer.MIN_VALUE;
    int maxIndex = 0;
    for (int i = left; i <= right; i++) {
        if (nums[i] > max) {
            max = nums[i];
            maxIndex = i;
        }
    }

    TreeNode root = new TreeNode(max);
    root.left = construct(nums, left, maxIndex - 1);
    root.right = construct(nums, maxIndex + 1, right);
    return root;
}

617. 合并二叉树

public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) return root2;
    if (root2 == null) return root1;

    TreeNode root = new TreeNode(root1.val + root2.val);
    root.left = mergeTrees(root1.left, root2.left);
    root.right = mergeTrees(root1.right, root2.right);

    return root;
}

6.11 二叉搜索树

二叉搜索树的中序遍历输出即为升序顺序

700. 二叉搜索树中的搜索

public static TreeNode searchBST(TreeNode root, int val) {
    if (root == null)
        return null;
    if (root.val == val)
        return root;
    if (root.val > val)
        return searchBST(root.left, val);

    return searchBST(root.right, val);
}

98. 验证二叉搜索树

每个节点都有一个合法取值区间 (min, max)

public static boolean isValidBST(TreeNode root) {
       return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
   }

   public static boolean isValid(TreeNode root, long min, long max) {
       if (root == null)
           return true;
       if (root.val <= min || root.val >= max)
           return false;

       return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
   }

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

二叉搜索树的中序遍历输出即为升序顺序
使用 prev 作为前一个值的指针，实现计算最小差值

static int min;
static Integer prev;
public static int getMinimumDifference(TreeNode root) {
    min = Integer.MAX_VALUE;
    prev = null;
    getMin(root);
    return min;
}

public static void getMin(TreeNode root) {
    if (root == null)
        return;

    getMin(root.left);
    if (prev != null)
        min = Math.min(min, root.val - prev);
    prev = root.val;
    getMin(root.right);
}

501. 二叉搜索树中的众数

中序遍历二叉搜索树等于遍历有序数组

static int maxNum;
static List<Integer> list;
static Integer prev;
static int sum;

public static int[] findMode(TreeNode root) {
    maxNum = Integer.MIN_VALUE;
    list = new ArrayList<>();
    prev = null;
    sum = 0;
    inorder(root);
    return list.stream().mapToInt(Integer::intValue).toArray();
}

public static void inorder(TreeNode root) {
    if (root == null)
        return;

    inorder(root.left);
    if (prev != null && prev.equals(root.val)) {
        sum++;
    } else {
        sum = 1;
    }

    if (sum > maxNum) {
        list = new ArrayList<>();
        list.add(root.val);
        maxNum = sum;
    } else if (sum == maxNum) {
        list.add(root.val);
        maxNum = sum;
    }
    prev = root.val;

    inorder(root.right);
}

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

按照二叉搜索树的特性，左右递归搜索即可

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

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

public static TreeNode sortedArrayToBST(int[] nums) {
    return ToBST(nums, 0, nums.length - 1);
}

public static TreeNode ToBST(int[] nums, int left, int right) {
    if (left > right)
        return null;
    int mid = (left + right) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    
    root.left = ToBST(nums, left, mid - 1);
    root.right = ToBST(nums, mid + 1, right);
    return root;
}

538. 把二叉搜索树转换为累加树

反着的中序遍历-右中左

static int sum;
public static TreeNode convertBST(TreeNode root) {
    sum = 0;
    BST(root);
    return root;
}

public static void BST(TreeNode root) {
    if (root == null)
        return;
    BST(root.right);
    sum += root.val;
    root.val = sum;
    BST(root.left);
}

6.12 最近公共祖先

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

后序遍历从下往上找：

如果左右子树各自找到了一个目标节点（p、q），那当前节点就是它们“汇合的地方”，也就是最近公共祖先。

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     if (root == null || root == p || root == q)
         return root;

     // 后序遍历
     TreeNode left = lowestCommonAncestor(root.left, p, q);
     TreeNode right = lowestCommonAncestor(root.right, p, q);
     if (left != null && right != null)
         return root;
     if (left != null && right == null)
         return left;
     return right;
 }

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

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {     //如果根节点为空或者等于 p，或者等于q，则直接返回根节点
        return root;
    }

    if (p.val > root.val && q.val > root.val)
        return lowestCommonAncestor(root.right, p, q);
    else if (p.val < root.val && q.val < root.val)
        return lowestCommonAncestor(root.left, p, q);
    else return root;
}

Ⅶ 回溯

7.1 组合

77. 组合

static List<List<Integer>> res;
static List<Integer> list;

public static List<List<Integer>> combine(int n, int k) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    backtracking(n, k, 1);
    return res;
}

public static void backtracking(int n, int k, int start) {
    // 终止条件
    if (list.size() == k) {
        res.add(new ArrayList<>(list));
        return;
    }

    // 遍历 + 回溯
    for (int i = start; i <= n; i++) {
        list.add(i);
        backtracking(n, k, i + 1);
        list.removeLast();
    }
}

216. 组合总和 III

static List<List<Integer>> res;
 static List<Integer> list;

 public static List<List<Integer>> combinationSum3(int k, int n) {
     res = new ArrayList<>();
     list = new ArrayList<>();
     backtracking(k, n, 1);
     return res;
 }

 public static void backtracking(int k, int n, int start) {
     // 终止条件
     if (k == list.size()) {
         int sum = 0;
         for (int num : list)
             sum += num;
         if (sum == n) {
             res.add(new ArrayList<>(list));
             return;
         }
     }

     // 遍历
     for (int i = start; i <= 9; i++) {
         list.add(i);
         backtracking(k, n, i + 1); // 递归
         list.removeLast(); //回溯
     }
 }

17. 电话号码的字母组合

回溯：

终止条件
for：这一层有哪些元素需要遍历
递归：递归到下一层

static List<String> res;
static List<Character> list;
static String[] digitsStr = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public static List<String> letterCombinations(String digits) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    backtracking(digits, 0);
    return res;
}

public static void backtracking(String digits, int start) {
    // 终止条件
    if (digits.length() == list.size()) {
        StringBuilder sb = new StringBuilder();
        for (Character c : list) {
            sb.append(c);
        }
        res.add(new String(sb));
        return;
    }

    String string = digitsStr[digits.charAt(start) - '2'];

    // abc是第一层，def是第二层
    for (int i = 0; i < string.length(); i++) { // abc依次for遍历
        list.add(string.charAt(i));
        backtracking(digits, start + 1); // 递归到下一层def
        list.removeLast(); // 回溯
    }
}

39. 组合总和

static List<List<Integer>> res;
static List<Integer> list;

public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    backtracking(candidates, target, 0, 0);
    return res;
}

public static void backtracking(int[] candidates, int target, int start, int sum) {
    if (sum == target) {
        res.add(new ArrayList<>(list));
        return;
    }
    if (sum > target)
        return;

    for (int i = start; i < candidates.length; i++) {
        list.add(candidates[i]);
        sum += candidates[i];
        backtracking(candidates, target, i, sum);
        sum -= list.getLast();
        list.removeLast();
    }
}

40. 组合总和 II

static List<List<Integer>> res;
 static List<Integer> list;

 public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
     res = new ArrayList<>();
     list = new ArrayList<>();
     Arrays.sort(candidates); // 先排序
     backtracking(candidates, target, 0, 0);

     return res;
 }

 public static void backtracking(int[] candidates, int target, int start, int sum) {
     if (sum == target) {
         res.add(new ArrayList<>(list));
         return;
     }
     if (sum > target)
         return;

     for (int i = start; i < candidates.length; i++) {
         // 要对同一层的元素先进行去重
         if (i > start && candidates[i] == candidates[i - 1])
             continue;
         
         list.add(candidates[i]);
         sum += candidates[i];
         backtracking(candidates, target, i + 1, sum);
         sum -= list.getLast();
         list.removeLast();
     }
 }

7.2 切割问题

131. 分割回文串

static List<List<String>> res;
static List<String> list;

public static List<List<String>> partition(String s) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    backtracking(s, 0);
    return res;
}

public static void backtracking(String s, int start) {
    if (start == s.length()) {
        res.add(new ArrayList<>(list));
        return;
    }

    for (int i = start; i < s.length(); i++) {
        String string = s.substring(start, i + 1);
        if (isHuiwen(string)) { // 是回文串才添加
            list.add(string);
            backtracking(s, i + 1);
            list.removeLast();
        }
    }
}

public static boolean isHuiwen(String s) {
    for (int i = 0; i < s.length() / 2; i++) {
        if (s.charAt(i) != s.charAt(s.length() - i - 1))
            return false;
    }
    return true;
}

93. 复原 IP 地址

static List<String> res;
 static List<String> list;

 public static List<String> restoreIpAddresses(String s) {
     res = new ArrayList<>();
     list = new ArrayList<>();
     backtracking(s, 0);
     return res;
 }

 public static void backtracking(String s, int start) {
     if (list.size() == 4 && start == s.length()) { // 四个IP，并且遍历到最后一个字符了
         StringBuilder sb = new StringBuilder();
         for (String string : list)
             sb.append(string).append(".");
         sb.deleteCharAt(sb.length() - 1);
         res.add(new String(sb));
         return;
     }

     for (int i = start; i < s.length(); i++) {
         String string = s.substring(start, i + 1);
         if (isIP(string)) {
             list.add(string);
             backtracking(s, i + 1);
             list.removeLast();
         }
     }
 }

 public static boolean isIP(String s) {
     // 长度超过 3，一定非法
     if (s.length() > 3) return false;

     // 前导 0 处理
     if (s.length() > 1 && s.charAt(0) == '0') return false;
     int num = Integer.parseInt(s);
     return num >= 0 && num <= 255;
 }

7.3 子集

78. 子集

子集的“每一个中间状态”本身就是一个合法解

static List<List<Integer>> res;
static List<Integer> list;

public static List<List<Integer>> subsets(int[] nums) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    backtracking(nums, 0);
    res.add(new ArrayList<>());
    return res;
}

public static void backtracking(int[] nums, int start) {
    if (!list.isEmpty()) {
        res.add(new ArrayList<>(list)); // if里面去掉return;
    }

    for (int i = start; i < nums.length; i++) {
        list.add(nums[i]);
        backtracking(nums, i + 1);
        list.removeLast();
    }
}

90. 子集 II

先排序再去重

static List<List<Integer>> res;
static List<Integer> list;

public static List<List<Integer>> subsetsWithDup(int[] nums) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    Arrays.sort(nums); // 先排序
    backtracking(nums, 0);
    res.add(new ArrayList<>());
    return res;
}

public static void backtracking(int[] nums, int start) {
    if (!list.isEmpty()) {
        res.add(new ArrayList<>(list));
    }

    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) // 在每一层中去重
            continue;
        list.add(nums[i]);
        backtracking(nums, i + 1);
        list.removeLast();
    }
}

491. 非递减子序列

因为数组不是有序的，所以要用set集合进行去重

static List<List<Integer>> res;
   static List<Integer> list;

   public static List<List<Integer>> findSubsequences(int[] nums) {
       res = new ArrayList<>();
       list = new ArrayList<>();
       backtracking(nums, 0);
       return res;
   }

   public static void backtracking(int[] nums, int start) {
       if (list.size() >= 2) {
           res.add(new ArrayList<>(list));
       }
       
       Set<Integer> set = new HashSet<>(); // 使用set集合进行去重
       for (int i = start; i < nums.length; i++) {
           if (!list.isEmpty() && nums[i] < list.getLast() || set.contains(nums[i]))
               continue;
           set.add(nums[i]);
           list.add(nums[i]);
           
           backtracking(nums, i + 1);
           if (!list.isEmpty())
               list.removeLast();
       }
   }

7.4 排列

46. 全排列

每一层都从头开始遍历
用一个used[]数组跳过已经被选过的元素

static List<List<Integer>> res;
static List<Integer> list;
static boolean[] used;

public static List<List<Integer>> permute(int[] nums) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    used = new boolean[nums.length];
    backtracking(nums);
    return res;
}

public static void backtracking(int[] nums) {
    if (list.size() == nums.length) {
        res.add(new ArrayList<>(list));
        return;
    }

    for (int i = 0; i < nums.length; i++) { // 每一层都从0到nums.length-1遍历
        if (used[i]) {
            continue;
        }
        list.add(nums[i]);
        used[i] = true;
        backtracking(nums);
        list.removeLast();
        used[i] = false;
    }
}

47. 全排列 II

去重：排序+去重

如果当前数字和前一个数字相同，且前一个相同数字在当前路径中还没被使用，说明这是同一层的重复选择

static List<List<Integer>> res;
  static List<Integer> list;
  static boolean[] used;

  public static List<List<Integer>> permuteUnique(int[] nums) {
      res = new ArrayList<>();
      list = new ArrayList<>();
      used = new boolean[nums.length];
      Arrays.sort(nums); // 排序
      backtracking(nums);
      return res;
  }

  public static void backtracking(int[] nums) {
      if (list.size() == nums.length) {
          res.add(new ArrayList<>(list));
          return;
      }

      for (int i = 0; i < nums.length; i++) {
          if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { // 去重
              continue;
          }
          if (used[i])
              continue;
          list.add(nums[i]);
          used[i] = true;
          backtracking(nums);
          list.removeLast();
          used[i] = false;
      }
  }

7.5 N皇后

51. N 皇后

n皇后解题思路

static List<List<String>> res;

public static List<List<String>> solveNQueens(int n) {
    res = new ArrayList<>();
    char[][] chess = new char[n][n];
    for (char[] chars1 : chess)
        Arrays.fill(chars1, '.');
    backtracking(chess, 0, n);
    return res;
}

public static void backtracking(char[][] chess, int row, int n) {
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (char[] chars : chess) {
            list.add(new String(chars));
        }
        res.add(new ArrayList<>(list));
        return;
    }

    for (int i = 0; i < n; i++) {
        if (isValid(chess, row, i, n)) {
            chess[row][i] = 'Q';
            backtracking(chess, row + 1, n);
            chess[row][i] = '.';
        }
    }
}

public static boolean isValid(char[][] chess, int row, int col, int n) {
    for (int i = 0; i < n; i++) {
        if (chess[i][col] == 'Q')
            return false;
    }
    
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (chess[i][j] == 'Q')
            return false;
    
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        if (chess[i][j] == 'Q')
            return false;
    
    return true;
}

Ⅷ 贪心

持续更新ing………

算法

#算法 #LeetCode #JAVA

通过自定义AOP实现二级缓存注解功能上一篇

详解JVM中StringTable原理下一篇