剑指 offer——LeetCode

03. 数组中重复的数字

自己的想法

方法一：标记数组

• 执行用时：1 ms, 在所有 Java 提交中击败了83.99%的用户
• 内存消耗：45.8 MB, 在所有 Java 提交中击败了94.72%的用户

class Solution {
    public int findRepeatNumber(int[] nums) {
        boolean[] is = new boolean[nums.length];
        for (int i : nums) {
            if (is[i]) {
                return i;
            }
            is[i] = true;
        }
        return 0;
    }
}

看题解后

方法二：置换

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：45.9 MB, 在所有 Java 提交中击败了92.22%的用户

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 如果当前数不在它对应的下标，则进行互换
            while (nums[i] != i) {
                // 如果它对应的下标就是该数，则说明该数已经出现过了
                if (nums[nums[i]] == nums[i]) {
                    return nums[i];
                }
                // 进行互换
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }
        return 0;
    }
}

04. 二维数组中的查找

自己的想法

方法一：从上往下找

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：44.2 MB, 在所有 Java 提交中击败了47.22%的用户

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int h = 0, l = 0;
        int n = matrix.length, m = matrix[0].length;
        while (l >= 0 && h < n && l < m) {
            // 相等直接返回
            if (matrix[h][l] == target) {
                return true;
            } else if (target < matrix[h][l]) {
                // 向左走
                l--;
            } else if (l + 1 < m && target >= matrix[h][l + 1]) {
                // 向右走
                l++;
            } else if (h + 1 < n && target >= matrix[h + 1][l]) {
                // 右边无法走往下走
                h++;
            } else {
                // 往左下走
                l--;
                h++;
            }
        }
        return false;
    }
}

看题解后

方法二：从下往上找

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：44.1 MB, 在所有 Java 提交中击败了76.34%的用户

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

05. 替换空格

自己的想法

方法一：使用 API

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.2 MB, 在所有 Java 提交中击败了82.08%的用户

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "+");
    }
}

方法二：字符数组

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.3 MB, 在所有 Java 提交中击败了64.99%的用户

class Solution {
    public String replaceSpace(String s) {
        char[] array = new char[s.length() * 3];
        // 新数组的下标
        int index = 0;
        // 变量字符串的字符
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                array[index++] = '%';
                array[index++] = '2';
                array[index++] = '0';
            } else {
                array[index++] = c;
            }
        }
        return new String(array, 0, index);
    }
}

06. 从尾到头打印链表

自己的想法

方法一：递归

• 执行用时：1 ms, 在所有 Java 提交中击败了72.99%的用户
• 内存消耗：39.6 MB, 在所有 Java 提交中击败了15.04%的用户

class Solution {

    List<Integer> list = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        recursion(head);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public void recursion(ListNode head) {
        if (head == null) {
            return;
        }
        recursion(head.next);
        list.add(head.val);
    }
}

方法二：栈

• 执行用时：1 ms, 在所有 Java 提交中击败了72.99%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了88.66%的用户

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int size = stack.size();
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = stack.pop();

        }
        return result;
    }
}

看题解后

方法三：不使用额外空间

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.1 MB, 在所有 Java 提交中击败了55.26%的用户

class Solution {
    public int[] reversePrint(ListNode head) {
        int length = 0;
        ListNode num = head;
        // 获取链表长度
        while (num != null) {
            length++;
            num = num.next;
        }
        int[] result = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            result[i] = head.val;
            head = head.next;
        }
        return result;
    }
}

07. 重建二叉树

二叉树前序遍历的顺序为：

• 先遍历根节点；
• 随后递归地遍历左子树；
• 最后递归地遍历右子树。

二叉树中序遍历的顺序为：

• 先递归地遍历左子树；
• 随后遍历根节点；
• 最后递归地遍历右子树。

对于任意一颗树而言，前序遍历的形式总是：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是：

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

看题解后

方法一：递归

• 执行用时：2 ms, 在所有 Java 提交中击败了99.23%的用户
• 内存消耗：38.8 MB, 在所有 Java 提交中击败了34.19%的用户

class Solution {

    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 将中序遍历的数组加入集合中，方便查找根节点
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return myTree(preorder, 0, preorder.length - 1, 0);
    }

    public TreeNode myTree(int[] preorder, int preorderLeft, int preorderRight, int inorderLeft) {
        if (preorderLeft > preorderRight) {
            return null;
        }
        // 前序遍历的左边的节点就是根节点
        int preorderValue = preorder[preorderLeft];
        // 获取中序遍历的根节点下标
        int inorderIndex = map.get(preorderValue);
        // 构造根节点
        TreeNode root = new TreeNode(preorderValue);
        // 根据中序遍历得到左子树的长度
        int leftLength = inorderIndex - inorderLeft;
        // 获取左节点
        root.left = myTree(preorder, preorderLeft + 1, preorderLeft + leftLength, inorderLeft);
        // 获取右节点
        root.right = myTree(preorder, preorderLeft + leftLength + 1, preorderRight, inorderIndex + 1);
        return root;
    }
}

代码优化：

class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 将中序遍历的数组加入集合中，方便查找根节点
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.preorder = preorder;
        return myTree(0, 0, preorder.length - 1);
    }

    // root == preorderLeft，left == inorderLeft，right == preorderRight
    public TreeNode myTree(int root, int left, int right) {
        if (left > right) {
            return null;
        }
        // 获取中序遍历的根节点下标
        int inorderIndex = map.get(preorder[root]);
        // 构造根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 获取左节点
        node.left = myTree(root + 1, left, inorderIndex - 1);
        // 获取右节点
        node.right = myTree(inorderIndex - left + root + 1, inorderIndex + 1, right);
        return node;
    }
}

最好理解的代码：

class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    int[] preorder;
    int preorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 将中序遍历的数组加入集合中，方便查找根节点
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.preorder = preorder;
        preorderIndex = 0;
        return myTree(0, preorder.length - 1);
    }

    public TreeNode myTree(int inorderLeft, int inorderRight) {
        if (inorderLeft > inorderRight) {
            return null;
        }
        // 前序遍历的左边的节点就是根节点
        int preorderValue = preorder[preorderIndex++];
        // 获取中序遍历的根节点下标
        int inorderIndex = map.get(preorderValue);
        // 构造根节点
        TreeNode root = new TreeNode(preorderValue);
        // 获取左节点
        root.left = myTree(inorderLeft, inorderIndex - 1);
        // 获取右节点
        root.right = myTree(inorderIndex + 1, inorderRight);
        return root;
    }
}

方法二：迭代

  前序遍历，从根节点 root开始，只要有左子节点，就一直会往左下方走，直到最左下角。 而中序遍历，是从最左下角往上，如果碰到节点有右子节点，则会转向。因此，代码中的 if块是用前序数组一直构建左子树，如果碰到了 inorder[inorderIndex]，表示到了左下角，这时就需要往上走并处理右子树，也就是 while代码块。

