algorithm-hot100

没有特殊说明，题目均来自牛客面试必刷101

链表

反转链表

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

class Node {
  int val;
  Node nxt;
  public Node(int val) {
    this.val = val;
  }
}
public class Solution {
  public static void main(String[] args) {
    Node dummy = new Node(-1), pre = dummy;
    for (int i = 0; i < 10; i++) {
      Node cur = new Node(i);
      pre.nxt = cur;
      pre = cur;
    }
    pre = null;
    Node cur = dummy.nxt;
    while (cur != null) {
      Node nxt = cur.nxt;
      cur.nxt = pre;
      pre = cur;
      cur = nxt;
    }
    while (pre != null) {
      System.out.println(pre.val);
      pre = pre.nxt;
    }
  }
}

链表内指定区间反转

public ListNode reverseBetween (ListNode head, int m, int n) {  // 思路和普通反转链表一样，但需要调整区间的头尾节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = dummy, pre = null;
    int cnt = 0;
    while (cnt < m) {  // 找到第m-1个节点，记为ahead
        pre = cur;
        cur = cur.next;
        cnt++;
    }
    ListNode ahead = pre;
    while (cnt <= n && cur != null) {  // 反转m到n区间节点
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
        cnt++;
    }
    ahead.next.next = cur;  // 调整原本第m个节点的next指针
    ahead.next = pre;  // 调整ahead节点的next指针
    return dummy.next;
}

public ListNode reverseBetween (ListNode head, int m, int n) {  // 修改反转思路
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = dummy, pre = null;
    int cnt = 0;
    while (cnt < m) {
        pre = cur;
        cur = cur.next;
        cnt++;
    }
    // [1,2,3,4,5], m=2, n=4 -> [1,3,2,4,5], [1,4,3,2,5]
    while (cnt < n && cur.next != null) {  // 直接把nxt节点插入到pre节点的next位置
        ListNode nxt = cur.next;
        cur.next = nxt.next;
        nxt.next = pre.next;
        pre.next = nxt;
        cnt++;
    }
    return dummy.next;
}

合并两个排序的链表

