01 - 10

03. 数组中重复的数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        for (int n : nums) {
            if (!hashSet.add(n)) return n;
        }
        return -1;
    }
}

04. 二维数组中的查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) {
                --i;
            } else if (matrix[i][j] < target) {
                ++j;
            }
            else return true;
        }
        return false;
    }
}

05. 替换空格

class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        char[] chars = new char[len * 3];
        int j = 0;
        for (int i = 0; i < len; ++i) {
            char c = s.charAt(i);
            if (c == ' ')  {
                chars[j++] = '%';
                chars[j++] = '2';
                chars[j++] = '0';
            } else chars[j++] = c;
        }
        return new String(chars, 0, j);
    }
}

06. 从尾到头打印链表

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode root = head;
        while (root != null) {
            stack.push(root);
            root = root.next;
        }

        int size = stack.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; ++i) {
            ans[i] = stack.pop().val;
        }
        return ans;
    }
}

07. 重建二叉树

递归 & 分治

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; ++i) {
            hashMap.put(inorder[i], i);
        }
        return recur(0, 0, preorder.length - 1); 
    }
    //root为preorder中开始坐标
    //start end 为 inorder中的坐标
    public TreeNode recur (int root, int start, int end) {
        if (start > end) return null;
        //创建节点
        TreeNode node = new TreeNode(preorder[root]);
        //递归
        int idx = hashMap.get(preorder[root]);
        node.left = recur(root + 1, start, idx - 1);
        node.right = recur(root + 1 + idx - start, idx + 1, end);
        return node;
    }
}

09. 用两个栈实现队列

class CQueue {
    Deque<Integer> A;
    Deque<Integer> B;

    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        A.push(value);
    }

    public int deleteHead() {  
        if (!B.isEmpty()) return B.pop();
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()) {
            B.push(A.pop());
        }
        return B.pop();
    }
}

10-I. 斐波那契数列

动态规划

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        int r = 0; int l = 1;
        for (int i = 2; i <= n; ++ i) {
            int tmp = l;
            l = (l + r) % 1000000007;
            r = tmp;
        }
        return l;
    }
}

11 - 20

11. 旋转数组的最小数字

二分法

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (numbers[mid] < numbers[right]) {
                right = mid;
            }
            else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            }
            else {
                right--;
            }
        }
        return numbers[left];
    }
}

12. 矩阵中的路径

DFS

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (dfs(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    public static boolean dfs (char[][] board, int i, int j, String word, int idx) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)) {
            return false;
        }
        if (idx == word.length() - 1) return true;
        board[i][j] = ' ';
        boolean res = dfs(board, i + 1, j, word, idx + 1) || dfs(board, i - 1, j, word, idx + 1) || 
                        dfs(board, i, j + 1, word, idx + 1) || dfs(board, i, j - 1, word, idx + 1);
        board[i][j] = word.charAt(idx);
        return res;
    }
}

13. 机器人的运动范围

DFS

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }

    public static int dfs (int i, int j, int m, int n, int k, boolean[][] visited) {
        if (i >= m || j >= n || visited[i][j] || (sumDigits(i) + sumDigits(j)) > k) {
            return 0;
        }
        visited[i][j] = true;
        return  1 + dfs(i + 1, j, m, n, k,visited) + dfs(i, j + 1, m, n, k,visited);
    }

    public static int sumDigits (int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

14-I. 剪绳子

数学

class Solution {
    public int cuttingRope(int n) {
        // 将绳子 以相等的长度等分为多段 ,得到的乘积最大。
        // 尽可能将绳子以长度 3 等分为多段时,乘积最大。
        // 为使乘积最大,只有长度为 2 和 3 的绳子不应再切分,且 3 比 2 更优
        if (n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if (b == 0) return (int)Math.pow(3, a);
        else if (b == 1) return (int)Math.pow(3, a - 1) * 4;
        else return (int)Math.pow(3, a) * 2;
    }
}

14-II. 剪绳子II

贪心

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        long ans = 1;
        while (n > 4) {
            ans = ans * 3 % 1000000007;
            n -= 3;
        }
        return (int)(ans * n % 1000000007);
    }
}