• 执行用时：2 ms, 在所有 Java 提交中击败了99.23%的用户
• 内存消耗：38.1 MB, 在所有 Java 提交中击败了96.95%的用户

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        // 定义根节点
        TreeNode root = new TreeNode(preorder[0]);
        // 使用双向队列模拟栈
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        // 记录中序遍历的下标
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            // 获取当前的根节点
            int preorderValue = preorder[i];
            // 查看栈顶元素
            TreeNode node = stack.peek();
            // 判断 preorderValue 是 node 的左节点还是右节点
            // 如果栈顶节点不是当前左叶子节点
            if (node.val != inorder[inorderIndex]) {
                // 构建左子树，直到左叶子节点为止
                node.left = new TreeNode(preorderValue);
                stack.push(node.left);
            } else {
                // 移动
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                // 添加右节点
                node.right = new TreeNode(preorderValue);
                stack.push(node.right);
            }
        }
        return root;
    }
}

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

看题解后

方法一：递归

  利用后序数组从后往前遍历，从右往左构造二叉树

• 执行用时：3 ms, 在所有 Java 提交中击败了67.42%的用户
• 内存消耗：38.3 MB, 在所有 Java 提交中击败了85.57%的用户

class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    int[] postorder;
    int postorderIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.postorder = postorder;
        postorderIndex = postorder.length - 1;
        return myTree(0, postorder.length - 1);
    }

    public TreeNode myTree(int inorderLeft, int inorderRight) {
        if (inorderLeft > inorderRight) {
            return null;
        }
        // 获取根节点的值
        int value = postorder[postorderIndex--];
        // 查找根节点在中序遍历的位置
        int inorderIndex = map.get(value);
        // 构造节点
        TreeNode node = new TreeNode(value);
        // 右子树
        node.right = myTree(inorderIndex + 1, inorderRight);
        // 左子树
        node.left = myTree(inorderLeft, inorderIndex - 1);
        return node;
    }
}

方法二：迭代

• 执行用时：2 ms, 在所有 Java 提交中击败了98.49%的用户
• 内存消耗：37.8 MB, 在所有 Java 提交中击败了99.62%的用户

class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        int inorderIndex = inorder.length - 1;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        // 使用双端队列模拟栈
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        for (int i = postorder.length - 2; i >= 0; i--) {
            // 当前节点值，判断该节点应该存放在哪里
            int value = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                // 不相等则存放在右子树中
                node.right = new TreeNode(value);
                stack.push(node.right);
            } else {
                // 向上回溯
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(value);
                stack.push(node.left);
            }
        }
        return root;
    }
}

根据前序和后序遍历构造二叉树

看题解后

前序遍历为：[根节点, [前序遍历左分支], [前序遍历右分支]]

后序遍历为：[[后序遍历左分支], [后序遍历右分支], 根节点]

方法一：递归

  根节点为 pre[preLeft]，并且它在后序中的位置为 postRight，因此这里我们需要找到能区分左右子树的节点。左子树的根节点为 pre[preLeft+1]，因此只要找到它在后序中的位置就可以分开左右子树。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：37.7 MB, 在所有 Java 提交中击败了92.88%的用户

class Solution {
    int[] pre;
    int[] post;

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.pre = pre;
        this.post = post;
        return helper(0, pre.length - 1, 0, post.length - 1);
    }

    public TreeNode helper(int preLeft, int preRight, int postLeft, int postRight) {
        if (preLeft > preRight || postLeft > postRight) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preLeft]);
        if (preLeft == preRight) {
            return root;
        }
        int index = postLeft;
        while (post[index] != pre[preLeft + 1]) {
            index++;
        }
        // 左子树节点的个数
        int count = index - postLeft;
        root.left = helper(preLeft + 1, preLeft + 1 + count, postLeft, index);
        root.right = helper(preLeft + 2 + count, preRight, index + 1, preRight - 1);
        return root;
    }
}

09. 用两个栈实现队列

自己的想法

方法一：一个入，一个出

class CQueue {
  
    // 用来装入
    Deque<Integer> in;
    // 用来取出
    Deque<Integer> out;

    public CQueue() {
        in = new LinkedList<>();
        out = new LinkedList<>();
    }

    public void appendTail(int value) {
        while (out.size() != 0) {
            in.push(out.pop());
        }
        in.push(value);
    }

    public int deleteHead() {
        while (in.size() != 0) {
            out.push(in.pop());
        }
        return out.size() != 0 ? out.pop() : -1;
    }
}

方法二：只在删除做处理

class CQueue {
    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
  
    public void appendTail(int value) {
        stack1.add(value);
    }
  
    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()) return -1;
            while(!stack1.isEmpty()){
                stack2.add(stack1.pop());
            }
            return stack2.pop();
        }else {
            return stack2.pop();
        }
    }
}

用队列实现栈

看题解后

方法一：两个队列

class MyStack {

    Queue<Integer> in;
    Queue<Integer> out;
    /** Initialize your data structure here. */
    public MyStack() {
        in = new LinkedList<>();
        out = new LinkedList<>();
    }
  
    /** Push element x onto stack. */
    public void push(int x) {
        in.offer(x);
        while(out.size() != 0) {
            in.offer(out.poll());
        }
        while(in.size() != 0) {
            out.offer(in.poll());
        }
    }
  
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return out.poll();
    }
  
    /** Get the top element. */
    public int top() {
        return out.peek();
    }
  
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return out.isEmpty();
    }
}

方法二：一个队列

class MyStack {

    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
  
    /** Push element x onto stack. */
    public void push(int x) {
        // 获取队列的长度
        int size = queue.size();
        queue.offer(x);
        while(size-- != 0) {
            queue.offer(queue.poll());
        }
    }
  
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
  
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
  
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

10- I. 斐波那契数列

自己的想法

方法一：递归（超时）

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

方法二：动态规划

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0, b = 1;
        while (n >= 2) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
            n--;
        }
        return b;
    }
}

10- II. 青蛙跳台阶问题

自己的想法

方法一：动态规划

class Solution {

    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int a = 1, b = 1;
        while (n >= 2) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
            n--;
        }
        return b;
    }
}

11. 旋转数组的最小数字

看题解后

方法一：二分查找

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.4 MB, 在所有 Java 提交中击败了27.24%的用户

class Solution {

    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            // 如果中间的数小于右边的数
            if (numbers[mid] < numbers[right]) {
                right = mid;
            } else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else {
                // 它们的值相同，所以无论 numbers[right] 是不是最小值，都有一个它的「替代品」numbers[mid]，因此我们可以忽略二分查找区间的右端点。
                right--;
            }
        }
        return numbers[left];
    }
}

12. 矩阵中的路径

自己的想法

方法一：DFS

• 执行用时：6 ms, 在所有 Java 提交中击败了65.95%的用户
• 内存消耗：40.6 MB, 在所有 Java 提交中击败了7.57%的用户

class Solution {
    int n;
    int m;

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

    public boolean is(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) {
            return true;
        }
        // 越界、判断字符是否可用或字符不相等
        if (i < 0 || i == n || j < 0 || j == m || board[i][j] != word.charAt(index)) {
            return false;
        }
        board[i][j] = '\0';
        if (is(board, word, i + 1, j, index + 1)
            || is(board, word, i, j + 1, index + 1)
            || is(board, word, i - 1, j, index + 1)
            || is(board, word, i, j - 1, index + 1)) {
                return true;
            }
        board[i][j] = word.charAt(index);
        return false; 
    }
}