public ListNode Merge (ListNode pHead1, ListNode pHead2) {  // 合并两个已排序的链表
    ListNode dummy = new ListNode(0), cur = dummy;;
    while (pHead1 != null && pHead2 != null) {
        if (pHead1.val < pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        }
        else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    cur.next = pHead1 != null ? pHead1 : pHead2;
    return dummy.next;
}

合并k个已排序的链表

public ListNode mergeKLists (ArrayList<ListNode> lists) {
    // write code here
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    ListNode dummy = new ListNode(0), cur = dummy;
    for (ListNode list : lists) {
        if (list != null) pq.offer(list);
    }
    while (!pq.isEmpty()) {
        ListNode p = pq.poll();
        cur.next = p;
        p = p.next;
        if (p != null) pq.offer(p);
        cur = cur.next;
    }
    return dummy.next;
}

判断链表是否有环

链表中环的入口结点

public ListNode EntryNodeOfLoop(ListNode pHead) {  // 快慢指针
    ListNode slow = pHead, fast = pHead;  // slow和fast初始位置必须相同，否则fast初始化pHead.next则可能死循环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;
    ListNode head = pHead;
    while (head != slow) {
        head = head.next;
        slow = slow.next;
    }
    return head;
}

链表中倒数最后k个结点

public ListNode FindKthToTail (ListNode pHead, int k) {  // 快慢指针，快指针先走k步
    ListNode slow = pHead, fast = pHead;
    while (k-- > 0) {
        if (fast == null) return null;
        fast = fast.next;
    }
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

public ListNode FindKthToTail (ListNode pHead, int k) {  // 先找到总长度，再遍历
    ListNode cur = pHead;
    int cnt = 0;
    while (cur != null) {
        cur = cur.next;
        cnt++;
    }
    if (cnt < k) return null;
    cur = pHead;
    for (int i = 0; i < cnt-k; i++) {
        cur = cur.next;
    }
    return cur;
}

两个链表的第一个公共结点

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode cur1 = pHead1, cur2 = pHead2;
    while (cur1 != cur2) {
        cur1 = cur1 == null ? pHead2 : cur1.next;
        cur2 = cur2 == null ? pHead1 : cur2.next;
    }
    return cur1;
}

链表相加(二)：两个链表组成的数字相加，形成一个新链表

public ListNode addInList (ListNode head1, ListNode head2) {
    ListNode cur1 = reverse(head1), cur2 = reverse(head2);
    ListNode dummy = new ListNode(-1), pre = dummy;
    int add = 0;
    while (cur1 != null || cur2 != null || add != 0) {
        int add1 = cur1 == null ? 0 : cur1.val;
        int add2 = cur2 == null ? 0 : cur2.val;
        int val = add1 + add2 + add;
        if (val >= 10) {
            val -= 10;
            add = 1;
        }
        else add = 0;
        ListNode cur = new ListNode(val);
        pre.next = cur;
        pre = cur;
        if (cur1 != null) cur1 = cur1.next;
        if (cur2 != null) cur2 = cur2.next;
    }
    ListNode res = dummy.next;
    dummy = null;
    return reverse(res);
}
private ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

单链表的排序

public ListNode sortInList (ListNode head) {  // 排序节点值后赋值
    List<Integer> list = new ArrayList<>();
    ListNode cur = head;
    while (cur != null) {
        list.add(cur.val);
        cur = cur.next;
    }
    list.sort((a, b) -> a-b);
    cur = head;
    for (int i = 0; i < list.size(); i++) {
        cur.val = list.get(i);
        cur = cur.next;
    }
    return head;
}

public ListNode sortInList (ListNode head) {  // 排序节点
    List<ListNode> list = new ArrayList<>();
    ListNode cur = head;
    while (cur != null) {
        list.add(cur);
        cur = cur.next;
    }
    list.sort((a, b) -> a.val-b.val);
    for (int i = 0; i < list.size(); i++) {
        cur = list.get(i);
        cur.next = i+1 < list.size() ? list.get(i+1) : null;
    }
    return list.get(0);
}

public ListNode sortInList (ListNode head) {  // 归并排序
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;  // slow和fast初始位置可以不同，来调整奇偶情况的中间节点位置
    while (fast != null && fast.next != null) {  // 快慢指针找到中间节点
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;  // 奇数情况，左边链表长度 比 右边链表长度 +1
    slow.next = null;
    return Merge(sortInList(head), sortInList(mid));
}
public ListNode Merge (ListNode pHead1, ListNode pHead2) {  // 合并两个已排序的链表
    ListNode dummy = new ListNode(0), cur = dummy;;
    while (pHead1 != null && pHead2 != null) {
        if (pHead1.val < pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        }
        else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    cur.next = pHead1 != null ? pHead1 : pHead2;
    return dummy.next;
}

判断一个链表是否为回文结构

public boolean isPail (ListNode head) {  // O(n)空间 用一个List保存所有元素
    ListNode cur = head;
    List<Integer> list = new ArrayList<>();
    while (cur != null) {
        list.add(cur.val);
        cur = cur.next;
    }
    int sz = list.size();
    for (int i = 0; i < sz/2; i++) {
        if ((int)list.get(i) != (int)list.get(sz-1-i)) return false;
    }
    return true;
}

public boolean isPail (ListNode head) {  // O(1)空间，获取中间节点，反转右边链表
    ListNode slow = head, fast = head.next;  // 获取偏左的中间节点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode tail = ReverseList(slow.next);  // 反转中间节点右边的链表
    ListNode left = head, right = tail;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}
public ListNode ReverseList (ListNode head) {
    ListNode cur = head, pre = null;
    while (cur != null) {
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

链表的奇偶重排

public ListNode oddEvenList (ListNode head) {  // O(n)空间复杂度
    List<ListNode> list1 = new ArrayList<>();  // 奇数位节点
    List<ListNode> list2 = new ArrayList<>();  // 偶数位节点
    ListNode cur = head;
    int cnt = 0;
    while (cur != null) {
        if (cnt++ % 2 == 0) list1.add(cur);
        else list2.add(cur);
        cur = cur.next;
    }
    ListNode dummy = new ListNode(-1), pre = dummy;
    for (ListNode node : list1) {
        pre.next = node;
        pre = node;
    }
    for (ListNode node : list2) {
        pre.next = node;
        pre = node;
    }
    if (list2.size() > 0) list2.get(list2.size()-1).next = null;
    return dummy.next;
}

public ListNode oddEvenList (ListNode head) {  // O(1)空间复杂度
    if (head == null) return head;
    ListNode second = head.next;  // 偶数节点链表的头节点
    ListNode cur1 = head, cur2 = head.next;  // 分别遍历奇偶链表
    while (cur2 != null && cur2.next != null) {
        cur1.next = cur2.next;  // 修改奇数链表的指针
        cur2.next = cur2.next.next;  // 修改偶数链表的指针
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    cur1.next = second;  // 最后，奇数链表的尾节点连接到偶数节点链表的头节点
    return head;
}

删除有序链表中重复的元素-1：删除值重复的节点，剩下一个

public ListNode deleteDuplicates (ListNode head) {
    ListNode cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;  // 找到下一个值不一样的节点
        while (nxt != null && nxt.val == cur.val) nxt = nxt.next;
        cur.next = nxt;
        cur = nxt;
    }
    return head;
}

删除有序链表中重复的元素-2：删除值重复的所有节点

public ListNode deleteDuplicates (ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = head, pre = dummy;
    while (cur != null) {
        ListNode nxt = cur.next;  // 找到下一个值不一样的节点
        while (nxt != null && nxt.val == cur.val) nxt = nxt.next;
        if (cur.next == nxt) {  // 如果就是当前节点的下一节点，则不用删除
            pre = cur;
            cur = nxt;
        } else {  // 否则删除中间重复值的节点
            pre.next = nxt;
            cur = nxt;
        }
    }
    return dummy.next;
}

二分查找/排序

二分查找

public int search (int[] nums, int target) {
    int n = nums.length, l = 0, r = n-1;
    if (n == 0) return -1;
    while (l < r) {
        int mid = l + (r-l)/2;
        if (nums[mid] >= target) r = mid;
        else l = mid+1;
    }
    return nums[l] == target ? l : -1;
}

寻找峰值

public int findPeakElement (int[] nums) {
    int n = nums.length;
    int t[] = new int[n+2];
    System.arraycopy(nums, 0, t, 1, n);
    int l = 1, r = n;
    while (l < r) {
        int mid = l + (r-l)/2;
        if (t[mid] < t[mid+1]) l = mid+1;  // 右边一定有峰
        else if (t[mid] < t[mid-1]) r = mid;  // 左边一定有峰
        else return mid-1;  // 当前就是峰
    }
    return l-1;
}

数组中的逆序对（归并排序计数）

int res = 0, MOD = (int)1e9+7;
public int InversePairs (int[] nums) {
    int n = nums.length;
    mergeSort(nums, 0, n-1);
    return res;
}
private void mergeSort(int[] nums, int l, int r) {
    int mid = l + (r-l)/2;
    if (l < mid) mergeSort(nums, l, mid);
    if (mid+1 < r) mergeSort(nums, mid+1, r);
    merge(nums, l, mid, r);
}
private void merge(int[] nums, int l, int mid, int r) {
    int i = l, j = mid+1, idx = 0;
    int[] t = new int[r-l+1];
    while (i <= mid && j <= r) {
        if (nums[j] <= nums[i]) {
            res = (res + mid - i + 1) % MOD;
            t[idx++] = nums[j++];
        }
        else {
            t[idx++] = nums[i++];
        }
    }
    while (i <= mid) t[idx++] = nums[i++];
    while (j <= r) t[idx++] = nums[j++];
    for (int k = 0; k < t.length; k++) {
        nums[k+l] = t[k];
    }
}

旋转数组的最小数字

public int minNumberInRotateArray (int[] nums) {
    int n = nums.length, l = 0, r = n-1;
    while (l < r) {
        int mid = l + (r-l)/2;
        if (nums[mid] > nums[r]) l = mid+1;
        else if (nums[mid] < nums[r])r = mid;
        else r--;  // 相等情况无法二分，需要一个一个减右边界
    }
    return nums[l];
}

比较版本号

public int compare (String version1, String version2) {
    String words1[] = version1.split("\\."), words2[] = version2.split("\\.");
    int n1 = words1.length, n2 = words2.length;
    int idx = 0;
    while (idx < n1 || idx < n2) {
        int v1 = idx < n1 ? Integer.valueOf(words1[idx]) : 0;
        int v2 = idx < n2 ? Integer.valueOf(words2[idx]) : 0;
        if (v1 > v2) {
            return 1;
        }
        else if (v1 < v2) {
            return -1;
        }
        idx++;
    }
    return 0;
}

二叉树

先序遍历、中序遍历、后序遍历

private void preOrder(TreeNode cur, List<Integer> list) {  // 递归通用写法
    if (cur == null) return;
    list.add(cur.val);  // 前序
    preOrder(cur.left, list);
    // list.add(cur.val);  // 中序
    preOrder(cur.right, list);
    // list.add(cur.val);  // 后序
}
public int[] preorderTraversal (TreeNode root) {  // 非递归，前序遍历简单写法
    if (root == null) return new int[]{};
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode p = stack.pop();
        list.add(p.val);
        System.out.print(p.val + " ");
        // 先压右，再压左，保证左先弹出
        if (p.right != null) stack.push(p.right);
        if (p.left != null) stack.push(p.left);
    }
    return list.stream().mapToInt(i->i).toArray();
}
public int[] postorderTraversal (TreeNode root) {  // 非递归，后序遍历简单写法，双栈
    if (root == null) return new int[]{};
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> reverseStack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode p = stack.pop();
        reverseStack.push(p);
        // 先压左，再压右，保证右先弹出到reverseStack
        if (p.left != null) stack.push(p.left);
        if (p.right != null) stack.push(p.right);
    }
    while (!reverseStack.isEmpty()) list.add(reverseStack.pop().val);
    return list.stream().mapToInt(i->i).toArray();
}
public int[] preorderTraversal (TreeNode root) {  // 非递归，前序中序通用解法
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            list.add(cur.val);  // 前序遍历
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode p = stack.pop();
        // list.add(p.val);  // 中序遍历
        cur = p.right;
    }
    return list.stream().mapToInt(i -> i).toArray();
}
public int[] postorderTraversal (TreeNode root) {  // 非递归，后序遍历单栈写法
    if (root == null) return new int[]{};
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root, pre = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {  // 优先找左边节点
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode p = stack.pop();
        if (p.right == null || pre == p.right) {  // 右边没有元素或者已访问
            list.add(p.val);
            pre = p;
        } else {  // 当前节点入栈并访问右边
            stack.push(p);
            cur = p.right;
        }
    }
    return list.stream().mapToInt(i->i).toArray();
}

二叉树的最大深度

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

二叉搜索树与双向链表（转换成双向链表）

public TreeNode Convert(TreeNode pRootOfTree) {
    return inOrder(pRootOfTree)[0];
}
private TreeNode[] inOrder(TreeNode cur) {
    if (cur == null) return new TreeNode[]{null, null};
    TreeNode left[] = inOrder(cur.left);
    TreeNode right[] = inOrder(cur.right);
    TreeNode pre = left[1], nxt = right[0];
    if (pre != null) pre.right = cur;
    cur.left = pre;
    if (nxt != null) nxt.left = cur;
    cur.right = nxt;
    TreeNode l = left[0] == null ? cur : left[0], r = right[1] == null ? cur : right[1];
    return new TreeNode[]{l, r};
}

合并二叉树

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
}

二叉树的镜像

public TreeNode Mirror (TreeNode pRoot) {
    if (pRoot == null) return null;
    TreeNode left = pRoot.left;  // 需要提前定义，因为被下一句替换了
    pRoot.left = Mirror(pRoot.right);
    pRoot.right = Mirror(left);
    return pRoot;
}

判断是不是二叉搜索树

public boolean isValidBST (TreeNode root) {  // 丑陋dfs，外置一个变量保存结果，dfs结果返回子树范围
    dfs(root);
    return flag;
}
boolean flag = true;
public int[] dfs(TreeNode cur) {
    if (cur == null) return null;
    int[] left = dfs(cur.left), right = dfs(cur.right);
    if (left != null && cur.val <= left[1]) flag = false;
    if (right != null && cur.val >= right[0]) flag = false;
    int min = left == null ? cur.val : left[0], max = right == null ? cur.val : right[1];
    return new int[]{min, max};
}

public boolean isValidBST (TreeNode root) {  // 优雅dfs，参数中放置范围
    return dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean dfs(TreeNode cur, int l, int r) {
    if (cur == null) return true;
    if (cur.val <= l || cur.val >= r) return false;
    return dfs(cur.left, l, cur.val) && dfs(cur.right, cur.val, r);
}

public boolean isValidBST (TreeNode root) {  // 中序遍历dfs中添加判断
    return dfs(root);
}
int min = Integer.MIN_VALUE;
public boolean dfs(TreeNode cur) {
    if (cur == null) return true;
    if (!dfs(cur.left)) return false;
    if (cur.val <= min) return false;
    min = cur.val;
    return dfs(cur.right);
}

判断是不是完全二叉树

public boolean isCompleteTree (TreeNode root) {  // bfs，通过判断当前节点是否可以有子节点
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    boolean children = true;
    while (!dq.isEmpty()) {
        TreeNode p = dq.poll();
        if (p == null) continue;
        if (p.left == null && p.right != null) return false;
        if (!children && (p.left != null || p.right != null)) return false;
        if (p.right == null) children = false;
        dq.offer(p.left);
        dq.offer(p.right);
    }
    return true;
}

public boolean isCompleteTree (TreeNode root) {  // bfs，通过判断当前节点是否还可以出现
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    boolean getNull = false;
    while (!dq.isEmpty()) {
        TreeNode p = dq.poll();
        if (p == null) {
            getNull = true;
            continue;
        }
        if (getNull) return false;
        dq.offer(p.left);
        dq.offer(p.right);
    }
    return true;
}

判断是不是平衡二叉树

public boolean IsBalanced_Solution (TreeNode pRoot) {
    dfs(pRoot);
    return res;
}
boolean res = true;
public int dfs(TreeNode cur) {  // dfs找到当前子树的高度，同时判断左右子树高度差是否满足
    if (cur == null) return 0;
    int left = dfs(cur.left) + 1, right = dfs(cur.right) + 1;
    if (Math.abs(left - right) > 1) res = false;
    return Math.max(left, right);
}

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

public int lowestCommonAncestor (TreeNode root, int p, int q) {  // dfs查找
    if (p < root.val && q < root.val) return lowestCommonAncestor(root.left, p, q);
    else if (p > root.val && q > root.val) return lowestCommonAncestor(root.right, p, q);
    else return root.val;
}

public int lowestCommonAncestor (TreeNode root, int p, int q) {  // 按照大小直接向下查找
    while (root != null) {
        if (p < root.val && q < root.val) root = root.left;
        else if (p > root.val && q > root.val) root = root.right;
        else return root.val;
    }
    return -1;
}

public int lowestCommonAncestor (TreeNode root, int p, int q) {  // bfs逐一判断
    Deque<TreeNode> dq = new ArrayDeque<>();
    dq.offer(root);
    while (!dq.isEmpty()) {
        TreeNode cur = dq.poll();
        if (Math.min(p, q) <= cur.val && cur.val <= Math.max(p, q)) return cur.val;
        if (cur.left != null) dq.offer(cur.left);
        if (cur.right != null) dq.offer(cur.right);
    }
    return -1;
}

在二叉树中找到两个节点的最近公共祖先

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    if (root == null) return -1;
    if (root.val == o1 || root.val == o2) return root.val;  // 当前节点满足
    int left = lowestCommonAncestor(root.left, o1, o2);
    int right = lowestCommonAncestor(root.right, o1, o2);
    if (left != -1 && right != -1) return root.val;  // 左右子树分别包含o1和o2，返回当前节点值
    return left == -1 ? right : left;  // 只有其中一个子树包含
}

序列化二叉树

String Serialize(TreeNode root) {  // 通过前序遍历和中序遍历构建字符串
    return preOrder(root) + "|" + inOrder(root);
}
String preOrder(TreeNode cur) {
    if (cur == null) return "";  // 不记录空的子节点
    String res = "";
    res += cur.val + ".";  // 最后会多一个"."
    res += preOrder(cur.left);
    res += preOrder(cur.right);
    return res;
}
String inOrder(TreeNode cur) {
    if (cur == null) return "";
    String res = "";
    res += inOrder(cur.left);
    res += cur.val + ".";
    res += inOrder(cur.right);
    return res;
}
TreeNode Deserialize(String str) {  // 通过字符串解析出前序遍历和中序遍历数组，并通过这两个数组构建二叉树
    String[] words = str.split("\\|");
    if (words.length < 2) return null;
    String[] preWords = words[0].split("\\."), inWords = words[1].split("\\.");
    int n = preWords.length;
    int[] pre = new int[n], in = new int[n];
    for (int i = 0; i < n; i++) {
        pre[i] = Integer.valueOf(preWords[i]);
        in[i] = Integer.valueOf(inWords[i]);
    }
    return reConstructBinaryTree(pre, in);
}
public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {  // 递归解决
    return dfs(preOrder, vinOrder, 0, preOrder.length-1, 0, vinOrder.length-1);
}
// preLeft和preRight代表preOrder窗口的左右指针，inLeft和inRight同理代表inOrder
public TreeNode dfs(int[] preOrder, int[] inOrder, int preLeft, int preRight, int inLeft, int inRight) {
    if (preLeft > preRight) return null;
    for (int i = inLeft; i <= inRight; i++) {
        // preOrder当前窗口的第一个位置就是当前节点值，即preLeft位置
        if (inOrder[i] == preOrder[preLeft]) {  // 找到inOrder窗口中对应的节点位置i
            TreeNode cur = new TreeNode(preOrder[preLeft]);
            int leftWindowLen = i-1-inLeft+1;
            // 位置i将inOrder窗口分为两半，preOrder按照对应长度也分为两半，分别递归得到下一个左右节点
            cur.left = dfs(preOrder, inOrder, preLeft+1, preLeft+leftWindowLen, inLeft, i-1);
            cur.right = dfs(preOrder, inOrder, preLeft+leftWindowLen+1, preRight, i+1, inRight);
            return cur;
        }
    }
    return null;
}

public class Solution {
    String Serialize(TreeNode root) {  // 只通过前序遍历构建字符串，但前序遍历需要记录空的子节点
        return preOrder(root);
    }
    String preOrder(TreeNode cur) {  // 记录空的子节点为'#'，同时也不会多一个'.'
        if (cur == null) return "#";
        return cur.val + "." + preOrder(cur.left) + "." + preOrder(cur.right);
    }
    int idx = -1;
    TreeNode Deserialize(String str) {  // 通过字符串解析出前序遍历和中序遍历数组，并通过这两个数组构建二叉树
        String[] words = str.split("\\.");  // 这里每次都split可能很慢，可以用words作为传参解决
        if (words[++idx].equals("#")) {
            return null;
        }
        TreeNode cur = new TreeNode(Integer.valueOf(words[idx]));  // 同样按照先序遍历的顺序，反序列化
        cur.left = Deserialize(str);
        cur.right = Deserialize(str);
        return cur;
    }
}

String Serialize(TreeNode root) {  // 通过层次遍历，也需要记录空的子节点，记录为-1
    String res = "";
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    while (!dq.isEmpty()) {
        TreeNode p = dq.poll();
        res += (p == null ? "-1" : p.val) + ".";
        if (p != null) {
            dq.offer(p.left);
            dq.offer(p.right);
        }
    }
    return res;
}
TreeNode Deserialize(String str) {  // 通过层次遍历字符串得到数组，并同样用dq顺序访问
    String[] words = str.split("\\.");
    int n = words.length;
    if (n == 0 || words[0].equals("-1")) return null;
    TreeNode root = new TreeNode(Integer.valueOf(words[0]));
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    for (int i = 1; i < n; i += 2) {
        int leftVal = Integer.valueOf(words[i]), rightVal = Integer.valueOf(words[i+1]);
        TreeNode cur = dq.poll();
        if (leftVal != -1) {
            cur.left = new TreeNode(leftVal);
            dq.offer(cur.left);
        }
        if (rightVal != -1) {
            cur.right = new TreeNode(rightVal);
            dq.offer(cur.right);
        }
    }
    return root;
}

重建二叉树

public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {  // 递归解决
    return dfs(preOrder, vinOrder, 0, preOrder.length-1, 0, vinOrder.length-1);
}
// preLeft和preRight代表preOrder窗口的左右指针，inLeft和inRight同理代表inOrder
public TreeNode dfs(int[] preOrder, int[] inOrder, int preLeft, int preRight, int inLeft, int inRight) {  // 这里构造树遍历中序数组，可读性没有遍历先序数组好，可以看下输出二叉树的右视图这题
    if (preLeft > preRight) return null;
    for (int i = inLeft; i <= inRight; i++) {
        // preOrder当前窗口的第一个位置就是当前节点值，即preLeft位置
        if (inOrder[i] == preOrder[preLeft]) {  // 找到inOrder窗口中对应的节点位置i
            TreeNode cur = new TreeNode(preOrder[preLeft]);
            int leftWindowLen = i-1-inLeft+1;
            // 位置i将inOrder窗口分为两半，preOrder按照对应长度也分为两半，分别递归得到下一个左右节点
            cur.left = dfs(preOrder, inOrder, preLeft+1, preLeft+leftWindowLen, inLeft, i-1);
            cur.right = dfs(preOrder, inOrder, preLeft+leftWindowLen+1, preRight, i+1, inRight);
            return cur;
        }
    }
    return null;
}

输出二叉树的右视图

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图（每一层的最右节点）

public int[] solve (int[] preOrder, int[] inOrder) {
    int n = preOrder.length;
    TreeNode root = dfs(preOrder, inOrder, 0, n-1, 0, n-1);
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    List<Integer> res = new ArrayList<>();
    while (!dq.isEmpty()) {  // 层序遍历得到每一层
        res.add(dq.peekLast().val);  // 每一层最后一个元素添加到res
        for (int i = dq.size(); i > 0; i--) {
            TreeNode p = dq.poll();
            if (p.left != null) dq.offer(p.left);
            if (p.right != null) dq.offer(p.right);
        }
    }
    return res.stream().mapToInt(i->i).toArray();
}
public TreeNode dfs(int[] preOrder, int[] inOrder, int l1, int r1, int l2, int r2) {  // 构造树
    if (l1 > r1 || l2 > r2) return null;
    TreeNode cur = new TreeNode(preOrder[l1]);
    for (int i = l1; i <= r1; i++) {  // 遍历先序数组
        if (preOrder[l1] == inOrder[l2+i-l1]) {  // 将中序数组分割成两半，左半是左子树，右半是右子树
            cur.left = dfs(preOrder, inOrder, l1+1, i, l2, l2+i-l1-1);
            cur.right = dfs(preOrder, inOrder, i+1, r1, l2+i-l1+1, r2);
        }
    }
    return cur;
}

栈/队列

用两个栈实现队列

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();    
public void push(int node) {
    stack1.push(node);
}
public int pop() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

包含min函数的栈

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();        
    public void push(int node) {
        stack1.push(node);
        if (stack2.isEmpty() || node <= stack2.peek()) stack2.push(node);  // 小于等于才加入
        // stack2.push(Math.min(node, stack2.isEmpty() ? (int)1e9 : stack2.peek()));  // 解法2，每次压入栈的最小值
    }
    public void pop() {
        int p = stack1.pop();
        if (p == stack2.peek()) stack2.pop();  // 等于才弹出
        // stack2.pop();  // 解法2
    }
    public int top() {
        return stack1.peek();
    }
    public int min() {
        return stack2.peek();
    }
}

