Leetcode Hot100 刷题笔记

// l1 和 l2 为当前遍历的节点，carry 为进位， 默认为0
private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null && carry == 0) { // 递归边界
        return null;
    }
    int s = carry;
    if (l1 != null) {
        s += l1.val; // 累加进位与节点值
        l1 = l1.next;
    }
    if (l2 != null) {
        s += l2.val;
        l2 = l2.next;
    }

    // s 除以 10 的余数为当前节点值，商为进位
    return new ListNode(s % 10, addTwo(l1, l2, s / 10));
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 由于可能会删除链表头部，用哨兵节点简化代码
    ListNode dummy = new ListNode(0, head);
    ListNode left = dummy;
    ListNode right = dummy;
    while (n-- > 0) {
        right = right.next; // 右指针先向右走 n 步
    }
    while (right.next != null) {
        left = left.next;
        right = right.next; // 左右指针一起走
    }
    left.next = left.next.next; // 左指针的下一个节点就是倒数第 n 个节点
    return dummy.next;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
        ListNode cur = dummy; // cur 指向新链表的末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 把 list1 加到新链表中
                list1 = list1.next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur.next = list2; // 把 list2 加到新链表中
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
}

public ListNode mergeKLists(ListNode[] lists) {
      // 用PriorityQueue优先队列构建最小堆
      PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
      for (ListNode head : lists) {
          if (head != null) {
              pq.offer(head); // 把所有非空链表的头节点入堆
          }
      }

      ListNode dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
      ListNode cur = dummy;
      while (!pq.isEmpty()) { // 循环直到堆为空
          ListNode node = pq.poll(); // 剩余节点中的最小节点
          if (node.next != null) { // 下一个节点不为空
              pq.offer(node.next); // 下一个节点有可能是最小节点，入堆
          }
          cur.next = node; // 把 node 添加到新链表的末尾
          cur = cur.next; // 准备合并下一个节点
      }
      return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
}

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head; // 乌龟和兔子同时从起点出发
    while (fast != null && fast.next != null) {
        slow = slow.next; // 乌龟走一步
        fast = fast.next.next; // 兔子走两步
        if (fast == slow) { // 兔子追上乌龟（套圈），说明有环
            return true;
        }
    }
    return false; // 访问到了链表末尾，无环
}

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) { // 相遇
            while (slow != head) { // 再走 a 步 (头指针走a步 = 慢指针从相遇位置走a步)
                slow = slow.next;
                head = head.next;
            }
            return slow;
        }
    }
    return null;
}

public ListNode sortList(ListNode head) {
    // 如果链表为空或者只有一个节点，无需排序
    if (head == null || head.next == null) {
        return head;
    }
    // 找到中间节点 head2，并断开 head2 与其前一个节点的连接
    // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
    ListNode head2 = middleNode(head);
    // 分别排序左边和右边
    head = sortList(head);
    head2 = sortList(head2);
    // 合并 -> 双指针 + 比较大小
    return mergeTwoLists(head, head2);
}

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }

public ListNode reverseList(ListNode head) {
      ListNode dummy = new ListNode();
      ListNode cur = head;
      while (cur != null) {
          ListNode nxt = cur.next;
          cur.next = dummy.next;
        	dummy.next = cur;
          cur = nxt;
      }
      return dummy.next;
  }

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

public boolean isPalindrome(ListNode head) {
      ListNode mid = middleNode(head); // 寻找中间节点
      ListNode head2 = reverseList(mid); // 反转链表
      while (head2 != null) {
          if (head.val != head2.val) { // 不是回文链表
              return false;
          }
          head = head.next;
          head2 = head2.next;
      }
      return true;
  }

void dfs(List<Integer> res, TreeNode root) {
		if(root==null) {
			return;
		}
		//按照 左-打印-右的方式遍历
		dfs(res,root.left);
		res.add(root.val);
		dfs(res,root.right);
	}

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

private boolean isValidBST(TreeNode node, long left, long right) {
    if (node == null) {
        return true;
    }
    long x = node.val;
    return left < x && x < right &&
           isValidBST(node.left, left, x) &&
           isValidBST(node.right, x, right);
}

public boolean isSymmetric(TreeNode root) {
    return root == null || recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
    if (L == null && R == null) return true;
    if (L == null || R == null || L.val != R.val) return false;
    return recur(L.left, R.right) && recur(L.right, R.left);
}

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return List.of();
    }
    List<List<Integer>> ans = new ArrayList<>();
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int n = q.size();
        List<Integer> vals = new ArrayList<>(n); // 预分配空间
        while (n-- > 0) {
            TreeNode node = q.poll();
            vals.add(node.val);
            if (node.left != null)  q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        ans.add(vals);
    }
    return ans;
}

// 自顶向下：先序遍历，ans是全局变量
public int maxDepth(TreeNode root) {
    dfs(root, 0);
    return ans;
}