13. 机器人的运动范围

自己的想法

方法一：DFS

  从（0，0）出发，只用往右和下走，不用往左和上走。

• 执行用时：1 ms, 在所有 Java 提交中击败了84.01%的用户
• 内存消耗：35.5 MB, 在所有 Java 提交中击败了52.19%的用户

class Solution {

    int m;
    int n;
    boolean[][] is;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        is = new boolean[m][n];
        return dfs(0, 0, k);
    }

    public int dfs(int i, int j, int k) {
        // 不满足要求则结束
        if (i < 0 || i == m || j < 0 || j == n || is[i][j] || is(i, j, k)) {
            return 0;
        }
        is[i][j] = true;
        // 只用向右和向下走
        return 1 + dfs(i + 1, j, k) + dfs(i, j + 1, k);
    }

    // 不满足要求返回true
    public boolean is(int i, int j, int k) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum > k;
    }
}

优化计算行列坐标的数位之和

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.3 MB, 在所有 Java 提交中击败了83.12%的用户

class Solution {

    int m;
    int n;
    int k;
    boolean[][] is;

    public int movingCount(int m, int n, int k) {
        this.k = k;
        this.m = m;
        this.n = n;
        is = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    public int dfs(int i, int j, int si, int sj) {
        // 不满足要求则结束
        if (i == m || j == n || is[i][j] || (si + sj) > k) {
            return 0;
        }
        is[i][j] = true;
        // 只用向右和向下走
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

方法二：BFS

• 执行用时：7 ms, 在所有 Java 提交中击败了13.10%的用户
• 内存消耗：37.6 MB, 在所有 Java 提交中击败了7.30%的用户

class Solution {

    public int movingCount(int m, int n, int k) {
        int count = 0;
        boolean[][] is = new boolean[m][n];
        Deque<int[]> stack = new LinkedList<>();
        stack.push(new int[]{0, 0, 0, 0});
        while (stack.size() != 0) {
            // 取出栈顶元素
            int[] array = stack.pop();
            // 判断是否合法
            if (array[0] == m || array[1] == n || is[array[0]][array[1]] || (array[2] + array[3]) > k) {
                continue;
            }
            is[array[0]][array[1]] = true;
            count++;
            stack.push(new int[]{array[0] + 1, array[1], (array[0] + 1) % 10 != 0 ? array[2] + 1 : array[2] - 8, array[3]});
            stack.push(new int[]{array[0], array[1] + 1, array[2], (array[1] + 1) % 10 != 0 ? array[3] + 1 : array[3] - 8});
        }
        return count;
    }
}

14- I. 剪绳子

看题解后

方法一：动态规划

• 执行用时：1 ms, 在所有 Java 提交中击败了45.32%的用户
• 内存消耗：35.4 MB, 在所有 Java 提交中击败了18.05%的用户

class Solution {

    public int cuttingRope(int n) {
        // 因为最少分为两段
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // 指定长度的最大值
        int[] dp = new int[n + 1];
        // 3 以下的绳子不需要拆分，拆分反而变小
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        // 长度为 i
        for (int i = 4; i <= n; i++) {
            // 拆分的长度，循环一半向上取整即可
            for (int j = 1; j < i / 2 + 1; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[n];
    }
}

方法二：贪心

  将 n 切分为多块。

假如 ni >= 5，拆分出一个3
    3 * (ni - 3) >= ni
         3ni - 9 >= ni
             2ni >= 9  因为 ni 大于 5，所以成立
当ni == 4，拆分为 4 = 2 * 2
因为 2 * 2 * 2 < 3 * 3
所以拆分的线段只有 2 和 3，且 2 的个数最多为两个

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.5 MB, 在所有 Java 提交中击败了10.67%的用户

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return 1 * (n - 1);
        }
        int res = 1;
        if (n % 3 == 1) {
            n -= 4;
            res *= 4;
        } else if (n % 3 == 2) {
            n -= 2;
            res *= 2;
        }
        return (int) (res * Math.pow(3, n / 3));
    }
}

14- II. 剪绳子 II

自己的想法

方法一： 贪心

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.3 MB, 在所有 Java 提交中击败了34.61%的用户

class Solution {
  
    public int cuttingRope(int n) {
        if (n <= 3) {
            return 1 * (n - 1);
        }
        int res = 1;
        if (n % 3 == 1) {
            n -= 4;
            res *= 4;
        } else if (n % 3 == 2) {
            n -= 2;
            res *= 2;
        }
        int count = n / 3;
        long a = 1;
        for (int i = 0; i < count; i++) {
            a = (a * 3) % 1000000007;
        }
        return (int) (res * a % 1000000007);
    }
}

方法二：快速幂

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.3 MB, 在所有 Java 提交中击败了34.61%的用户

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return 1 * (n - 1);
        }
        int res = 1;
        if (n % 3 == 1) {
            n -= 4;
            res *= 4;
        } else if (n % 3 == 2) {
            n -= 2;
            res *= 2;
        }
        return (int) (res * myPow(3, n / 3) % 1000000007);
    }

    public long myPow(long x, int b) {
        long res = 1;
        while (b != 0) {
            // 如果当前位为1，则进行乘
            if ((b & 1) == 1) {
                res = res * x % 1000000007;
            }
            x = x * x % 1000000007;
            b >>= 1;
        }
        return res;
    }
}

15. 二进制中1的个数

自己的想法

方法一：逐位判断

  因为可能是负数，所有需要无符号右移（>>>）。

• 执行用时：1 ms, 在所有 Java 提交中击败了96.63%的用户
• 内存消耗：35.6 MB, 在所有 Java 提交中击败了10.44%的用户

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            // 判断最右比特位是否为 1
            if ((n & 1) == 1) {
                count++;
            }
            n >>>= 1;
        }
        return count;
    }
}

看题解后

代码优化

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

方法二：n & (n−1)

  每次 n&(n-1) 可以消除最右的1。

n 	= 10101000
n-1	= 10100111
n&(n-1)	= 10100000

• 执行用时：1 ms, 在所有 Java 提交中击败了96.63%的用户
• 内存消耗：35.5 MB, 在所有 Java 提交中击败了18.84%的用户

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

16. 数值的整数次方

自己的想法

方法一：暴力破解（超时）

class Solution {
    public double myPow(double x, int n) {
        double result;
        if (n >= 0) {
            result = 1;
            while (n-- != 0) {
                result *= x;
            }
        } else {
            // n 小于 0 时
            result = x;
            n = -n;
            while (--n != 0) {
                result *= x;
            }
            result = 1 / result;
        }
        return result;
    }
}

看题解后

方法二：快速幂（位运算）

  Java 代码中 int32 变量 n∈[−2147483648,2147483647]，因此当 n=−2147483648 时执行 n = -n会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。