有效括号序列（括号匹配）

public boolean isValid (String s) {
    // write code here
    char cs[] = s.toCharArray();
    Map<Character, Character> MAP = new HashMap<>();
    MAP.put(')', '('); MAP.put('}', '{'); MAP.put(']', '[');
    Deque<Character> stack = new LinkedList<>();
    for (char c : cs) {
        Character match = MAP.get(c);
        if (match == null) {
            stack.push(c);
        }
        else {
            if (!stack.isEmpty() && stack.peek().equals(match)) {
                stack.pop();
            }
            else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

用两个栈实现队列

滑动窗口的最大值

public ArrayList<Integer> maxInWindows (int[] num, int size) {
    int n = num.length;
    ArrayList<Integer> res = new ArrayList<>();
    if (size == 0) return res;
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekLast() <= i - size) dq.pollLast();  // 如果栈底超过窗口范围，弹出栈底
        while (!dq.isEmpty() && num[i] > num[dq.peek()]) {  // 递增栈
            dq.pop();
        }
        dq.push(i);
        if (i >= size-1) res.add(num[dq.peekLast()]);  // 栈底是最大值
    }
    return res;
}

表达式求值

public int solve (String s) {
    char[] cs = s.toCharArray();
    int n = cs.length, res = 0, num = 0;
    Deque<Integer> st = new LinkedList<>();  // 用一个栈保存所有需要相加的元素
    char op = '+';  // 记录上一个运算符号
    for (int i = 0; i < n; i++) {
        if (Character.isDigit(cs[i])) {  // 计算当前数字
            num = num * 10 + (cs[i]-48);
        } else if(cs[i] == '(') {  // 遇到左括号，需要递归计算子表达式的结果
            int cnt = 1, j = i+1;
            while (j < n) {
                if (cs[j] == '(') cnt++;
                else if (cs[j] == ')') cnt--;
                if (cnt == 0) break;
                j++;
            }
            num = solve(s.substring(i+1, j));
            i = j;
        }
        if (i == n-1 || cs[i] == '+' || cs[i] == '-' || cs[i] == '*') {  // 遇到结尾或者运算符号，说明当前值计算完毕可以放入栈中，并通过上一个运算符号判断需要存入栈的值
            if (op == '+') st.push(num);
            else if (op == '-') st.push(-num);
            else if (op == '*') st.push(st.pop() * num);
            op = cs[i];
            num = 0;
        }
    }
    while (!st.isEmpty()) res += st.pop();  // 栈中所有值的和就是答案
    return res;
}

堆

最小的k个数

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {  // 堆O(nlogk)，还可以用快排O(n)
   // write code here
    int n = input.length;
    ArrayList<Integer> res = new ArrayList<>();
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);  // 维护大小为k的最大堆优先队列，保存当前的最小k个数
    for (int i = 0; i < k; i++) {
        pq.offer(input[i]);
    }
    for (int i = k; i < n; i++) {
        if (!pq.isEmpty() && input[i] < pq.peek()) {  // 和堆顶最大值相比较，小于则放入
            pq.poll();
            pq.offer(input[i]);
        }
    }
    for (int x : pq) {  // 这样遍历不保证大小顺序（要顺序请用poll）
        res.add(x);
    }
    return res;
}

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {  // 手写最大堆
    int n = input.length;
    ArrayList<Integer> res = new ArrayList<>();
    if (k == 0) return res;
    int[] heap = new int[k+1];
    for (int i = 0; i < k; i++) {
        heap[i+1] = input[i];
    }
    buildHeap(heap, k);
    for (int i = k; i < n; i++) {
        if (input[i] < heap[1]) {
            heap[1] = input[i];
            heapify(heap, 1, k);
        }
    }
    for (int i = 0; i < k; i++) {  // 这样遍历不保证大小顺序（要顺序请用poll）
        res.add(heap[i+1]);
    }
    return res;
}
private void buildHeap(int[] heap, int size) {
    for (int i = size/2; i > 0; i--) {
        heapify(heap, i, size);
    }
}
private void heapify(int[] heap, int i, int size) {
    int largest = i;
    int left = i*2, right = i*2 + 1;
    if (left <= size && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right <= size && heap[right] > heap[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(heap, largest, i);
        heapify(heap, largest, size);
    }
}
private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

寻找第k大的数

public int findKth (int[] a, int n, int K) {
    // return quickSort(a, 0, n-1, K-1);  // 寻找第k小的数
    return quickSort(a, 0, n-1, n-K);
}
private void swap(int nums[], int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
private int partition(int nums[], int l, int r) {
    int pivot = nums[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        while (i < j && nums[i] <= pivot) i++;
        swap(nums, i, j);
        if (i == j) swap(nums, l, j);
    }
    return j;
}
private int quickSort(int nums[], int l, int r, int K) {
    int p = partition(nums, l, r);
    if (K < p) return quickSort(nums, l, p-1, K);
    else if (K > p) return quickSort(nums, p+1, r, K);
    else return nums[p];
}

数据流的中位数

PriorityQueue<Integer> up = new PriorityQueue<>();  // 最小堆，存储数值较大的上半部分，奇数时个数更多
PriorityQueue<Integer> down = new PriorityQueue<>((a, b) -> b - a);  // 最大堆，存储下半部分
public void Insert(Integer num) {
    up.offer(num);  
    down.offer(up.poll());
    if (down.size() > up.size()) {  // 平衡两个堆，下半部分更多时弹出给上半部分
       up.offer(down.poll());
    }
}

public Double GetMedian() {
    if (up.size() > down.size()) {  // 奇数情况
        return (double)up.peek();
    }
    else {
        return (double)(up.peek() + down.peek()) / 2;
    }
}

哈希

数组中出现次数超过一半的数字

public int MoreThanHalfNum_Solution (int[] numbers) {  // 候选数字 O(n)
    int candidate = -1, cnt = 0;
    for (int x : numbers) {
        if (cnt == 0) {
            candidate = x;
            cnt++;
        }
        else {
            if (x != candidate) cnt--;
            else cnt++;
        }
    }
    cnt = 0;
    for (int x : numbers) {
        if (x == candidate) cnt++;
    }
    return cnt > numbers.length/2 ? candidate : -1;
}

数组中只出现一次的两个数字

public int[] FindNumsAppearOnce (int[] nums) {
    int xor = 0;
    for (int x : nums) {
        xor ^= x;
    }
    int lowbit = xor & (-xor);
    int[] res = new int[2];
    for (int x : nums) {
        if ((x & lowbit) == 0) res[0] ^= x;
        else res[1] ^= x;
    }
    Arrays.sort(res);
    return res;
}

缺失的第一个正整数

public int minNumberDisappeared (int[] nums) {  // 原地哈希
    int n = nums.length;
    for (int i = 0; i < n; i++) {  // 小于等于0的非正整数，给它赋值n+1，不进行下一步for循环的逻辑
        if (nums[i] <= 0) nums[i] = n+1;
    }
    for (int x : nums) {  // 每个元素x，给它映射到数组上对应的位置，并赋予负值
        if (Math.abs(x) <= n) nums[Math.abs(x)-1] = -Math.abs(nums[Math.abs(x)-1]);
    }
    for (int i = 0; i < n; i++) {  // 最后判断，找到第一个非负值的元素，说明缺失了
        if (nums[i] > 0) return i+1;
    }
    return n+1;
}

dfs

没有重复项数字的全排列

// [1,2,3] 题目要求字典排序，但这里最后两个排列[3,2,1],[3,1,2]也能通过
// 预期输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 实际输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
public ArrayList<ArrayList<Integer>> permute (int[] num) {  // 这种方法返回的结果不是字典序
    Arrays.sort(num);
    dfs(num, 0);
    return res;
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public void dfs(int[] num, int idx) {  // 数组两两元素交换
    int n = num.length;
    if (idx == n-1) {  // 递归到最后一个元素，添加到结果中
        ArrayList<Integer> t = new ArrayList<>();
        for (int x : num) t.add(x);
        res.add(t);
    }
    for (int i = idx; i < n; i++) {  // 遍历交换元素
        swap(num, i, idx);
        dfs(num, idx + 1);
        swap(num, i, idx);
    }
}
public void swap(int[] num, int i, int j ) {
    int t = num[i];
    num[i] = num[j];
    num[j] = t;
}

public ArrayList<ArrayList<Integer>> permute (int[] num) {  // 可以保证结果字典序
    int n = num.length;
    Arrays.sort(num);
    List<Integer> list = Arrays.asList(new Integer[n]);
    int[] vis = new int[n];
    dfs(0, num, list, vis);
    return res;
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public void dfs(int cnt, int[] num, List<Integer> list, int[] vis) {  // 通过list赋值和记录是否出现进行dfs
    int n = num.length;
    if (cnt == n) {  // 递归到最后一个元素，添加到结果中
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < n; i++) {  // 遍历交换元素
        if (vis[i] == 1) continue;
        list.set(cnt, num[i]);
        vis[i] = 1;
        dfs(cnt + 1, num, list, vis);
        vis[i] = 0;
    }
}

有重复项数字的全排列

public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
    int n = num.length;
    Arrays.sort(num);
    List<Integer> list = Arrays.asList(new Integer[n]);
    int[] vis = new int[n];
    dfs(0, num, list, vis);
    return res;
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public void dfs(int cnt, int[] num, List<Integer> list, int[] vis) {
    int n = num.length;
    if (cnt == n) {  // 递归到最后一个元素，添加到结果中
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < n; i++) {  // 依次加入list中
        if (vis[i] == 1) continue;  // 已放入list
        // 在一次遍历中，对于连续的几个重复数字，我们只考虑将第一个数字进行后续dfs
        if (i > 0 && num[i] == num[i-1] && vis[i-1] == 0) continue;  // 和之前重复，跳过
        list.set(cnt, num[i]);
        vis[i] = 1;
        dfs(cnt + 1, num, list, vis);
        vis[i] = 0;
    }
}

岛屿数量

int res = 0;
public int solve (char[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfs(i, j, grid);
                res++;
            }
        }
    }
    return res;
}
private void dfs(int x, int y, char grid[][]) {
    int dirs[] = new int[]{1, 0, -1, 0, 1};
    grid[x][y] = '0';
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i], ny = y + dirs[i+1];
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (grid[nx][ny] == '0') continue;
        dfs(nx, ny, grid);
    }
}