15. 二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += n & 1;
            n >>>= 1;
        }
        return ans;
    }
}
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

16. 数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        double ans = 1.0;
        //Java 代码中 int32 变量 n∈[−2147483648,2147483647] ,因此当 n = -2147483648 时执行 n = -n会因越界而赋值出错。
        //因此需将值传给long型变量
        long b = (long) n; 

        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b != 0) {
            if ((b & 1) == 1) ans *= x;
            x *= x;
            b >>= 1; 
        }
        return ans;
    }
}

17. 打印从1到最大的n位数

考虑大数问题

class Solution {
    StringBuilder res;
    int count = 0, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder(); // 数字字符串集
        num = new char[n]; // 定义长度为 n 的字符列表
        dfs(0); // 开启全排列递归
        res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
        return res.toString(); // 转化为字符串并返回
    }
    void dfs(int x) {
        if(x == n) { // 终止条件:已固定完所有位
            res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部,使用逗号隔开
            return;
        }
        for(char i : loop) { // 遍历 ‘0‘ - ’9‘
            num[x] = i; // 固定第 x 位为 i
            dfs(x + 1); // 开启固定第 x + 1 位
        }
    }
}

去除多余的'0'

class Solution {
    StringBuilder res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder();
        num = new char[n];
        start = n - 1;
        dfs(0);
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res.append(s + ",");
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

19. 正则表达式匹配🌟

  • dp[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配:
    1. 对于前面两个情况,可以合并成一种情况 dp[i][j] = dp[i-1][j-1]
    2. 对于第三种情况,对于 c* 分为看和不看两种情况
      • 不看:直接砍掉正则串的后面两个, dp[i][j] = dp[i][j-2]
      • 看:正则串不动,主串前移一个,dp[i][j] = dp[i-1][j]

动态规划

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        //dp[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
         for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]; //当p中有*时长度必不小于2
                    if (isEqual(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
                else if (isEqual(s, p, i, j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public static boolean isEqual (String s, String p, int i, int j) {
        if (i == 0) return false;
        if (p.charAt(j - 1) == '.') return true;
        return s.charAt(i - 1) == p.charAt(j - 1); 
    }
}

20. 表示数值的字符串🌟

状态机

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') t = 'd';
            else if (c == '-' || c == '+') t = 's';
            else if (c == 'e' || c == 'E') t = 'e';
            else if (c == ' ' || c == '.') t = c;
            else t = '?';
            if (!states[p].containsKey(t)) return false;
            p = (int) states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

21 - 30

21. 调整数组顺序使奇数位于偶数前面

class Solution {
    public int[] exchange(int[] nums) {
        for (int i = 0, j = 0; j < nums.length; ++j) {
            if (nums[j] % 2 == 0) continue;
            int tmp = nums[i];
            nums[i++] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

22. 链表中倒数第k个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 0; i < k; ++i) {
            if (fast == null) return null;
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

24. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while(curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

25. 合并两个排序的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        ListNode p = ret;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return ret.next;
    }
}

26. 树的子结构

递归

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public static boolean recur (TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

27. 二叉树的镜像

递归

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{push(root);}};

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

28. 对称的二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return recur(root.left, root.right);
    }

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

29. 顺时针打印矩阵

模拟

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int m = matrix.length, n = matrix[0].length;
        int len = m * n, idx = 0;
        int[] ans = new int[len];
        int endi = n - 1, endj = m - 1, start = 0;
        while (start <= endi && start <= endj) {
            for (int i = start; i <= endi; ++i) {
                ans[idx++] = matrix[start][i];
            }
            if (idx == len) break;
            for (int i = start + 1; i <= endj; ++i) {
                ans[idx++] = matrix[i][endi];
            }
            if (idx == len) break;
            for (int i = endi - 1; i >= start; --i) {
                ans[idx++] = matrix[endj][i];
            }
            if (idx == len) break;
            for (int i = endj - 1; i > start; --i) {
                ans[idx++] = matrix[i][start];
            }
            start++ ;
            endi--;
            endj--;
        }
        return ans;
    }
}

30. 包含min函数的栈

class MinStack {
    Stack<Integer> stackA;
    Stack<Integer> stackB;

    /** initialize your data structure here. */
    public MinStack() {
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

    public void push(int x) {
        // 等于也要加入stackB栈中
        if (stackA.empty() || x <= stackB.peek()) {
            stackB.push(x);
        }
        stackA.push(x);
    }

    public void pop() {
        if (stackA.pop().equals(stackB.peek())) {
            stackB.pop();
        }
    }

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

    public int min() {
        return stackB.peek();
    }
}

31 - 40

31. 栈的压入、弹出序列

模拟(贪心)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 使用一个栈模拟
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.empty() && stack.peek() == popped[j]) {
                stack.pop();
                ++j;
            }
        }
        return stack.empty();
    }
}