• 执行用时：1 ms, 在所有 Java 提交中击败了98.46%的用户
• 内存消耗：37.6 MB, 在所有 Java 提交中击败了62.13%的用户

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long  b = n;
        // 如果这个数为负数则进行转换
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b != 0) {
            // 如果当前位为1，则进行乘
            if ((b & 1) == 1) {
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;  
    }
}

方法三：快速幂（二分）

  二分推导： $x^n = x^{n/2} * x^{n/2} = (x^2)^{n/2}$ ，令 n/2 为整数，则需要分为奇偶两种情况：

当 n 为偶数：$x^n = (x^2)^{n/2}$；

当 n 为奇数：$x^n = (x^2)^{n/2}$，即会多出一项 x；

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.1 MB, 在所有 Java 提交中击败了5.00%的用户

class Solution {
    public double myPow(double x, int n) {
        //当 n = 0 时，返回 1
        if(n == 0){
            return 1;
        }else if(n < 0){
            // 当 n < 0 时，返回 1/ x^(-n), 为了防止越界，所以需要-1
            return 1 / (x * myPow(x, - n - 1));
        }else if(n % 2 == 1){
            // 为避免越界，提取 x
            return x * myPow(x, n - 1);
        }else{
            return myPow(x * x, n / 2);
        }   
    }
}

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

自己的想法

方法一：暴力

• 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
• 内存消耗：46.8 MB, 在所有 Java 提交中击败了27.88%的用户

class Solution {
    public int[] printNumbers(int n) {
        int l = (int)Math.pow(10, n) - 1;
        int[] res = new int[l];
        for (int i = 0; i < l; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

方法二：大数

• 执行用时：8 ms, 在所有 Java 提交中击败了15.98%的用户
• 内存消耗：46.7 MB, 在所有 Java 提交中击败了51.46%的用户

class Solution {
    // 结果集
    int[] res;
    // index 表示结果集的下标，n 表示数的位数
    int index, n;
    // 用于拼接字符串
    char[] num;

    public int[] printNumbers(int n) {
        this.n = n;
        // 计算数的个数
        res = new int[(int) Math.pow(10, n) - 1];
        num = new char[n];
        // 从第一位开始构造
        dfs(0);
        return res;
    }

    void dfs(int x) {
        // 构造完毕，开始生成字符
        if (x == n) {
            int value = Integer.parseInt(String.valueOf(num));
            // 如果不为 0，则添加
            if (value != 0) {
                res[index++] = value;
            }
            return;
        }
        // 全排列
        for (char i = '0'; i <= '9'; i++) {
            num[x] = i;
            dfs(x + 1);
        }
    }
}

18. 删除链表的节点

自己的想法

方法一：

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：37.8 MB, 在所有 Java 提交中击败了64.47%的用户

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 删除头节点
        if (head.val == val) {
            return head.next;
        }
        ListNode node = head;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
                break;
            }
            node = node.next;
        }
        return head;
    }
}

19. 正则表达式匹配

看题解后

方法一：动态规划

• 执行用时：4 ms, 在所有 Java 提交中击败了69.50%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了17.66%的用户

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        // dp[0][0] 代表 s 和 p 均为空字符串，dp[1][1] 代表 s 和 p 的第一个字符（即在 s 和 p 中下标为 0 的字符）
        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++) {
                // p 的第 j 个字符为 *
                if (p.charAt(j - 1) == '*') {
                    // 匹配 s 的第 i 个字符和 p 的第 j-1 个字符
                    if (matches(s, p, i, j - 1)) {
                        // p 中 * 前面的字符在 s 中出现多次或者在 s 中只出现 1 次
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        // p 中 * 前面的在 s 中字符出现 0 次
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    // p 的第 j 个字符不为 *
                    // 匹配 s 的第 i 个字符和 p 的第 j 个字符
                    if (matches(s, p, i, j)) {
                        // 匹配成功，状态转移；匹配不成功，默认是false
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    private boolean matches(String s, String p, int i, int j) {
        // 注意在字符串中的下标变换，0 表示没有字符
        if (i == 0) {
            return false;
        }
        // 如果当前匹配为 . 则通过
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        // 否则判断字符是否相等
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

20. 表示数值的字符串

看题解后

方法一：有限状态自动机

字符类型：空格「 」、数字「 0—9」、正负号「 +− 」、小数点「 . 」 、幂符号「 eE 」。

按照字符串从左到右的顺序，定义以下 9 种状态：（合法的结束状态有 2, 3, 7, 8 ）

0. 开始的空格
1. 幂符号前的正负号
2. 小数点前的数字
3. 小数点、小数点后的数字
4. 当小数点前为空格时，小数点、小数点后的数字
5. 幂符号
6. 幂符号后的正负号
7. 幂符号后的数字
8. 结尾的空格

• 执行用时：7 ms, 在所有 Java 提交中击败了41.02%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了57.39%的用户

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
                new HashMap<Character,Integer>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
                new HashMap<Character,Integer>() {{ put('d', 2); put('.', 4); }},                           // 1.
                new HashMap<Character,Integer>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
                new HashMap<Character,Integer>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
                new HashMap<Character,Integer>() {{ put('d', 3); }},                                        // 4.
                new HashMap<Character,Integer>() {{ put('s', 6); put('d', 7); }},                           // 5.
                new HashMap<Character,Integer>() {{ put('d', 7); }},                                        // 6.
                new HashMap<Character,Integer>() {{ put('d', 7); put(' ', 8); }},                           // 7.
                new HashMap<Character,Integer>() {{ 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. 调整数组顺序使奇数位于偶数前面

自己的想法

方法一：首尾双指针

  首尾两个指针，左边的指针指向奇数，右边的指针指向偶数。移动左指针，当左边指针指向了偶数，则和右边的指针指向的数进行互换，并移动右指针。

• 执行用时：2 ms, 在所有 Java 提交中击败了98.18%的用户
• 内存消耗：46.2 MB, 在所有 Java 提交中击败了75.79%的用户

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 等于偶数则互换，位运算判偶
            if ((nums[left] & 1) == 0) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp; 
                right--;
            } else {
                left++;
            }
        }
        return nums;
    }
}

看题解后

方法二：快慢双指针（能保证数组原顺序）

  快慢两个指针，慢指针指向奇数，快指针指向时偶数。移动快指针，当快指针指向了奇数，则和慢指针指向的数进行互换，并移动慢指针。

• 执行用时：2 ms, 在所有 Java 提交中击败了98.18%的用户
• 内存消耗：46.4 MB, 在所有 Java 提交中击败了51.89%的用户

class Solution {
    public int[] exchange(int[] nums) {
        int low = 0, fast = 0;
        while (fast < nums.length) {
            // 奇数则互换
            if ((nums[fast] & 1) == 1) {
                int tmp = nums[low];
                nums[low] = nums[fast];
                nums[fast] = tmp;
                low++;
            }
            fast++;
        }
        return nums;
    }
}

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

自己的想法

方法一：快慢指针

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.5 MB, 在所有 Java 提交中击败了16.87%的用户

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 快慢指针
        ListNode start = head, end = head;
        // 移动快指针
        while (k-- != 0) {
            end = end.next;
        }
        while (end != null) {
            start = start.next;
            end = end.next;
        }
        return start;
    }
}

24. 反转链表

自己的想法

方法一：使用栈

• 执行用时：1 ms, 在所有 Java 提交中击败了5.78%的用户
• 内存消耗：38 MB, 在所有 Java 提交中击败了82.31%的用户

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        // 先将节点压入栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        ListNode root = new ListNode();
        // 中间节点
        ListNode node = root;
        while (stack.size() != 0) {
            node.next = stack.pop();
            node = node.next;
        }
        // 消除环
        node.next = null;
        return root.next;
    }
}