字符串的排列

括号生成

ArrayList<String> res = new ArrayList<>();
public ArrayList<String> generateParenthesis (int n) {
    dfs(n, n, "");
    return res;
}
public void dfs(int left, int right, String s) {  // left和right分别表示左右括号剩余数量，s是当前构造的字符串
    if (left == 0 && right == 0) {
        res.add(s);
        return;
    }
    if (left > 0) dfs(left-1, right, s+"(");
    if (right > 0 && right > left) dfs(left, right-1, s+")");
}

矩阵最长递增路径

dp

斐波那契数列

public int Fibonacci (int n) {  // 递归写法
    // write code here
    if (n <= 2) return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

public int Fibonacci (int n) {  // 动态规划迭代写法
    // write code here
    int[] f = new int[n+1];
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

跳台阶

public int jumpFloor (int number) {  // 递归，没记忆化可能超时
    if (number < 0) return 0;
    if (number == 0) return 1;
    return jumpFloor(number-1) + jumpFloor(number-2);
}

public int jumpFloor (int number) {
    int[] f = new int[number+2];
    f[1] = 1;
    for (int i = 0; i < number; i++) {
        f[i+2] = f[i+1] + f[i];
    }
    return f[number+1];
}

最小花费爬楼梯

public int minCostClimbingStairs (int[] cost) {
    int n = cost.length;
    // f[i]: 到第i个台阶的最低花费，从0开始，到达顶部是第n个台阶
    int[] f = new int[n+1];
    for (int i = 0; i <= n; i++) {
        int pre = i-1 >= 0 ? f[i-1] : 0;  // 到达前一个台阶的最小花费
        int prepre = i-2 >= 0 ? f[i-2] : 0;  // 到达前两个台阶的最小花费
        f[i] = i < n ? cost[i] : 0;  // 第n个台阶是最顶部，不需要花费
        f[i] += Math.min(pre, prepre);  // 从前一个或者前两个台阶转移过来
    }
    return f[n];
}

最长公共子序列(二)

public String LCS (String s1, String s2) {
    char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
    int n1 = cs1.length, n2 = cs2.length;
    // f[i][j]: cs1[:i-1]和cs2[:j-1]的最长公共子序列长度
    int[][] f = new int[n1+1][n2+1];
    for (int i = 0; i < n1; i++) {
        for (int j=  0; j < n2; j++) {
            f[i+1][j+1] = Math.max(f[i][j+1], f[i+1][j]);
            if (cs1[i] == cs2[j]) {
                f[i+1][j+1] = f[i][j] + 1;
            }
        }
    }
    StringBuilder res = new StringBuilder();
    for (int i = n1-1, j = n2-1; f[i+1][j+1]!=0;) {  // dp回溯找方案
        if (f[i+1][j+1] > f[i][j] && cs1[i] == cs2[j]) {  // 如果先判断和左上角元素关系，那么还需要判断字符是否相等。因为只靠大于不能保证从这里转移过来，有可能从左边或者上边传过来的值也大于左上
            res.append(cs1[i]);
            i--; j--;
        } else {
            if (f[i+1][j+1] == f[i][j+1]) i--;
            else j--;
        }
        // 或者这样写，直接优先判断与左边和上边的关系，如果不是从左边和上边转移过来的，那么一定是从左上转移过来
        // if(f[i+1][j+1] == f[i][j+1]) i--;
        // else if(f[i+1][j+1] == f[i+1][j]) j--;
        // else if(f[i+1][j+1] > f[i][j]){
        //     res.append(cs1[i]);
        //     i--; j--;
        // }
    }
    if (res.length() == 0) return "-1";
    return res.reverse().toString();
}

最长公共子串

public String LCS (String str1, String str2) {
    char[] cs1 = str1.toCharArray(), cs2 = str2.toCharArray();
    int n1 = cs1.length, n2 = cs2.length;
    // f[i][j]: cs1[:i-1]和cs2[:j-1]的最长公共子串长度
    int[][] f = new int[n1+1][n2+1];
    int maxI = 0, maxJ = 0;  // 最长子串长度的索引
    for (int i = 0; i < n1; i++) {
        for (int j=  0; j < n2; j++) {
            if (cs1[i] == cs2[j]) {  // 相等则+1
                f[i+1][j+1] = f[i][j] + 1;
            }
            if (f[i+1][j+1] > f[maxI][maxJ]) {  // 是否更新最长子串索引
                maxI = i+1;
                maxJ = j+1;
            }
        }
    }
    int len = f[maxI][maxJ];
    return str1.substring(maxI-len, maxI);  // 根据最长子串索引和长度，得到子串
}

不同路径的数目(一)

public int uniquePaths (int m, int n) {  // 动态规划
    // f[i][j]: 到达matrix[i][j]位置的路径数目
    int[][] f = new int[m][n];
    f[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            int up = i-1 < 0 ? 0 : f[i-1][j];
            int left = j-1 < 0 ? 0 : f[i][j-1];
            f[i][j] = up + left;
        }
    }
    return f[m-1][n-1];
}

public int uniquePaths (int m, int n) {  // 动态规划，冗余一行写法
    // f[i][j]: 到达matrix[i-1][j-1]位置的路径数目
    int[][] f = new int[m+1][n+1];
    f[0][1] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            f[i+1][j+1] = f[i][j+1] + f[i+1][j];
        }
    }
    return f[m][n];
}