private void dfs(TreeNode node, int depth) {
    if (node == null) {
        return;
    }
    depth++;
    ans = Math.max(ans, depth);
    dfs(node.left, depth);
    dfs(node.right, depth);
}
// 自底向上：后序遍历
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int lDepth = maxDepth(root.left);
    int rDepth = maxDepth(root.right);
    return Math.max(lDepth, rDepth) + 1;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int n = preorder.length;
    if (n == 0) { // 空节点
        return null;
    }
    int leftSize = indexOf(inorder, preorder[0]); // 左子树的大小
    int[] pre1 = Arrays.copyOfRange(preorder, 1, 1 + leftSize); // 先序左子树
    int[] pre2 = Arrays.copyOfRange(preorder, 1 + leftSize, n); // 先序右子树
    int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);       // 中序左子树
    int[] in2 = Arrays.copyOfRange(inorder, 1 + leftSize, n);   // 中序右子树
    TreeNode left = buildTree(pre1, in1);
    TreeNode right = buildTree(pre2, in2);
    return new TreeNode(preorder[0], left, right);
}

// 获取左子树大小：返回 x 在 a 中的下标，保证 x 一定在 a 中
private int indexOf(int[] a, int x) {
    for (int i = 0; ; i++) {
        if (a[i] == x) {
            return i;
        }
    }
}

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

// 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
private TreeNode dfs(int[] nums, int left, int right) {
    if (left == right) {
        return null;
    }
    int m = (left + right) >>> 1;
    return new TreeNode(nums[m], dfs(nums, left, m), dfs(nums, m + 1, right));
}

public void flatten(TreeNode root) {
    if (root == null) {
        return;
    }
    flatten(root.right); // 右节点
    flatten(root.left);  // 左节点
    root.left = null;  // 左子树置空
    root.right = pre; // 头插法，相当于链表的 root.next = head
    pre = root; // 现在链表头节点是 root
}

 public TreeNode invertTree(TreeNode root) {
 		if (root == null){
      	return null;
    }
    TreeNode left = invertTree(root.left);
   	TreeNode right = invertTree(root.right);
   	root.left = right; // 交换左右子树的值
    root.right = left;
    return root;
 }

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 基本情况处理：
    // 1.如果当前节点为空，返回null
    // 2.如果当前节点是p或q中的任一个，直接返回该节点
    if (root == null || root == p || root == q) {
        return root;
    }
    // 递归搜索左子树 
    TreeNode findInLeftTree = lowestCommonAncestor(root.left, p, q);
    // 递归搜索右子树
    TreeNode findInRightTree = lowestCommonAncestor(root.right, p, q);
    // 情况1: p和q分别位于当前节点的左右子树
    // 此时当前节点就是最近公共祖先
    if (findInLeftTree != null && findInRightTree != null) {
        return root;
    }
    // 情况2: p和q都在左子树中
    if (findInLeftTree != null) {
        return findInLeftTree;
    }
    // 情况3: p和q都在右子树中
    // 情况4: p和q都不在当前子树中(此时right为null)
    return findInRightTree;
}

private int s = 0; // 全局变量记录累加值
public TreeNode convertBST(TreeNode root) {
    dfs(root);
    return root;
}

private void dfs(TreeNode node) {
    if (node == null) {
        return;
    }
    dfs(node.right); // 递归右子树
    s += node.val;
    node.val = s; // 此时 s 就是 >= node.val 的所有数之和
    dfs(node.left); // 递归左子树
}

private int ans; // 全局变量记录结果
public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return ans;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return -1; // 对于叶子来说，链长就是 -1+1=0
    }
    int lLen = dfs(node.left) + 1; // 左子树最大链长+1
    int rLen = dfs(node.right) + 1; // 右子树最大链长+1
    ans = Math.max(ans, lLen + rLen); // 两条链拼成路径
    return Math.max(lLen, rLen); // 当前子树最大链长
}

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) return root2;
    if (root2 == null) return root1;
    return new TreeNode(root1.val + root2.val,
        mergeTrees(root1.left, root2.left),    // 合并左子树
        mergeTrees(root1.right, root2.right)); // 合并右子树
}

private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 四个方向
public boolean exist(char[][] board, String word) {
    // 为了方便，直接用数组代替哈希表
    int[] cnt = new int[128];
    for (char[] row : board) {
        for (char c : row) {
            cnt[c]++;
        }
    }

    // 优化一
    char[] w = word.toCharArray();
    int[] wordCnt = new int[128];
    for (char c : w) {
        if (++wordCnt[c] > cnt[c]) {
            return false;
        }
    }

    // 优化二
    if (cnt[w[w.length - 1]] < cnt[w[0]]) {
        w = new StringBuilder(word).reverse().toString().toCharArray();
    }

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (dfs(i, j, 0, board, w)) {
                return true; // 搜到了！
            }
        }
    }
    return false; // 没搜到
}