看题解后

方法二：递归

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了11.01%的用户

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 获取最后的节点
        ListNode node = reverseList(head.next);
        // 将下一个节点指向当前节点
        head.next.next = head;
        // 防止环
        head.next = null;
        return node;
    }
}

方法三：迭代

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.3 MB, 在所有 Java 提交中击败了37.38%的用户

class Solution {
    public ListNode reverseList(ListNode head) {
        // 记录当前节点和前节点
        ListNode node = head;
        ListNode front = null;
        while (node != null) {
            // 取出下一个节点
            ListNode next = node.next;
            // 将当前节点指向前一个节点
            node.next = front;
            // 重定向前节点和当前节点
            front = node;
            node = next;
        }
        return front;
    }
}

25. 合并两个排序的链表

自己的想法

方法一：归并排序

• 执行用时：1 ms, 在所有 Java 提交中击败了99.31%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了28.42%的用户

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 结果集
        ListNode node = new ListNode();
        ListNode root = node;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        // 处理剩下的节点
        node.next = l1 != null ? l1 : l2;
        return root.next;
    }
}

26. 树的子结构

自己的想法

方法一：层次遍历

• 执行用时：4 ms, 在所有 Java 提交中击败了5.96%的用户
• 内存消耗：40.6 MB, 在所有 Java 提交中击败了5.10%的用户

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        // 层次遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(A);
        while (queue.size() != 0) {
            TreeNode node = queue.poll();
            if (node.val == B.val) {
                if (isEques(node, B)) {
                    return true;
                }
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    // 判断两个树是否相等
    public boolean isEques(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        } else if (A == null) {
            return false;
        } else {
            // 两个都不为 null，则判断当前值和其子树
            return A.val == B.val && isEques(A.left, B.left) && isEques(A.right, B.right);
        }
    }
}

看题解后

方法二：先序遍历

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：40.2 MB, 在所有 Java 提交中击败了49.38%的用户

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        // 先序遍历
        return isEquals(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    // 判断两个树是否相等
    public boolean isEquals(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        } else if (A == null) {
            return false;
        } else {
            // 两个都不为 null，则判断当前值和其子树
            return A.val == B.val && isEquals(A.left, B.left) && isEquals(A.right, B.right);
        }
    }
}

27. 二叉树的镜像

看题解后

方法一：递归

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.7 MB, 在所有 Java 提交中击败了79.84%的用户

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

方法二：层次遍历

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.8 MB, 在所有 Java 提交中击败了46.82%的用户

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 交换其左右子节点
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}

28. 对称的二叉树

看题解后

方法一：递归

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.4 MB, 在所有 Java 提交中击败了59.71%的用户

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isEquals(root.left, root.right);
    }
  
    public boolean isEquals(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return true;
        }
        if (A == null || B == null) {
            return false;
        }
        return A.val == B.val && isEquals(A.left, B.right) && isEquals(A.right, B.left);
    }
}

29. 顺时针打印矩阵

自己的想法

方法一：模拟

• 执行用时：3 ms, 在所有 Java 提交中击败了20.79%的用户
• 内存消耗：39.9 MB, 在所有 Java 提交中击败了29.39%的用户

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        // 用来防止越界
        int n = matrix.length, m = matrix[0].length;
        // 计算矩阵中数的个数
        int length = n * m;
        // 结果集
        int[] result = new int[length];
        // 移动的下标
        int i = 0, j = 0;
        // 用来控制移动的方向
        int[][] move = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 控制 move 的下标
        int mv = 0;
        // 记录走过的下标
        boolean[][] is = new boolean[n][m];
        for (int index = 0; index < length; index++) {
            // 存储当前数
            result[index] = matrix[i][j];
            is[i][j] = true;
            // 移动下标
            i += move[mv][0];
            j += move[mv][1];
            if (i < 0 || i == n || j < 0 || j == m || is[i][j]) {
                // 如果下标不合法，则返回
                i -= move[mv][0];
                j -= move[mv][1];
                mv = (mv + 1) % 4;
                // 然后转向
                i += move[mv][0];
                j += move[mv][1];
            }
        }
        return result;
    }
}

方法二：模拟

  使用一个 while 套 4 个 for。

• 执行用时：1 ms, 在所有 Java 提交中击败了97.57%的用户
• 内存消耗：39.7 MB, 在所有 Java 提交中击败了64.01%的用户

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[0];
        }
        // 最大下标
        int n = matrix.length - 1, m = matrix[0].length - 1;
        // 移动的下标，存储下标
        int i = 0, j = 0, index = 0;
        // 结果集
        int[] result = new int[(n + 1) * (m + 1)];
        while (i <= n && j <= m) {
            // 往右走
            for (int z = j; z <= m; z++) {
                result[index++] = matrix[i][z];
            }
            i++;
            // 判断是否越界
            if (i > n) {
                break;
            }
            // 往下走
            for (int z = i; z <= n; z++) {
                result[index++] = matrix[z][m];
            }
            m--;
            if (j > m) {
                break;
            }
            // 往左走
            for (int z = m; z >= j; z--) {
                result[index++] = matrix[n][z];
            }
            n--;
            // 往上走
            for (int z = n; z >= i; z--) {
                result[index++] = matrix[z][j];
            }
            j++;
        }
        return result;
    }
}

30. 包含min函数的栈

看题解后

方法一：

  创建一个栈用于存储最小值，在任意一个时刻，栈内元素的最小值就存储在该栈的栈顶。

• 每次添加元素时，和这个栈顶元素做比较，小于等于则存储。
• 每次弹出元素时，和这个栈顶元素做比较，等于则也将该栈中的元素弹出。

  top() 方法和 peek() 方法作用一样。

• 执行用时：21 ms, 在所有 Java 提交中击败了99.24%的用户
• 内存消耗：40.2 MB, 在所有 Java 提交中击败了79.89%的用户

class MinStack {

    // 维护两个栈一个栈存储元素，一个栈存储较小的数
    Deque<Integer> stack;
    Deque<Integer> min;

    public MinStack() {
        stack = new LinkedList<>();
        min = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (min.size() == 0 || min.peek() >= x) {
            min.push(x);
        }
    }

    public void pop() {
        // Integer 引用类型使用 equals 比较
        if (min.peek().equals(stack.pop())) {
            min.pop();
        }
    }

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

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

31. 栈的压入、弹出序列

看题解后

方法一：模拟栈

• 执行用时：3 ms, 在所有 Java 提交中击败了36.93%的用户
• 内存消耗：38 MB, 在所有 Java 提交中击败了85.18%的用户

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        // 将当前数组的所有的数据入栈
        for (int value : pushed) {
            stack.push(value);
            // 如果栈不为空，则判断和 popped[i] 是否相等
            while (stack.size() != 0 && stack.peek() == popped[i]) {
                // 不相等则弹出
                stack.pop();
                i++;
            }
        }
        // 遍历完，则成立
        return i == pushed.length;
    }
}