public int uniquePaths (int m, int n) {  // 组合数
    // 向右n-1步，向下m-1步
    // C(n-1, m+n-2) = (m+n-2)! / ((n-1)!*(m-1)!) = (m+n-2)*...*(m) / (n-1)!
    long res = 1;
    for (int i = m, j = 1; j <= n-1; i++, j++) {
        res = res * i / j;
    }
    return (int)res;
}

矩阵的最小路径和

public int minPathSum (int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    // f[i][j]: 到达matrix[i][j]位置的最小路径和
    int[][] f = new int[m][n];
    f[0][0] = matrix[0][0];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            int up = i-1 < 0 ? (int)1e9 : f[i-1][j];
            int left = j-1 < 0 ? (int)1e9 : f[i][j-1];
            f[i][j] = matrix[i][j] + Math.min(up, left);
        }
    }
    return f[m-1][n-1];
}

把数字翻译成字符串

有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。现在给一串数字，返回有多少种可能的译码结果

public int solve (String nums) {
    char[] cs = nums.toCharArray();
    int n = cs.length;
    // f[i+1]: nums[:i]的译码方案数
    int[] f = new int[n+1];
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        if (cs[i] != '0') f[i+1] += f[i];  // 当前字符不为0，则可以作为一个编码
        if (i-1 >= 0) {  // 考虑前两位
            int num = (cs[i-1]-48)*10 + (cs[i]-48);  // 计算前两位组成的数字
            if (num == 0) return 0;  // 如果两位都是0，则无法编码，返回0
            if (10 <= num && num <= 26) f[i+1] += f[i-1];  // 如果数字在10和26之间，则这两位数字也可以作为一个编码
        }
    }
    return f[n];
}

兑换零钱(一)

public int minMoney (int[] arr, int aim) {  // 完全背包
    int n = arr.length;
    // f[i]: 兑换零钱值为i的最少货币数量
    int[] f = new int[aim+1];
    Arrays.fill(f, (int)1e9);
    f[0] = 0;
    for (int i = 0; i < n; i++) {  // 遍历所有货币面值
        for (int j = 0; j <= aim; j++) {  // 遍历所有aim取值
            int pre = j-arr[i] >= 0 ? f[j-arr[i]] : (int)1e9;
            f[j] = Math.min(f[j], pre+1);
        }
    }
    return f[aim] == (int)1e9 ? -1 : f[aim];
}

最长上升子序列(一)（递增）

public int LIS (int[] arr) {  // 动态规划 O(n^2)
    int n = arr.length;
    // f[i]: arr[:i]的最长递增子序列
    if (n == 0) return 0;
    int[] f = new int[n];
    Arrays.fill(f, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) f[i] = Math.max(f[i], f[j]+1);
        }
    }
    return Arrays.stream(f).max().getAsInt();
}

public int LIS (int[] arr) {  // 贪心 + 二分 O(nlogn)
    int n = arr.length;
    // cnt[i]: 长度为i+1的最长上升子序列的最后一个元素
    int[] map = new int[n];
    int cnt = 0;
    for (int x : arr) {
        int l = 0, r = cnt;
        while (l < r) {
            int mid = l + (r-l)/2;
            if (map[mid] >= x) r = mid;
            else l = mid + 1;
        }
        map[l] = x;
        if (l == cnt) cnt++;
        // System.out.println(Arrays.toString(map) + " " + cnt);
    }
    return cnt;
}

最长回文子串

public int getLongestPalindrome (String A) {  // 遍历中间位置
    char[] cs = A.toCharArray();
    int n = cs.length, res = 0;
    for (int i = 0; i < n; i++) {
        int l = i-1, r = i+1, cur = 1;
        while (l >= 0 && r <= n-1) {  // 奇数情况，往两边扩散
            if (cs[l--] == cs[r++]) cur += 2;
            else break;
        }
        res = Math.max(res, cur);
        l = i; r = i+1; cur = 0;
        while (l >= 0 && r <= n-1) {  // 偶数情况，往两边扩散
            if (cs[l--] == cs[r++]) cur += 2;
            else break;
        }
        res = Math.max(res, cur);
    }
    return res;
}

public int getLongestPalindrome (String A) {  // 动态规划
    char[] cs = A.toCharArray();
    int n = cs.length, res = 0;
    int[][] f = new int[n][n];
    for (int i = n-1; i >= 0; i--) {  // 从中间往外遍历，保证f[i+1][j-1]已经计算
        for (int j = i; j < n; j++) {
            if (cs[i] == cs[j]) {
                if (i+1 >= j-1) f[i][j] = j - i + 1;
                else if (f[i+1][j-1] != 0) f[i][j] = f[i+1][j-1] + 2;
                res = Math.max(res, f[i][j]);
            }
        }
    }
    return res;
}

public int getLongestPalindrome (String A) {  // manacher
    char[] cs = A.toCharArray();
    int n = cs.length, res = 0;
    char[] t = new char[n*2+3];  // 改造原始字符串
    t[0] = '@'; t[n*2+2] = '$';
    for (int i = 0; i < n; i++) {
        t[i*2 + 1] = '#';
        t[i*2 + 2] = cs[i];
    }
    t[n*2+1] = '#';
    int[] p = new int[n*2+3];  // 每个位置的回文半径，映射后的回文半径恰好就是原始字符串的回文长度
    int center = 0, right = 0;  // right最右的窗口
    for (int i = 1; i < t.length-1; i++) {
        int mirror = center - (i - center);
        if (right > i) {  // 根据对称性，计算p[i]的初始值
            p[i] = Math.min(p[mirror], right-i);
        }
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) {  // 暴力拓展
            p[i]++;
        }
        if (i + p[i] > right) {  // 更新最右窗口
            right = i + p[i];
            center = i;
        }
    }
    return Arrays.stream(p).max().getAsInt();
}

数字字符串转化成IP地址

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：给出的字符串为"25525522135", 返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)

public ArrayList<String> restoreIpAddresses (String s) {
    dfs(s, 0, 0, "");
    return res;
}
ArrayList<String> res = new ArrayList<>();
// 字符串s，当前的起始位置start，分割次数cnt，形成的目标字符串tg
public void dfs(String s, int start, int cnt, String tg) {  // 递归，由于还要具体的字符串结果，所以这里用dfs比较好（用迭代dp比较适合计算个数）
    char[] cs = s.toCharArray();
    int n = cs.length, cur = 0;
    if (start >= n) return;  // 超出边界
    if (cnt == 3) {  // 最后一段数字
        int num = Integer.valueOf(s.substring(start));
        if (num != 0 && cs[start] == '0') return;  // 有前导0，不添加到res
        if (num <= 255) {  // 小于255则添加到res
            res.add(tg + num);
        }
        return;
    }
    for (int i = start; i < n; i++) {  // 遍历分割位置
        cur = cur*10 + cs[i] - 48;
        if (cur > 255) break;
        dfs(s, i+1, cnt+1, tg + cur + ".");  // 寻找下一个分割位置
        if (cur == 0) break;  // 说明有前导0，则不进行下一次遍历
    }
}

编辑距离(一)

public int editDistance (String str1, String str2) {
    // write code here
    int m = str1.length(), n = str2.length();
    int f[][] = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) f[i][0] = (int)1e9;
    for (int i = 0; i <= n; i++) f[0][i] = (int)1e9;
    f[0][0] = 0;
    for (int i = 0; i < m; i++) {
        char c1 = str1.charAt(i);
        for (int j = 0; j < n; j++) {
            char c2 = str2.charAt(j);
            int add = c1 == c2 ? 0 : 1;
            f[i+1][j+1] = Math.min(f[i][j] + add, Math.min(f[i+1][j] + 1, f[i][j+1] + 1));
        }
    }
    return f[m][n];
}

打家劫舍(一)（不相邻即可）