private boolean dfs(int i, int j, int k, char[][] board, char[] word) {
    if (board[i][j] != word[k]) { // 匹配失败
        return false;
    }
    if (k == word.length - 1) { // 匹配成功！
        return true;
    }
    board[i][j] = 0; // 标记访问过
    for (int[] d : DIRS) {
        int x = i + d[0];
        int y = j + d[1]; // 相邻格子
        if (0 <= x && x < board.length && 0 <= y && y < board[x].length && dfs(x, y, k + 1, board, word)) {
            return true; // 搜到了！
        }
    }
    board[i][j] = word[k]; // 恢复现场
    return false; // 没搜到
}

public int numIslands(char[][] grid) {
    int ans = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == '1') { // 找到了一个新的岛
                dfs(grid, i, j); // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                ans++;
            }
        }
    }
    return ans;
}

private void dfs(char[][] grid, int i, int j) {
    // 出界，或者不是 '1'，就不再往下递归
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
        return;
    }
    grid[i][j] = '2'; // 插旗！避免来回横跳无限递归
    dfs(grid, i, j - 1); // 往左走
    dfs(grid, i, j + 1); // 往右走
    dfs(grid, i - 1, j); // 往上走
    dfs(grid, i + 1, j); // 往下走
}

private int ans; // 全局记录答案
public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> cnt = new HashMap<>();
    cnt.put(0L, 1);
    dfs(root, 0, targetSum, cnt);
    return ans;
}
private void dfs(TreeNode node, long s, int targetSum, Map<Long, Integer> cnt) {
    if (node == null) {
        return;
    }

    s += node.val;
    // 把 node 当作路径的终点，统计有多少个起点
    ans += cnt.getOrDefault(s - targetSum, 0);

    cnt.merge(s, 1, Integer::sum); // cnt[s]++
    dfs(node.left, s, targetSum, cnt);
    dfs(node.right, s, targetSum, cnt);
    cnt.merge(s, -1, Integer::sum); // cnt[s]-- 恢复现场，防止遍历完左子树，遍历右子树的时候出现前缀合多加上左子树值的情况。
}

private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    int n = digits.length();
    if (n == 0) {
        return List.of();
    }
    List<String> ans = new ArrayList<>();
    char[] path = new char[n]; // 注意 path 长度一开始就是 n，不是空数组
    dfs(0, ans, path, digits.toCharArray());
    return ans;
}

private void dfs(int i, List<String> ans, char[] path, char[] digits) {
    if (i == digits.length) {
        ans.add(new String(path));
        return;
    }
    String letters = MAPPING[digits[i] - '0'];
    for (char c : letters.toCharArray()) {
        path[i] = c; // 直接覆盖 (相当于赋值+恢复现场一体)
        dfs(i + 1, ans, path, digits);
    }
}

public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        char[] path = new char[n * 2]; // 所有括号长度都是一样的 2n
        dfs(0, 0, n, path, ans); // 一开始没有填括号
        return ans;
    }

// 目前填了 left 个左括号，right 个右括号
private void dfs(int left, int right, int n, char[] path, List<String> ans) {
    if (right == n) { // 填完 2n 个括号
        ans.add(new String(path));
        return;
    }
    if (left < n) { // 可以填左括号
        path[left + right] = '('; // 直接覆盖
        dfs(left + 1, right, n, path, ans);
    }
    if (right < left) { // 可以填右括号
        path[left + right] = ')'; // 直接覆盖
        dfs(left, right + 1, n, path, ans);
    }
}

public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, 0, n, path, ans);
        return ans;
    }
// 目前填了 i 个括号
// 这 i 个括号中的左括号个数 - 右括号个数 = balance
private void dfs(int i, int balance, int n, List<Integer> path, List<String> ans) {
    if (path.size() == n) {
        char[] s = new char[n * 2];
        Arrays.fill(s, ')');
        for (int j : path) {
            s[j] = '(';
        }
        ans.add(new String(s));
        return;
    }
    // 枚举填 right=0,1,2,...,balance 个右括号
    for (int right = 0; right <= balance; right++) {
        // 先填 right 个右括号，然后填 1 个左括号，记录左括号的下标 i+right
        path.add(i + right);
        dfs(i + right + 1, balance - right + 1, n, path, ans);
        path.removeLast(); // path.remove(path.size() - 1);
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }
private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
    if (left == 0) {
        // 找到一个合法组合
        ans.add(new ArrayList<>(path));
        return;
    }
    if (i == candidates.length || left < candidates[i]) {
        // 如果candidates[i] > left，说明后面的数都比 left 要大，path数组的和不可能为left
        return;
    }

    // 不选
    dfs(i + 1, left, candidates, ans, path);

    // 选
    path.add(candidates[i]);
    dfs(i, left - candidates[i], candidates, ans, path);
    path.remove(path.size() - 1); // 恢复现场
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }
private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
    if (left == 0) {
        // 找到一个合法组合
        ans.add(new ArrayList<>(path));
        return;
    }

    // 枚举当前位置，选哪个元素
    for (int k = i; k < candidates.length && candidates[k] <= left; k++) {
        path.add(candidates[k]);
        dfs(k, left - candidates[k], candidates, ans, path);
        path.remove(path.size() - 1); // 恢复现场
    }
}