32-I. 从上到下打印二叉树

class Solution {
    public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                list.add(node.val);
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); ++ i) ans[i] = list.get(i);
        return ans;
    }
}

32-II. 从上到下打印二叉树II

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++ i) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            } 
            list.add(level);
        }
        return list;
    }
}

32-III. 从上到下打印二叉树 III

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            LinkedList<Integer> level = new LinkedList<>();
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++ i) {
                TreeNode node = q.poll();
                if (list.size() % 2 == 1) level.addFirst(node.val);
                else level.addLast(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            list.add(level);
        }
        return list;
    }
}

33. 二叉搜索树的后序遍历序列

递归分治

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur (int[] postorder, int start, int end) {
        if (start >= end) return true;
        int p = start;
        while (postorder[end] > postorder[p]) ++p;
        int q = p;
        while (postorder[end] < postorder[q]) ++q;
        if (end != q) return false;
        else return recur(postorder, start, p - 1) && recur(postorder, p, end - 1);
    }
}

辅助单调栈⭐⭐

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 表示上一个根节点的元素,这里可以把postorder的最后一个元素root看成无穷大节点的左孩子
        int root = Integer.MAX_VALUE;
        // 逆向遍历,就是翻转的先序遍历
        for (int i = postorder.length - 1; i >= 0; --i) {
            // 左子树元素必须要小于递增栈被peek访问的元素,否则就不是二叉搜索树
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                // 数组元素小于单调栈的元素了,表示往左子树走了,记录下上个根节点
                // 找到这个左子树对应的根节点,之前右子树全部弹出,不再记录,因为不可能在往根节点的右子树走了
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}

34. 二叉树中和为某一值的路径

递归

class Solution {
    LinkedList<List<Integer>> list = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return list;
    }

    private void recur (TreeNode node, int tar) {
        if (node == null) return;
        path.add(node.val);
        tar -= node.val;
        if (tar == 0 && node.left == null && node.right == null) {
            list.add(new LinkedList(path));
        }
        recur(node.left, tar);
        recur(node.right, tar);
        path.removeLast();
    }
}

35. 复杂链表的复制

class Solution {
    HashMap<Node, Node> visitedMap = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) return head;

        if (this.visitedMap.containsKey(head)) {
            return this.visitedMap.get(head);
        }

        Node node = new Node(head.val, null, null);
        this.visitedMap.put(head, node);

        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        return node;
    }
}

36. 二叉搜索树与双向链表

递归

class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs (Node node) {
        if (node == null) return;
        dfs(node.left);
        if (pre != null) {
            pre.right = node;
        } else head = node;
        node.left = pre;
        pre = node;
        dfs(node.right);
    }
}

迭代

class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node head = null, pre = null;
        Deque<Node> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null) {
                pre.right = root;
            } else head = root;
            root.left = pre;
            pre = root;
            root = root.right;
        }
        head.left = pre;
        pre.right = head;
        return head;
    }
}