方法二：双指针

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.2 MB, 在所有 Java 提交中击败了45.39%的用户

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // i 指向 pushed，j 指向 popped
        int i = 0, j = 0;
        // pushed 数组不会改变，改变的只是下表 i
        for (int num : pushed) {
            // 覆盖值
            pushed[i] = num;
            while (i >= 0 && pushed[i] == popped[j]) {
                j++;
                i--;
            }
            // 如果此时不等于 pop 指针指到的值
            i++;
        }
        return i == 0;
    }
}

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

自己的想法

方法一：层次遍历

• 执行用时：1 ms, 在所有 Java 提交中击败了99.71%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了55.00%的用户

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

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

看题解后

方法一：按层遍历（迭代）

• 执行用时：1 ms, 在所有 Java 提交中击败了94.79%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了61.40%的用户

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

方法二：先序遍历（递归）

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了60.82%的用户

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        bfs(root, 0);
        return res;
    }

    public void bfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        // 创建新的集合
        if (res.size() == level) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(node.val);
        bfs(node.left, level + 1);
        bfs(node.right, level + 1);
    }
}

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

看题解后

方法一：双端队列

• 执行用时：1 ms, 在所有 Java 提交中击败了99.89%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了79.41%的用户

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                // 偶数正常
                if ((lists.size() & 1) == 0) {
                    list.addLast(node.val);
                } else {
                    list.addFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
}

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

• 后序遍历定义：[ 左子树 | 右子树 | 根节点 ]。
• 二叉搜索树定义：左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值。

看题解后

方法一：递归

  最后一个元素一定是根节点，利用二叉搜索树的性质根据根节点划分左右子树。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.9 MB, 在所有 Java 提交中击败了45.51%的用户

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

    boolean recur(int[] postorder, int i, int j) {
        // 越界则为 true
        if (i >= j) {
            return true;
        }
        // postorder[j] 是根
        int p = i;
        // 小于根节点的节点都在左子树
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int m = p;
        // 判断剩下的节点是否都属于右子树
        while (postorder[p] > postorder[j]) {
            p++;
        }
        // 如果不属于，则结束
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

方法二：单调栈**（不会）**

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

方法一：DFS

• 执行用时：2 ms, 在所有 Java 提交中击败了27.56%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了32.34%的用户

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    int target;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.target = target;
        if (root != null) {
            List<Integer> list = new LinkedList<>();
            list.add(root.val);
            dfs(root, list, root.val);
        }
        return result;
    }

    public void dfs(TreeNode node, List<Integer> list, int sum) {
        if (sum == target) {
            // 如果相等，则判断是否为根节点
            if (node.left == null && node.right == null) {
                result.add(new ArrayList<>(list));
            }
        }
        // 遍历左子树
        if (node.left != null) {
            list.add(node.left.val);
            dfs(node.left, list, sum + node.left.val);
            list.remove(list.size() - 1);

        }
        // 遍历右子树
        if (node.right != null) {
            list.add(node.right.val);
            dfs(node.right, list, sum + node.right.val);
            list.remove(list.size() - 1);
        }
    }
}

看题解后

代码优化

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了93.78%的用户

class Solution {
    LinkedList<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return result;
    }

    void recur(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            result.add(new LinkedList<>(path));
        }
        recur(root.left, sum);
        recur(root.right, sum);
        // 回溯
        path.removeLast();
    }
}

35. 复杂链表的复制

看题解后

方法一：拼接+拆分

  构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，然后在通过新链表链接 Random。最后拆分两个链表，题目隐含不能破坏原链表，所以拆分时，需要恢复原链表。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.2 MB, 在所有 Java 提交中击败了45.05%的用户

class Solution {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node node = head;
        // 拼接，复制节点
        while (node != null) {
            // 创建新节点
            Node tmp = new Node(node.val);
            // 链接
            tmp.next = node.next;
            node.next = tmp;
            node = node.next.next;
        }
        // 构建 Random
        node = head;
        while (node != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        // 拆分两个链表
        node = head.next;
        // pre 用于复原原链表，res 存储新链表
        Node pre = head, res = head.next;
        while (node.next != null) {
            // 指向原链表
            pre.next = node.next;
            // 指向新建的链表
            node.next = node.next.next;
            node = node.next;
            pre = pre.next;
        }
        pre.next = null;
        return res;
    }
}

方法二：哈希表

  使用 Map 节点构造，原节点和新节点的 Map 映射。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38 MB, 在所有 Java 提交中击败了66.28%的用户

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node node = head;
        Map<Node, Node> map = new HashMap<>();
        // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while (node != null) {
            map.put(node, new Node(node.val));
            node = node.next;
        }
        node = head;
        // 构建新链表的 next 和 random 指向
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

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

看题解后

方法一：中序遍历

  左指针指向前驱，右指针指向后继。使用 pre 记录前一个节点，head 记录最小的节点。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：37.9 MB, 在所有 Java 提交中击败了32.30%的用户

class Solution {
    // pre 记录前一个节点
    Node pre, head;

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

    void dfs(Node node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        if (pre != null) {
            // 前一个节点的后继指向当前节点
            pre.right = node;
        } else {
            // 如果 pre 为空，则表示该节点最小，则为 head
            head = node;
        }
        // 当前节点指向前一个节点
        node.left = pre;
        // 更换前节点
        pre = node;
        dfs(node.right);

        new Object();
    }
}

37. 序列化二叉树

看题解后

方法一：利用层次遍历

• 执行用时：24 ms, 在所有 Java 提交中击败了60.73%的用户
• 内存消耗：40.1 MB, 在所有 Java 提交中击败了81.28%的用户

class Codec {

    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                // 添加当前值
                res.append(node.val).append(",");
                queue.add(node.left);
                queue.add(node.right);
            } else {
                res.append("null,");
            }
        }
        // 删除最后的逗号
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) {
            return null;
        }
        // 去掉字符串的括号，并按逗号进行拆分
        String[] str = data.substring(1, data.length() - 1).split(",");
        // 生成根节点
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 如果下个不为空，则表示左节点不为空
            if (!str[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.left);
            }
            i++;
            if (!str[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

38. 字符串的排列

自己的想法

方法一：DFS

• 执行用时：6 ms, 在所有 Java 提交中击败了99.10%的用户
• 内存消耗：42.9 MB, 在所有 Java 提交中击败了70.57%的用户

class Solution {
    // 原字符串
    char[] array;
    // 字符串的长度
    int n;
    // 组成的字符串
    char[] c;
    // 记录那些字符使用过
    boolean[] is;
    // 生成的字符串
    List<String> list;

    public String[] permutation(String s) {
        array = s.toCharArray();
        n = array.length;
        // 排序
        Arrays.sort(array);
        // 组成的字符串
        c = new char[n];
        // 记录那些字符使用过
        is = new boolean[n];
        list = new ArrayList<>();
        dfs(0);
        // 生成结果集
        return list.toArray(new String[0]);
    }

    public void dfs(int index) {
        if (index == n) {
            list.add(new String(c));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 当前字符未使用过，或前一个字符和该字符相等，而前一个字符未使用过。
            if (is[i] || (i > 0 && array[i] == array[i - 1] && !is[i - 1])) {
                continue;
            }
            is[i] = true;
            c[index] = array[i];
            // 递归
            dfs(index + 1);
            is[i] = false;
        }
    }
}

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

其他方法：哈希表，排序（数组中点的元素一定为众数）

看题解后

方法一：摩尔投票法

• 执行用时：1 ms, 在所有 Java 提交中击败了99.97%的用户
• 内存消耗：41.8 MB, 在所有 Java 提交中击败了55.74%的用户

class Solution {
    public int majorityElement(int[] nums) {
        // 记录当前数出现的次数
        int count = 1;
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[index]) {
                count++;
            } else {
                // 如果之前的数被清空，则重新初始化
                if (--count == 0) {
                    index = i;
                    count = 1;
                }
            }
        }
        return nums[index];
    }
}