public int rob (int[] nums) {
    int n = nums.length;
    // f[i]：到nums[i-1]的价值最大值
    int[] f = new int[n+2];
    for (int i = 0; i < n; i++) {
        f[i+2] = Math.max(f[i+1], f[i] + nums[i]);
    }
    return f[n+1];
}

打家劫舍(二)（环形）

public int rob (int[] nums) {
    int n = nums.length;
    return Math.max(rob(nums, 0, n-2), rob(nums, 1, n-1));
}
public int rob (int[] nums, int l, int r) {
    int n = r - l + 1;
    // f[i]：到nums[i-1]的价值最大值
    int[] f = new int[n+2];
    for (int i = 0; i < n; i++) {
        f[i+2] = Math.max(f[i+1], f[i] + nums[l+i]);
    }
    return f[n+1];
}

字符串

字符串变形

这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

public String trans (String s, int n) {
    char[] cs = s.toCharArray();
    StringBuilder res = new StringBuilder(), cur = new StringBuilder();
    for (int i = n-1; i >= 0; i--) {
        char c = Character.isLowerCase(cs[i]) ? Character.toUpperCase(cs[i]) : Character.toLowerCase(cs[i]);  // 切换大小写
        if (c == ' ') {  // 空字符，则添加当前单词到res，并重置
            res.append(cur);
            cur = new StringBuilder();
            res.append(' ');
        } else {  // 更新当前单词
            cur.insert(0, c);
        }
    }
    res.append(cur);  // 加上最后一个单词
    return res.toString();
}

最长公共前缀

public String longestCommonPrefix (String[] strs) {
    int n = strs.length;
    if (n == 0) return "";
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < strs[0].length(); i++) {  // 直接遍历第一个字符串，要求公共，所以只可能出现任意一个字符串以内
        char c = strs[0].charAt(i);
        for (String word : strs) {
            if (i >= word.length() || word.charAt(i) != c) {  // 不匹配直接返回
                return res.toString();
            }
        }
        res.append(c);
    }
    return res.toString();
}

public String longestCommonPrefix (String[] strs) {  // 不用额外空间的写法
    int n = strs.length;
    if (n == 0) return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (String word : strs) {
            if (i >= word.length() || word.charAt(i) != c) {  // 不匹配直接截取返回
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];  // 第一个字符串就是公共字符串
}

验证IP地址

public String solve (String IP) {
    if (IP.contains(":") && isIPv6(IP)) return "IPv6";
    else if (IP.contains(".") && isIPv4(IP)) return "IPv4";
    return "Neither";
}
public boolean isIPv4(String s) {  // 验证IPv4
    if (s.length() == 0 || s.charAt(0) == '.' || s.charAt(s.length()-1) == '.') return false;  // 检查空串和首尾
    String[] words = s.split("\\.");
    for (String word : words) {
        int cur = 0;
        for (char c : word.toCharArray()) {
            if (!Character.isDigit(c)) return false;  // 非数字
            if (c == 48 && cur == 0) return false;  // 前导0
            cur = cur * 10 + (c-48);
        }
        if (cur > 255) return false;  // 大于255
    }
    return true;
}
public boolean isIPv6(String s) {  // 验证IPv6
    if (s.length() == 0 || s.charAt(0) == ':' || s.charAt(s.length()-1) == ':') return false;  // 检查空串和首尾
    String[] words = s.split("\\:");
    for (String word : words) {
        if (word.length() == 0 || word.length() > 4) return false;  // 检查长度
        for (char c : word.toCharArray()) {
            if (!Character.isDigit(c) && !(c >= 'a' && c <= 'f') && !(c >= 'A' && c <= 'F')) return false;   // 检查字符
        }
    }
    return true;
}

大数加法

public String solve (String s, String t) {  // 倒序模拟两个数字相加
    int m = s.length(), n = t.length();
    int idx1 = m-1, idx2 = n-1, add = 0;
    StringBuilder res = new StringBuilder();
    while (idx1 >= 0 || idx2 >= 0 || add > 0) {
        int add1 = idx1 >= 0 ? s.charAt(idx1--)-48 : 0;
        int add2 = idx2 >= 0 ? t.charAt(idx2--)-48 : 0;
        int value = add1 + add2 + add;
        if (value >= 10) {
            value -= 10;
            add = 1;
        }
        else add = 0;
        res.append((char)(value+48));
    }
    return res.reverse().toString();
}

双指针

判断是否为回文字符串

public boolean judge (String str) {
    char[] cs = str.toCharArray();
    int n = cs.length;
    int l = 0, r = n-1;
    while (l < r) {
        if (cs[l++] != cs[r--]) return false;
    }
    return true;
}

合并区间

public ArrayList<Interval> merge (ArrayList<Interval> intervals) {  // 按序合并
    intervals.sort((a, b) -> a.start - b.start);  // 根据start排序
    int n = intervals.size();
    int l = 0, r = 0;
    ArrayList<Interval> res = new ArrayList<>();
    while (l < n) {
        int end = intervals.get(l).end;
        while (r < n && intervals.get(r).start <= end) {  // 找到当前区间的范围（合并这一个区间）
            end = Math.max(end, intervals.get(r).end);
            r++;
        }
        res.add(new Interval(intervals.get(l).start, end));
        l = r;
    }
    return res;
}

public ArrayList<Interval> merge (ArrayList<Interval> intervals) {  // 差分 + 扫描线
    int MX = 2*(int)1e5;
    int[] add = new int[MX], delete = new int[MX];
    for (Interval in : intervals) {  // 分别记录差分的增加和减少数组（不能用一个数组一起表示，这样无法处理这种start和end相等的区间）
        add[in.start]++;
        delete[in.end]--;
    }
    ArrayList<Interval> res = new ArrayList<>();
    int sum = 0;
    Interval cur = new Interval(-1, -1);
    for (int i = 0; i < MX; i++) {  // 遍历所有可能的值
        sum += add[i];
        if (sum > 0 && cur.start == -1) cur.start = i;  // 存在区间，开始记录
        sum += delete[i];
        if (sum == 0 && cur.start != -1) cur.end = i;  // 当前区间结束
        if (cur.start != -1 && cur.end != -1) {  // 合并完一个区间
            res.add(cur);
            cur = new Interval(-1, -1);
        }
    }
    return res;
}

反转字符串

public String solve (String str) {
    return new StringBuilder(str).reverse().toString();
}

最长无重复子数组

public int maxLength (int[] arr) {
    int n = arr.length;
    int l = 0, res = 0;
    HashSet<Integer> set = new HashSet<>();
    for (int r = 0; r < n; r++) {  // 右端点
        while (set.contains(arr[r])) {
            set.remove(arr[l++]);  // 左端点
        }
        set.add(arr[r]);
        res = Math.max(res, r-l+1);
    }
    return res;
}

盛水最多的容器

贪心

主持人调度（二）

结构

LRU

使用LinkedList的写法，这样写法需要遍历list查找，而自己定义Node前后指针可以O(1)进行修改

public class Solution {
    class Node {
        int key, val;
    }
    int capacity;
    HashMap<Integer, Node> map = new HashMap<>();
    LinkedList<Node> list = new LinkedList<>();
    public Solution(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        Node cur = map.get(key);
        if (cur == null) return -1;
        list.remove(cur);
        list.addFirst(cur);
        return cur.val;
    }
    public void set(int key, int value) {
        Node cur = map.get(key);
        if (cur == null) {
            cur = new Node();
            cur.key = key;
            cur.val = value;
            map.put(key, cur);
            if (map.size() > capacity) {
                map.remove(list.getLast().key);
                list.removeLast();
            }
        } else {
            cur.val = value;
            list.remove(cur);
        }
        list.addFirst(cur);
    }
}

public class Solution {  // 也可以不用自定义Node结构了
    int capacity;
    HashMap<Integer, Integer> map = new HashMap<>();
    LinkedList<Integer> list = new LinkedList<>();
    public Solution(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        Integer cur = map.get(key);
        if (cur == null) return -1;
        list.remove((Integer)key);
        list.addFirst((Integer)key);
        return cur;
    }
    public void set(int key, int value) {
        Integer cur = map.get(key);
        if (cur == null) {
            map.put(key, value);
            if (map.size() > capacity) {
                map.remove(list.getLast());
                list.removeLast();
            }
        } else {
            map.put(key, value);
            list.remove((Integer)key);
        }
        list.addFirst((Integer)key);
    }
}

自己实现链表的写法

class Node {
    int key, val;
    Node pre, nxt;
}
int capacity;
Node head = new Node(), tail = new Node();  // 虚拟dummy头尾Node
HashMap<Integer, Node> map = new HashMap<>();
public Solution(int capacity) {
    this.capacity = capacity;
    head.nxt = tail;
    tail.pre = head;
}
private void addFirst(Node cur) {
    cur.pre = head;
    cur.nxt = head.nxt;
    head.nxt.pre = cur;
    head.nxt = cur;
}
private void delete(Node cur) {
    cur.pre.nxt = cur.nxt;
    cur.nxt.pre = cur.pre;
}
public int get(int key) {
    Node cur = map.get(key);
    if (cur == null) return -1;
    delete(cur);
    addFirst(cur);
    return cur.val;
}
public void set(int key, int value) {
    Node cur = map.get(key);
    if (cur == null) {
        cur = new Node();
        cur.key = key;
        cur.val = value;
        map.put(key, cur);
        if (map.size() > capacity) {
            map.remove(tail.pre.key);
            delete(tail.pre);
        }
    }
    else {
        cur.val = value;
        delete(cur);
    }
    addFirst(cur);
}

使用LinkedHashMap自带的LRU

import java.util.LinkedHashMap;

public class Main{
    public static int capacity = 3;
    public static LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(capacity, 0.75f, true);  // 这里需要设置访问顺序true
    public static int get(int key) {
        return map.getOrDefault(key, -1);
    }
    public static void put(int key, int val) {
        map.put(key, val);
        if (map.size() > capacity) {
            Integer oldestKey = map.keySet().iterator().next();  // LinkedHashMap队首才是最久未使用
            map.remove(oldestKey);
        }
    }
    public static void main(String[] args) {
        put(1, 1);
        put(2, 2);
        put(3, 3);
        get(1);
        put(4, 4);
        System.out.println(get(1) + " " + get(2) + " " + get(3) + " " + get(4));
    }
}

LFU

class Node {
    int key, val, freq;
    Node pre, nxt;
}
class NodeList {
    Node head = new Node(), tail = new Node();
    public NodeList() {
        head.nxt = tail;
        tail.pre = head;
    }
    private void addFrist(Node cur) {
        cur.pre = head;
        cur.nxt = head.nxt;
        head.nxt.pre = cur;
        head.nxt = cur;
    }
    private void delete(Node cur) {
        cur.pre.nxt = cur.nxt;
        cur.nxt.pre = cur.pre;
    }
    private void moveToHead(Node cur) {
        delete(cur);
        addFrist(cur);
    }
}
int minFreq = 0, capacity;
HashMap<Integer, Node> map = new HashMap<>();  // 存储key和对应的Node
HashMap<Integer, NodeList> freqMap = new HashMap<>();  // 存储频率和对应Node组成的NodeList
public int get(int key) {
    Node cur = map.get(key);
    if (cur == null) return -1;
    incrFreq(cur);
    return cur.val;
}
public void set(int key, int val) {
    Node cur = map.get(key);
    if (cur == null) {
        if (map.size() == capacity) {
            NodeList list = freqMap.get(minFreq);
            map.remove(list.tail.pre.key);
            list.delete(list.tail.pre);
        }
        cur = new Node();
        cur.key = key; cur.val = val; cur.freq = 1;
        minFreq = 1;
        map.put(key, cur);
        addNode(cur);
    }
    else {
        incrFreq(cur);
        cur.val = val;
    }
}
public void incrFreq(Node cur) {
    NodeList list = freqMap.get(cur.freq);
    list.delete(cur);
    if (list.head.nxt == list.tail) {
        if (cur.freq == minFreq) {
            minFreq++;
        }
    }
    cur.freq++;
    addNode(cur);
}
public void addNode(Node cur) {
    NodeList list = freqMap.getOrDefault(cur.freq, new NodeList());
    list.addFrist(cur);
    freqMap.put(cur.freq, list);
}
public int[] LFU (int[][] operators, int k) {
    // 若opt=1，接下来两个整数x, y，表示set(x, y)
    // 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
    capacity = k;
    ArrayList<Integer> res = new ArrayList<>();
    for (int operator[] : operators) {
        if (operator[0] == 1) {
            int key = operator[1], val = operator[2];
            set(key, val);
        }
        else {
            int key = operator[1];
            res.add(get(key));
        }
    }
    return res.stream().mapToInt(i -> i).toArray();
}

模拟

旋转数组（右移m位）

public int[] solve (int n, int m, int[] a) {
    m %= n;
    reverse(a, 0, n-1);  // 反转整个数组
    reverse(a, 0, m-1);  // 反转数组前m个数
    reverse(a, m, n-1);  // 反转数组剩余的n-m个数
    return a;
}
public void reverse(int a[], int left, int right) {
    while (left < right) {
        int t = a[left];
        a[left] = a[right];
        a[right] = t;
        left++;
        right--;
    }
}

public int[] solve (int n, int m, int[] a) {
    m = m % n;  // 左移m位
    int start = 0, cnt = 0;
    while (cnt < n) {
        int cur = start;
        while (cnt < n) {  // 迭代左移这个环
            int nxt = (cur + n - m) % n;
            // int nxt = (cur + m) % n;  // 右移
            cnt++;
            if (nxt == start) break;
            swap(a, cur, nxt);
            cur = nxt;
        }
        start++;  // 处理下一个环
    }
    return a;
}
private void swap(int a[], int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

顺时针旋转矩阵

其它面试面到的

搜索二维矩阵 leetcode 74

每行中的整数从左到右按非严格递增顺序排列，每行的第一个整数大于前一行的最后一个整数。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m-1;
        while (l < r) {  // 找到第一列中，第一个小于等于target的值（行索引）
            int mid = l + (r-l+1)/2;
            if (matrix[mid][0] <= target) l = mid;
            else r = mid - 1;
        }
        int x = l;
        l = 0; r = n-1;
        while (l < r) {  // 在这个行中，二分查找target（大于等于和小于等于都可以）
            int mid = l + (r-l)/2;
            if (matrix[x][mid] >= target) r = mid;
            else l = mid + 1;
        }
        int y = l;
        System.out.println(matrix[x][y]);
        return matrix[x][y] == target;
    }
}