37. 序列化二叉树

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder s = new StringBuilder();
        s.append("[");
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                s.append(node.val + ",");
                q.offer(node.left);
                q.offer(node.right);
            } else {
                s.append("null,");
            }
        }
        s.deleteCharAt(s.length() - 1);
        s.append("]");
        return s.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        Queue<TreeNode> q = new LinkedList<>();
        String[] s = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        q.offer(root);
        int idx = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!s[idx].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(s[idx]));
                q.offer(node.left);
            }
            ++ idx;
            if (!s[idx].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(s[idx]));
                q.offer(node.right);
            }
            ++ idx;
        }
        return root;
    }
}

38. 字符串的排列

回溯

class Solution {
    public String[] permutation(String s) {
        StringBuilder str = new StringBuilder();
        int[] visited = new int[s.length()];
        Set<String> set = new HashSet<>();
        backTrack(s, str, visited, set);
        return set.toArray(new String[set.size()]);
    }

    private static void backTrack (String s, StringBuilder str, int[] visited, Set<String> set) {
        for (int i = 0; i < s.length(); ++ i) {
            if (visited[i] == 1) continue;
            str.append(s.charAt(i));
            visited[i] = 1;
            if (str.length() == s.length()) {
                set.add(str.toString());
            } else {
                backTrack (s, str, visited, set);
            }
            str.deleteCharAt(str.length() - 1);
            visited[i] = 0;
        }
    }
}

K佬

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复,因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换,将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

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

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1; 
        }
        return x;
    }
}

41 - 50

41. 数据流中的中位数

双堆

class MedianFinder {

    Queue<Integer> A;
    Queue<Integer> B;

    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x, y) -> y - x);
    }

    public void addNum(int num) {
        if (A.size() != B.size()) {
            B.add(num);
            A.add(B.poll());
        } else {
            A.add(num);
            B.add(A.poll());
        }
    }

    public double findMedian() {
        if (A.size() == B.size()) return (double)(A.peek() + B.peek()) / 2;
        return (double)B.peek();
    }
}

42. 连续子数组的最大和

动态规划专题最大子序和

44. 数字序列中某一位的数字

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) {
            n -= count;
            digit ++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

45. 把数组排成最小的数

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; ++ i) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));
        StringBuilder ans = new StringBuilder();
        for (String s : strs) {
            ans.append(s);
        }
        return ans.toString();
    }
}

快排

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; ++ i) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, n - 1);
        StringBuilder ans = new StringBuilder();
        for (String s : strs) {
            ans.append(s);
        }
        return ans.toString();
    }

    private void quickSort (String[] strs, int start, int end) {
        if (start >= end) return;
        int i = start, j = end;
        String pivot = strs[i];
        while (i < j) {
            while (i < j && (pivot + strs[j]).compareTo(strs[j] + pivot) <= 0) -- j;
            if (i < j) strs[i] = strs[j];
            while (i < j && (pivot + strs[i]).compareTo(strs[i] + pivot) >= 0) ++ i;
            if (i < j) strs[j] = strs[i];
        }
        strs[i] = pivot;
        quickSort(strs, start, i - 1);
        quickSort(strs, i + 1, end);
    }
}

49. 丑数

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; ++ i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num3, num5));
            if (dp[i] == num2) ++ p2;
            if (dp[i] == num3) ++ p3;
            if (dp[i] == num5) ++ p5;
        }
        return dp[n];
    }
}

51 - 60

56-I. 数组中数字出现的次数

位异或分组

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xorNum = 0;
        for (int num : nums) {
            xorNum ^= num;
        }
        int div = 1;
        while ((div & xorNum) == 0) {
            div <<= 1;
        }
        int[] ans = new int[2];
        for (int num : nums) {
            if ((num & div) == div) {
                ans[0] ^= num; 
            } else {
                ans[1] ^= num;
            }
        }
        return ans;
    }
}

56-II. 数组中数字出现的次数II

有限状态自动机

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}

57. 和为s的两个数字