代码简化：

class Solution {
    public int majorityElement(int[] nums) {
        // 众数为 value，票数为 count
        int value = 0, count = 0;
        for (int num : nums) {
            if (count == 0) {
                value = num;
            }
            count += num == value ? 1 : -1;
        }
        return value;
    }
}

方法二：位运算

  在 java 中 int 类型是 32 位的，我们只需要判断所有数字在某一位 1 的个数大于数组长度的一半，那么众数在这个位置肯定就是 1，我们需要遍历 32 次，确定这个众数每个位置是 0 还是 1。

• 执行用时：15 ms, 在所有 Java 提交中击败了22.74%的用户
• 内存消耗：41.5 MB, 在所有 Java 提交中击败了89.89%的用户

class Solution {
    public int majorityElement(int[] nums) {
        int result = 0;
        int length = nums.length;
        // 在 java 中 int 类型是 32 位，我们遍历每一位
        for (int i = 0, bit = 1; i < 32; i++, bit <<= 1) {
            // bitCounts 表示所有数字在 i 位置 1 的个数
            int bitCounts = 0;
            for (int num : nums) {
                //判断数字 num 的第 i 位置是否为 1
                if ((num & bit) == bit) {
                    // 如果是 1，bitCounts 就加1
                    bitCounts++;
                }
                // 如果 bitCounts 大于数组的一半，那么众数这个位置肯定是 1，然后通过 result |= bit 运算
                if (bitCounts > length / 2) {
                    result |= bit;
                    break;
                }
            }
        }
        return result;
    }
}

40. 最小的k个数

看题解后

方法一：快排

  找前 K 大/前 K 小的问题不需要对整个数组进行 O(nlogn) 的排序，直接通过快排切分排好第 K 小的数（下标为 K-1）。

• 执行用时：2 ms, 在所有 Java 提交中击败了99.60%的用户
• 内存消耗：39.4 MB, 在所有 Java 提交中击败了94.82%的用户

class Solution {

    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为 k-1 的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int left, int right, int k) {
        // 每快排切分 1 次，找到排序后下标为 j 的元素
        int j = partition(nums, left, right);
        // 如果 j 恰好等于 k 就返回 j 以及 j 左边所有的数；
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标 j 与 k 的大小关系来决定继续切分左段还是右段。
        return j > k ? quickSearch(nums, left, j - 1, k) : quickSearch(nums, j + 1, right, k);
    }

    // 快排切分，返回下标 j，使得比 nums[j] 小的数都在 j 的左边，比 nums[j] 大的数都在 j 的右边。
    private int partition(int[] nums, int left, int right) {
        int value = nums[left];
        int start = left + 1, end = right;
        // 快排单向扫描
        while (start <= end) {
            if (nums[start] <= value) {
                start++;
            } else {
                int t = nums[end];
                nums[end] = nums[start];
                nums[start] = t;
                end--;
            }
        }
        nums[left] = nums[end];
        nums[end] = value;
        return end;
    }
}

方法二：大根堆(前 K 小) / 小根堆（前 K 大)

  求前 K 小，用一个容量为 K 的大根堆，每次 poll 出最大的数，那堆中保留的就是前 K 小的了。（注意：不是小根堆！小根堆的话需要把全部的元素都入堆，那是 O(nlogn)，就不是 O(nlogk)。

  保持堆的大小为 K，然后遍历数组中的数字，遍历的时候做如下判断：

• 若目前堆的大小小于K，将当前数字放入堆中。
• 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；反之如果当前数字比大根堆堆顶小，先 poll 掉堆顶，再将该数字放入堆中。

  Java 中提供了现成的 PriorityQueue（默认小根堆）。

• 执行用时：14 ms, 在所有 Java 提交中击败了41.11%的用户
• 内存消耗：39.9 MB, 在所有 Java 提交中击败了24.19%的用户

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num : arr) {
            // 若目前堆的大小小于K，将当前数字放入堆中
            if (queue.size() < k) {
                queue.offer(num);
            } else if (num < queue.peek()) {
                // 反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
                queue.poll();
                queue.offer(num);
            }
        }
        // 返回堆中的元素
        int[] res = new int[queue.size()];
        int index = 0;
        for (int num : queue) {
            res[index++] = num;
        }
        return res;
    }
}

方法三：二叉搜索树（BST）

  BST 相对于前两种方法没那么常见，但是也很简单，和大根堆的思路差不多。与前两种方法相比，BST 有一个好处是求得的前 K 大的数字是有序的。

  因为有重复的数字，所以用的是 TreeMap 而不是 TreeSet。TreeMap 的 key 是数字，value 是该数字的个数。我们遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap：

• 若目前 map 中数字个数小于 K，则将 map 中当前数字对应的个数 +1；
• 否则，判断当前数字与 map 中最大的数字的大小关系：若当前数字大于等于 map 中的最大数字，就直接跳过该数字；若当前数字小于 map 中的最大数字，则将 map 中当前数字对应的个数 +1，并将 map 中最大数字对应的个数减 1。
• 执行用时：33 ms, 在所有 Java 提交中击败了10.99%的用户
• 内存消耗：39.4 MB, 在所有 Java 提交中击败了94.54%的用户

class Solution {

    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // TreeMap 的 key 是数字, value 是该数字的个数。
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // count 表示当前 map 总共存了多少个数字。
        int count = 0;
        for (int num : arr) {
            // 遍历数组，若当前 map 中的数字个数小于 k，则 map 中当前数字对应个数 +1
            if (count < k) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                count++;
                continue;
            }
            // 取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
            Map.Entry<Integer, Integer> entry = map.lastEntry();
            // 若当前数字比 map 中最大的数字小，则将当前数字加入 map 中，并将 map 中的最大数字的个数-1。
            if (num < entry.getKey()) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                if (entry.getValue() == 1) {
                    map.pollLastEntry();
                } else {
                    map.put(entry.getKey(), entry.getValue() - 1);
                }
            }
        }
        // 最后返回 map 中的元素
        int[] res = new int[k];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 个数
            int c = entry.getValue();
            while (c-- > 0) {
                res[index++] = entry.getKey();
            }
        }
        return res;
    }
}