搜索二维矩阵 II leetcode 240

每行的元素从左到右升序排列，每列的元素从上到下升序排列

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n-1;  // 从右上角出发
        while (x <= m-1 && y >= 0) {
            if (matrix[x][y] > target) {  // 舍弃这一列
                y--;
            }
            else if (matrix[x][y] < target) {  // 舍弃这一行
                x++;
            }
            else return true;
        }
        return false;
    }
}

实现一个LRU过期算法的KV cache, 所有KV过期间隔相同, 满足如下性质:

1. 最多存储n对KV;
2. 如果大于n个, 则随意剔除一个已经过期的KV;
3. 如果没有过期的KV, 则按照LRU的规则剔除一个KV;
4. 查询时如果已经过期, 则返回空;

import java.util.*;

class Solution {  // 使用LinkedList
    class Node {
        int key, val;
        long expireTime;
    }
    int capacity;
    long expireInterval;
    HashMap<Integer, Node> map = new HashMap<>();
    LinkedList<Node> list = new LinkedList<>();
    Deque<Node> dq = new LinkedList<>();
    public Solution(int capacity, long expireInterval) {
        this.capacity = capacity;
        this.expireInterval = expireInterval;
    }
    public int get(int key) {
        Node cur = map.get(key);
        if (cur == null) return -1;
        list.remove(cur);
        list.addFirst(cur);
        return cur.val;
    }
    public void set(int key, int value) {
        Node cur = map.get(key);
        System.out.println(System.currentTimeMillis());
        if (cur == null) {
            cur = new Node();
            cur.key = key;
            cur.val = value;
            cur.expireTime = System.currentTimeMillis() + expireInterval;
            map.put(key, cur);
            if (map.size() > capacity) {
                System.out.println(dq.peek().expireTime + " " + System.currentTimeMillis());
                Node removeNode = dq.peek().expireTime < System.currentTimeMillis() ? dq.peek() : list.getLast();
                dq.remove(removeNode);
                map.remove(removeNode.key);
                list.remove(removeNode);
            }
            dq.offer(cur);
        } else {
            cur.val = value;
            list.remove(cur);
        }
        list.addFirst(cur);
    }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        // Scanner input=new Scanner(System.in);
        // String str=input.next();
        System.out.println("hello world");
        Solution solution = new Solution(3, 1);
        solution.set(1, 1);
        Thread.sleep(10);
        solution.set(2, 2);
        Thread.sleep(10);
        solution.get(1);
        solution.set(3, 3);
        Thread.sleep(10);
        solution.set(4, 4);
        System.out.println(solution.get(1));
        System.out.println(solution.get(2));
        System.out.println(solution.get(3));
        System.out.println(solution.get(4));
    }
}

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int k) {
        ListNode dummy = new ListNode(-1), pre = dummy;
        dummy.next = head;
        ListNode right = head;
        for (int i = 0; i < k; i++) {
            if (right == null) break;
            right = right.next;
        }
        ListNode left = head;
        while (right != null) {
            pre = left;
            left = left.next;
            right = right.next;
        }
        pre.next = left.next;
        return dummy.next;
    }
}

其它

寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {  // O(n) 双指针 
        if (nums1.length > nums2.length) {  // 让nums1表示长度更短的数组
            int[] t = nums1;
            nums1 = nums2;
            nums2 = t;
        }
        int m = nums1.length, n = nums2.length;
        int[] a = new int[m+2], b = new int[n+2];  // 前后加入哨兵
        a[0] = b[0] = Integer.MIN_VALUE;
        a[m+1] = b[n+1] = Integer.MAX_VALUE;
        System.arraycopy(nums1, 0, a, 1, m);
        System.arraycopy(nums2, 0, b, 1, n);
        // 假设两个数组合起来排序后，分为前后两组，分别用第一组和第二组表示，并且我们规定奇数情况下，第一组比第二组数量多1
        int i = 0, j = (m + n + 1)/2;  // 表示a数组的前i个数在第一组，b数组的前j个数在第一组
        while (true) {
            int curMax = Math.max(a[i], b[j]);  // 第一组的最大值
            int nxtMin = Math.min(a[i+1], b[j+1]);  // 第二组的最小值
            if (curMax <= nxtMin) {
            // if (a[i] <= b[j+1] && b[j] <= a[i+1]) {  // 由于a和b数组有序，可以简化判断，同时这样就可以用二分了
                return (m+n)%2 == 0 ? ((double)curMax + (double)nxtMin)/2 : (double)curMax;
            }
            i++;
            j--;
        }
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {  // O(logn) 双指针 + 二分
        if (nums1.length > nums2.length) {  // 让nums1表示长度更短的数组
            int[] t = nums1;
            nums1 = nums2;
            nums2 = t;
        }
        int m = nums1.length, n = nums2.length;
        int[] a = new int[m+2], b = new int[n+2];  // 前后加入哨兵
        a[0] = b[0] = Integer.MIN_VALUE;
        a[m+1] = b[n+1] = Integer.MAX_VALUE;
        System.arraycopy(nums1, 0, a, 1, m);
        System.arraycopy(nums2, 0, b, 1, n);
        // 假设两个数组合起来排序后，分为前后两组，分别用第一组和第二组表示，并且我们规定奇数情况下，第一组比第二组数量多1
        int l = 0, r = m;
        while (l < r) {  // 二分位置i
            int mid = l + (r-l+1)/2;
            int i = mid, j = (m+n+1)/2 - i;  // 表示a数组的前i个数在第一组，b数组的前j个数在第一组
            if (a[i] <= b[j+1]) l = mid;
            else r = mid - 1;
        }
        int i = l, j = (m+n+1)/2 - i;
        int curMax = Math.max(a[i], b[j]);  // 第一组的最大值
        int nxtMin = Math.min(a[i+1], b[j+1]);  // 第二组的最小值
        return (m+n)%2 == 0 ? ((double)curMax + (double)nxtMin)/2 : (double)curMax;
    }
}