双指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ++ l;
            } else if (nums[l] + nums[r] > target) {
                -- r;
            } else {
                return new int[]{nums[l], nums[r]};
            }
        }
        return new int[]{};
    }
}

57-II. 和为s的连续正数序列

滑动窗口

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        for (int l = 1, r = 2; l < r;) {
            int tmpSum = (l + r) * (r - l + 1) / 2;
            if (tmpSum < target) ++ r;
            else if (tmpSum > target) ++ l;
            else {
                int[] tmp = new int[r - l + 1];
                for (int i = l; i <= r; ++ i) {
                    tmp[i - l] = i;
                }
                list.add(tmp);
                ++ l;
                ++ r;
            }
        }
        return list.toArray(new int[0][]);
    }
}

60. n个骰子的点数

逆向递推

class Solution {
    public double[] dicesProbability(int n) {
        int[][] dp = new int[12][67];

        for (int i = 1; i <= 6; ++i) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; ++i) {
            for (int j = i; j <= 6 * i; ++j) {
                for (int cur = 1; cur <= 6; ++cur) {
                    if ((j - cur) <= 0) {
                        break;
                    }
                    dp[i][j] += dp[i - 1][j - cur];
                }
            }
        }
        double all = Math.pow(6, n);

        int len = 6 * n + 1 - n; //要去掉前面几个取不到的数
        double[] rate = new double[len];
        for (int i = 0; i < len; ++i) {
            rate[i] = dp[n][i + n] / all;
        }
        return rate;
    }
}

优化空间复杂度

class Solution {
    public double[] dicesProbability(int n) {
        // int[][] dp = new int[12][67];
        int[] dp = new int[67];
        for (int i = 1; i <= 6; ++i) dp[i] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 6 * i; j >= i; --j) {
                dp[j] = 0; //归零很关键
                for (int cur = 1; cur <= 6; ++cur) {
                    //小于i - 1很关键
                    if ((j - cur) < i - 1) break;
                    dp[j] += dp[j - cur];
                }
            }
        }

        double all = Math.pow(6, n);
        int len = 5 * n + 1;
        double[] rate = new double[len];
        for (int i = 0; i < len; ++i) {
            rate[i] = dp[i + n] / all;
        }
        return rate;
    }
}

正向递推

class Solution {
    public double[] dicesProbability(int n) {
        //正向递推
        double[] dp = new double[6];
        Arrays.fill (dp, 1.0 / 6.0);

        for (int i = 2; i <= n; ++i) {
            double[] tmp = new double[i * 5 + 1];
            for (int j = 0; j < dp.length; ++j) {
                for (int k = 0; k < 6; ++k){
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

61 - 70

62. 圆圈中最后剩下的数字

class Solution {
    public int lastRemaining(int n, int m) {
        // 约瑟夫环问题
        // f(n) = (f(n - 1) + m) % i;
        // 最后一轮剩下2个人,所以从2开始反推
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

63. 股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int minPrice = prices[0];
        int ans = 0;

        for (int i = 1; i < prices.length; ++i) {
            minPrice = Math.min(minPrice, prices[i]);
            ans = Math.max(ans, prices[i] - minPrice);
        }
        return ans;
    }
}

68-I. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ans = root;
        while (true) {
            if (ans.val < p.val && ans.val < q.val) ans = ans.right;
            else if (ans.val > p.val && ans.val > q.val) ans = ans.left;
            else break;
        }
        return ans;
    }
}

68-II. 二叉树的最近公共祖先

DFS & 剪枝

class Solution {
    TreeNode ans;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ans= null;
        dfs (root, p, q);
        return ans;
    }

    private boolean dfs (TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || ans != null) return false;
        boolean a = dfs(node.left, p, q);
        boolean b = dfs(node.right, p , q);
        if ((a && b) || (node.val == p.val || node.val == q.val) && (a || b)) {
            ans = node;
        }
        return a || b || node.val == p.val || node.val == q.val;
    }
}

Try and fail, but don't fail to try.