优先队列（Priority Queue）

  队列中每个元素都有一个优先级，出队的时候，优先级最高的先出。

无序数组实现方式：

• 入队：放在数组末尾O(1)。
• 出队：找最大值并移除，然后移动数组后半部分的数O(n)。

有序数组实现方式：

• 入队：插入到合适的位置，然后移动数组后半部分的数O(n)。
• 出队：删除数组最末尾元素O(1)。

二叉堆实现方式：

  二叉堆是完全二叉树，除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对。特性：

• 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个节点的左子树和右子树都是一个二叉堆。
• 任意节点的值都大于等于其子节点的值——大顶堆。
• 任意节点的值都小于等于其子节点的值——小顶堆（Priority Queue）。

  由于二叉堆是二叉树的扩展，所以二叉堆是由数组表示：

• 根节点存储在 a[0]，然后依次按层次顺序存储。
• 查找子节点：左子节点( 2 * i + 1)，右子节点( 2 * i +2 )。
• 查找父节点 ：( i - 1 ) / 2。

  元素入队：

• 待插入元素放在最后。
• 上浮：不符合堆规则的点与父节点交换，直到符合规则为止。
• 复杂度O(log N)。

  元素出队：

• 将根出队，最后一个点换到根。
• 下浮：不符合堆规则的点与子节点中较大的交换，直到符合规则为止。
• 复杂度O(log N)。

数组中的第K个最大元素

自己的想法

方法一：小根堆（前 K 大)

  使用小根堆存储前 K 大的数。

• 执行用时：5 ms, 在所有 Java 提交中击败了54.34%的用户
• 内存消耗：38.8 MB, 在所有 Java 提交中击败了43.06%的用户

class Solution {
    public int findKthLargest(int[] arr, int k) {
        // 默认是小根堆
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : arr) {
            // 若目前堆的大小小于K，将当前数字放入堆中
            if (queue.size() < k) {
                queue.offer(num);
            } else if (num > queue.peek()) {
                // 反之如果当前数字比大根堆堆顶大，先 poll 掉堆顶，再将该数字放入堆中。
                queue.poll();
                queue.offer(num);
            }
        }
        return queue.peek();
    }
}

方法二：快排

  利用快排找到第 k 个最大元素，数组左边的数都大于 k，右边的数都小于 k。

• 执行用时：1 ms, 在所有 Java 提交中击败了99.21%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了69.98%的用户

class Solution {
    public int findKthLargest(int[] arr, int k) {
        return sort(arr, 0, arr.length - 1, k - 1);
    }

    // 按降序排序
    public int sort(int[] arr, int left, int right, int k) {
        int mid =  partition(arr, left, right);
        if (mid == k) {
            return arr[mid];
        }
        return mid > k ? sort(arr, left, mid - 1, k) : sort(arr, mid + 1, right, k);
    }

    public int partition(int[] arr, int left, int right) {
        int value = arr[left];
        int start = left + 1, end = right;
        while (start <= end) {
            if (arr[start] >= value) {
                start++;
            } else {
                int tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
                end--;
            }
        }
        arr[left] = arr[end];
        arr[end] = value;
        return end;
    }
}

41. 数据流中的中位数

看题解后

方法一：优先队列

  维护两个堆，一个小顶堆，一个大顶堆。

• 小顶堆维护较大的数，这样 peek() 出来的都是最小值。
• 大顶堆维护较小的数，这样 peek() 出来的都是最大值。

注意：

        int a = 5;
        System.out.println(a / 3);// 1
        System.out.println(a / 3.0);// 1.6666666666666667

• 执行用时：85 ms, 在所有 Java 提交中击败了55.33%的用户
• 内存消耗：49.8 MB, 在所有 Java 提交中击败了17.73%的用户

class MedianFinder {

    // 定义两个优先队列，一个小顶堆，一个大顶堆
    PriorityQueue<Integer> a;
    PriorityQueue<Integer> b;

    public MedianFinder() {
        // 存储较大的数
        a = new PriorityQueue<>();
        // 存储较小的数
        b = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (a.size() != b.size()) {
            // 对于一个新元素，将最小的给 b
            a.offer(num);
            // 最小的给 b
            b.offer(a.poll());
        } else {
            // 对于一个新元素，将最大的给 a
            b.offer(num);
            // 将最大的给 a
            a.offer(b.poll());
        }
    }

    public double findMedian() {
        return a.size() != b.size() ? a.peek() : (a.peek() + b.peek()) / 2.0;
    }
}

42. 连续子数组的最大和

看题解后

方法一：动态规划

• 执行用时：1 ms, 在所有 Java 提交中击败了98.49%的用户
• 内存消耗：44.9 MB, 在所有 Java 提交中击败了58.34%的用户

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE, max = 0;
        for (int num : nums) {
            // 对于每个数都有选和不选两种
            max = Math.max(max + num, num);
            result = Math.max(result, max);
        }
        return result;
    }
}

代码优化：减少一个变量。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 如果之前的数和小于 0，则不选
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

43. 1～n 整数中 1 出现的次数

看题解后

方法一：

  根据 cur 的值，分为三种情况

• 当 cur=0 时：此位 1 的出现次数只由高位 high 决定，计算公式为：high * digit。

  如下图所示，以 n = 2304 为例，求 digit=10 （即十位）的 1 出现次数。

     2  3   0  4
     千位和百位可以选00 01 02....22  十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 中排列
     当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
     但是2301不应该算进来，这个1是 单独  出现在个位的（而11，121,111这种可以被算多次）
     即 23*10

• 当 cur=1 时：此位 1 的出现次数由高位 high 和低位 low 决定，计算公式为：high * digit + low + 1。

  如下图所示，以 n = 2314 为例，求 digit=10 （即十位）的 1 出现次数。

   2  3  1  4
   千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
   当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
   即 23 *10 + 4 +1

• 当 cur = 2, 3, ⋯,9 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：(high + 1) * digit。

  如下图所示，以 n = 2324 为例，求 digit=10 （即十位）的 1 出现次数。

   2  3  2  4
   千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
   当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
   即 23 *10 + 10

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.2 MB, 在所有 Java 提交中击败了50.38%的用户

class Solution {
    public int countDigitOne(int n) {
        // 1 表示当前是个位
        int digit = 1, res = 0;
        // high 高位，cur 当前数，low 低位
        int high = n / 10, cur = n % 10, low = 0;
        while (high != 0 || cur != 0) {
            // 如果个位是 0
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }
            // 将 cur 加入 low ，组成下轮 low
            low += cur * digit;
            // 下轮 cur 是本轮 high 的最低位
            cur = high % 10;
            // 将本轮 high 最低位删除，得到下轮 high
            high /= 10;
            // 位因子每轮 × 10
            digit *= 10;
        }
        return res;
    }
}

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

看题解后

方法一：

所求数位 ① 在某个 digitdigit 位数中； ② 为从数字 startstart 开始的第 nn 个数位。