N 皇后

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[][] grid = new int[n][n];  // 棋盘
        dfs(grid, 0);
        return res;
    }
    List<List<String>> res = new ArrayList<>();
    public void dfs(int[][] grid, int i) {  // 排列型回溯
        int n = grid.length;
        if (i == n) {  // 所有行遍历结束，结果添加到res
            res.add(toString(grid));
            return;
        }
        for (int j = 0; j < n; j++) {  // 遍历第i行的每一个元素grid[i][j]
            if (check(grid, i, j)) {  // 当前位置可以放入皇后
                grid[i][j] = 1;
                dfs(grid, i+1);  // dfs下一行
                grid[i][j] = 0;
            }
        }
    }
    public boolean check(int[][] grid, int x, int y) {  // O(n)，通过当前位置的8个方向是否存在皇后进行判断
        int n = grid.length;
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        for (int[] dir : dirs) {
            for (int i = 1; i < n; i++) {
                int nx = x + dir[0]*i, ny = y + dir[1]*i;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
                if (grid[nx][ny] == 1) return false;
            }
        }
        return true;
    }
    public List<String> toString(int[][] grid) {  // 棋盘数组转换为String
        List<String> res = new ArrayList<>();
        for (int[] row : grid) {
            String cur = "";
            for (int x : row) cur += x == 1 ? "Q" : ".";
            res.add(cur);
        }
        return res;
    }
}

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[][] grid = new int[n][n];
        // 用这三个数组判断是否冲突，O(1)判断
        // cols[j]表示第j列是否存在皇后，diag1[idx]表示第idx对角线是否存在皇后，diag2表示另一条对角线
        int[] cols = new int[n], diag1 = new int[n*2], diag2 = new int[n*2];
        dfs(grid, 0, cols, diag1, diag2);
        return res;
    }
    List<List<String>> res = new ArrayList<>();
    public void dfs(int[][] grid, int i, int[] cols, int[] diag1, int[] diag2) {  // 排列型回溯
        int n = grid.length;
        if (i == n) {  // 所有行遍历结束，结果添加到res
            res.add(toString(grid));
            return;
        }
        for (int j = 0; j < n; j++) {  // 遍历第i行的每一个元素grid[i][j]
            int diag1Idx = i + j, diag2Idx = i - j + n - 1;
            if (cols[j] == 0 && diag1[diag1Idx] == 0 && diag2[diag2Idx] == 0) {  // 当前位置可以放入皇后
                grid[i][j] = 1;
                cols[j] = 1; diag1[diag1Idx] = 1; diag2[diag2Idx] = 1;
                dfs(grid, i+1, cols, diag1, diag2);
                cols[j] = 0; diag1[diag1Idx] = 0; diag2[diag2Idx] = 0;
                grid[i][j] = 0;
            }
        }
    }
    public List<String> toString(int[][] grid) {  // 棋盘数组转换为String
        List<String> res = new ArrayList<>();
        for (int[] row : grid) {
            String cur = "";
            for (int x : row) cur += x == 1 ? "Q" : ".";
            res.add(cur);
        }
        return res;
    }
}

有序数组中的单一元素：每个元素都会出现两次，唯有一个数只会出现一次

class Solution {
    public int singleNonDuplicate(int[] nums) {  // 二分
        int n = nums.length;
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + (r-l)/2;
            if (mid % 2 == 0) {  // 当前位置是偶数，则下一个位置是奇数，如果当前位置和下一个位置相等，则单一元素在右边，否则在左边
                if (nums[mid] != nums[mid+1]) r = mid;
                else l = mid + 1;
            } else {  // 当前位置是奇数，则上一个位置是偶数，如果当前位置和上一个位置相等，则单一元素在右边，否则在左边
                if (nums[mid] != nums[mid-1]) r = mid;
                else l = mid + 1;
            }
        }
        return nums[l];
    }
}

分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前

public ListNode partition(ListNode head, int x) {
    ListNode dummy1 = new ListNode(-1, head), pre1 = dummy1;  // 小于x的链表哨兵节点和前驱节点
    ListNode dummy2 = new ListNode(-1, head), pre2 = dummy2;  // 大于等于x的链表哨兵节点和前驱节点
    ListNode cur = head;
    while (cur != null) {
        if (cur.val < x) {
            pre1.next = cur;
            pre1 = cur;
        } else {
            pre2.next = cur;
            pre2 = cur;
        }
        cur = cur.next;
    }
    pre2.next = null;  // 将大于等于x的链表尾部置空，否则会出现环状链表，导致死循环
    pre1.next = dummy2.next;  // 连接两个链表
    return dummy1.next;
}

132模式

class Solution {
    public boolean find132pattern(int[] nums) {  // 遍历j解法，维护左边最小值和右边有序记录
        int n = nums.length;
        int leftMin = nums[0];
        TreeMap<Integer, Integer> rightCnt = new TreeMap<>();
        for (int k = 2; k < n; k++) {  // 初始化右边有序记录
            rightCnt.merge(nums[k], 1, (a, b) -> a+b);
        }
        for (int j = 1; j < n-1; j++) {
            Integer right = rightCnt.higherKey(leftMin);  // 获得右边大于左边最小值的最小元素
            if (right != null && leftMin < nums[j] && nums[j] > right) return true;  // 符合132序列
            leftMin = Math.min(leftMin, nums[j]);  // 维护左边最小值
            rightCnt.merge(nums[j+1], 1, (a, b) -> a-b);  // 维护右边有序记录（越来越少）
            if (rightCnt.get(nums[j+1]) == 0) rightCnt.remove(nums[j+1]);
        }
        return false;
    }
}

K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 哨兵节点，前一组的尾节点，当前节点
        ListNode dummy = new ListNode(-1, head), preTail = dummy, cur = head;
        while (cur != null) {
            ListNode t = cur;  // 临时节点
            for (int j = 0; j < k-1 && t != null; j++) {  // 判断长度是否小于k，小于则跳出
                t = t.next;
            }
            if (t == null) break;
            ListNode nxtPreTail = cur, pre = null;  // 下一个前一组的尾节点（也就是这一组的第一个节点），pre是前节点
            for (int j = 0; j < k; j++) {  // 翻转这一组
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            preTail.next = pre;  // 前一组的尾节点next指针指向这一组的最后一个节点
            nxtPreTail.next = cur;  // 这一组的第一个节点next指针指向下一组的第一个节点
            preTail = nxtPreTail;  // 更新前一组的尾节点
        }
        return dummy.next;
    }
}

大数

大数相减

public String substring (String num1, String num2) {
    int sign = 0;
    int compareRes = compare(num1, num2);
    if (compareRes == 0) return "0";
    if (compareRes < 0) {  // num1 < num2，交换num1和num2，并将符号置为负数
        String t = num1;
        num1 = num2;
        num2 = t;
        sign = -1;
    }
    StringBuilder res = new StringBuilder();
    int n1 = num1.length(), n2 = num2.length();
    int idx1 = n1-1, idx2 = n2-1, carry = 0;
    while (idx1 >= 0 || idx2 >= 0) {  // 从低位到高位遍历，计算每一位的结果，并将结果添加到res中
        int cur1 = idx1 >= 0 ? num1.charAt(idx1--)-48 : 0;
        int cur2 = idx2 >= 0 ? num2.charAt(idx2--)-48 : 0;
        int cur = cur1 - cur2 - carry;
        if (cur < 0) {  // 当前位不够减，需要向高位借1
            cur += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        res.append((char)(cur+48));
    }
    int cnt = 0;
    for (int idx = res.length()-1; idx >= 0 && res.charAt(idx) == '0'; idx--) {  // 去除前导0，并计算前导0的个数cnt
        cnt++;
    }
    return (sign == -1 ? "-" : "") + res.reverse().substring(cnt);  // 将res反转，并去除前导0，最后加上符号返回结果
}
public int compare(String num1, String num2) {
    int n1 = num1.length(), n2 = num2.length();
    if (n1 != n2) return n1 > n2 ? 1 : -1;
    for (int i = 0; i < n1; i++) {
        if (num1.charAt(i) > num2.charAt(i)) return 1;
        else if (num1.charAt(i) < num2.charAt(i)) return -1;
    }
    return 0;
}

大数乘法

public String solve (String s, String t) {  // 倒序模拟两个数字相乘
    int m = s.length(), n = t.length();
    String res = "0";
    for (int j = n-1; j >= 0; j--) {  // 遍历字符串t
        StringBuilder line = new StringBuilder();
        int cur2 = t.charAt(j) - 48;
        if (cur2 != 0) {  // 如果当前位不为0，则按位倒序计算
            int carry = 0;
            for (int k = j+1; k < n; k++) line.append("0");  // 根据t的当前位置补0
            for (int i = m-1; i >= 0; i--) {  // 遍历字符串s，计算当前位的结果和进位
                int cur1 = s.charAt(i) - 48;
                int cur = cur1 * cur2 + carry;
                carry = cur / 10;
                cur = cur % 10;
                line.append((char)(cur+48));
            }
            if (carry != 0) line.append((char)(carry+48));  // 如果最后还有进位，则补上去
        } else {  // 如果当前位是0，则结果直接为0
            line.append("0");
        }
        res = add(res, line.reverse().toString());  // 将当前位的相乘结果加到最终结果中去
    }
    return res;
}
public String add (String s, String t) {  // 倒序模拟两个数字相加
    int m = s.length(), n = t.length();
    int idx1 = m-1, idx2 = n-1, add = 0;
    StringBuilder res = new StringBuilder();
    while (idx1 >= 0 || idx2 >= 0 || add > 0) {
        int add1 = idx1 >= 0 ? s.charAt(idx1--)-48 : 0;
        int add2 = idx2 >= 0 ? t.charAt(idx2--)-48 : 0;
        int value = add1 + add2 + add;
        if (value >= 10) {
            value -= 10;
            add = 1;
        }
        else add = 0;
        res.append((char)(value+48));
    }
    return res.reverse().toString();
}

LeetCode LCR

LCR 001. 两数相除

要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’

class Solution {
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;  // 特判溢出
        int sign = (a ^ b) >= 0 ? 1 : -1;  // 判断符号
        long al = Math.abs((long)a), bl = Math.abs((long)b);  // 转换为long类型防止溢出，取绝对值
        int res = 0;
        while (al >= bl) {
            long cur = 1, sum = bl;  // 倍增法，cur表示当前倍数，sum表示当前和
            while (sum <= Integer.MAX_VALUE >> 1 && sum + sum <= al) {
                sum += sum;
                cur += cur;
            }
            al -= sum;
            res += cur;
        }
        return sign * res;
    }
}