03. 数组中重复的数字

自己的想法

方法一:标记数组

  • 执行用时:1 ms, 在所有 Java 提交中击败了83.99%的用户
  • 内存消耗:45.8 MB, 在所有 Java 提交中击败了94.72%的用户
 1class Solution {
 2    public int findRepeatNumber(int[] nums) {
 3        boolean[] is = new boolean[nums.length];
 4        for (int i : nums) {
 5            if (is[i]) {
 6                return i;
 7            }
 8            is[i] = true;
 9        }
10        return 0;
11    }
12}

看题解后

方法二:置换

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:45.9 MB, 在所有 Java 提交中击败了92.22%的用户
 1class Solution {
 2    public int findRepeatNumber(int[] nums) {
 3        for (int i = 0; i < nums.length; i++) {
 4            // 如果当前数不在它对应的下标,则进行互换
 5            while (nums[i] != i) {
 6                // 如果它对应的下标就是该数,则说明该数已经出现过了
 7                if (nums[nums[i]] == nums[i]) {
 8                    return nums[i];
 9                }
10                // 进行互换
11                int tmp = nums[i];
12                nums[i] = nums[tmp];
13                nums[tmp] = tmp;
14            }
15        }
16        return 0;
17    }
18}

04. 二维数组中的查找

自己的想法

方法一:从上往下找

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:44.2 MB, 在所有 Java 提交中击败了47.22%的用户
 1class Solution {
 2    public boolean findNumberIn2DArray(int[][] matrix, int target) {
 3        if (matrix.length == 0) {
 4            return false;
 5        }
 6        int h = 0, l = 0;
 7        int n = matrix.length, m = matrix[0].length;
 8        while (l >= 0 && h < n && l < m) {
 9            // 相等直接返回
10            if (matrix[h][l] == target) {
11                return true;
12            } else if (target < matrix[h][l]) {
13                // 向左走
14                l--;
15            } else if (l + 1 < m && target >= matrix[h][l + 1]) {
16                // 向右走
17                l++;
18            } else if (h + 1 < n && target >= matrix[h + 1][l]) {
19                // 右边无法走往下走
20                h++;
21            } else {
22                // 往左下走
23                l--;
24                h++;
25            }
26        }
27        return false;
28    }
29}

看题解后

方法二:从下往上找

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:44.1 MB, 在所有 Java 提交中击败了76.34%的用户
 1class Solution {
 2    public boolean findNumberIn2DArray(int[][] matrix, int target) {
 3        if (matrix.length == 0) {
 4            return false;
 5        }
 6        int i = matrix.length - 1, j = 0, m = matrix[0].length;
 7        while (i >= 0 && j < m) {
 8            if (target > matrix[i][j]) {
 9                // 往右走
10                j++;
11            } else if (target < matrix[i][j]) {
12                // 往上走
13                i--;
14            } else {
15                return true;
16            }
17        }
18        return false;
19    }
20}

05. 替换空格

自己的想法

方法一:使用 API

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.2 MB, 在所有 Java 提交中击败了82.08%的用户
1class Solution {
2    public String replaceSpace(String s) {
3        return s.replace(" ", "+");
4    }
5}

方法二:字符数组

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.3 MB, 在所有 Java 提交中击败了64.99%的用户
 1class Solution {
 2    public String replaceSpace(String s) {
 3        char[] array = new char[s.length() * 3];
 4        // 新数组的下标
 5        int index = 0;
 6        // 变量字符串的字符
 7        for (char c : s.toCharArray()) {
 8            if (c == ' ') {
 9                array[index++] = '%';
10                array[index++] = '2';
11                array[index++] = '0';
12            } else {
13                array[index++] = c;
14            }
15        }
16        return new String(array, 0, index);
17    }
18}

06. 从尾到头打印链表

自己的想法

方法一:递归

  • 执行用时:1 ms, 在所有 Java 提交中击败了72.99%的用户
  • 内存消耗:39.6 MB, 在所有 Java 提交中击败了15.04%的用户
 1class Solution {
 2
 3    List<Integer> list = new ArrayList<>();
 4
 5    public int[] reversePrint(ListNode head) {
 6        recursion(head);
 7        int[] result = new int[list.size()];
 8        for (int i = 0; i < list.size(); i++) {
 9            result[i] = list.get(i);
10        }
11        return result;
12    }
13
14    public void recursion(ListNode head) {
15        if (head == null) {
16            return;
17        }
18        recursion(head.next);
19        list.add(head.val);
20    }
21}

方法二:栈

  • 执行用时:1 ms, 在所有 Java 提交中击败了72.99%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了88.66%的用户
 1class Solution {
 2    public int[] reversePrint(ListNode head) {
 3        Deque<Integer> stack = new LinkedList<>();
 4        while (head != null) {
 5            stack.push(head.val);
 6            head = head.next;
 7        }
 8        int size = stack.size();
 9        int[] result = new int[size];
10        for (int i = 0; i < size; i++) {
11            result[i] = stack.pop();
12
13        }
14        return result;
15    }
16}

看题解后

方法三:不使用额外空间

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:39.1 MB, 在所有 Java 提交中击败了55.26%的用户
 1class Solution {
 2    public int[] reversePrint(ListNode head) {
 3        int length = 0;
 4        ListNode num = head;
 5        // 获取链表长度
 6        while (num != null) {
 7            length++;
 8            num = num.next;
 9        }
10        int[] result = new int[length];
11        for (int i = length - 1; i >= 0; i--) {
12            result[i] = head.val;
13            head = head.next;
14        }
15        return result;
16    }
17}

07. 重建二叉树

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

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

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

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

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

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

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

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

看题解后

方法一:递归

  • 执行用时:2 ms, 在所有 Java 提交中击败了99.23%的用户
  • 内存消耗:38.8 MB, 在所有 Java 提交中击败了34.19%的用户
 1class Solution {
 2
 3    Map<Integer, Integer> map = new HashMap<>();
 4
 5    public TreeNode buildTree(int[] preorder, int[] inorder) {
 6        // 将中序遍历的数组加入集合中,方便查找根节点
 7        for (int i = 0; i < inorder.length; i++) {
 8            map.put(inorder[i], i);
 9        }
10        return myTree(preorder, 0, preorder.length - 1, 0);
11    }
12
13    public TreeNode myTree(int[] preorder, int preorderLeft, int preorderRight, int inorderLeft) {
14        if (preorderLeft > preorderRight) {
15            return null;
16        }
17        // 前序遍历的左边的节点就是根节点
18        int preorderValue = preorder[preorderLeft];
19        // 获取中序遍历的根节点下标
20        int inorderIndex = map.get(preorderValue);
21        // 构造根节点
22        TreeNode root = new TreeNode(preorderValue);
23        // 根据中序遍历得到左子树的长度
24        int leftLength = inorderIndex - inorderLeft;
25        // 获取左节点
26        root.left = myTree(preorder, preorderLeft + 1, preorderLeft + leftLength, inorderLeft);
27        // 获取右节点
28        root.right = myTree(preorder, preorderLeft + leftLength + 1, preorderRight, inorderIndex + 1);
29        return root;
30    }
31}

代码优化:

 1class Solution {
 2
 3    Map<Integer, Integer> map = new HashMap<>();
 4    int[] preorder;
 5
 6    public TreeNode buildTree(int[] preorder, int[] inorder) {
 7        // 将中序遍历的数组加入集合中,方便查找根节点
 8        for (int i = 0; i < inorder.length; i++) {
 9            map.put(inorder[i], i);
10        }
11        this.preorder = preorder;
12        return myTree(0, 0, preorder.length - 1);
13    }
14
15    // root == preorderLeft,left == inorderLeft,right == preorderRight
16    public TreeNode myTree(int root, int left, int right) {
17        if (left > right) {
18            return null;
19        }
20        // 获取中序遍历的根节点下标
21        int inorderIndex = map.get(preorder[root]);
22        // 构造根节点
23        TreeNode node = new TreeNode(preorder[root]);
24        // 获取左节点
25        node.left = myTree(root + 1, left, inorderIndex - 1);
26        // 获取右节点
27        node.right = myTree(inorderIndex - left + root + 1, inorderIndex + 1, right);
28        return node;
29    }
30}

最好理解的代码:

 1class Solution {
 2
 3    Map<Integer, Integer> map = new HashMap<>();
 4    int[] preorder;
 5    int preorderIndex;
 6
 7    public TreeNode buildTree(int[] preorder, int[] inorder) {
 8        // 将中序遍历的数组加入集合中,方便查找根节点
 9        for (int i = 0; i < inorder.length; i++) {
10            map.put(inorder[i], i);
11        }
12        this.preorder = preorder;
13        preorderIndex = 0;
14        return myTree(0, preorder.length - 1);
15    }
16
17    public TreeNode myTree(int inorderLeft, int inorderRight) {
18        if (inorderLeft > inorderRight) {
19            return null;
20        }
21        // 前序遍历的左边的节点就是根节点
22        int preorderValue = preorder[preorderIndex++];
23        // 获取中序遍历的根节点下标
24        int inorderIndex = map.get(preorderValue);
25        // 构造根节点
26        TreeNode root = new TreeNode(preorderValue);
27        // 获取左节点
28        root.left = myTree(inorderLeft, inorderIndex - 1);
29        // 获取右节点
30        root.right = myTree(inorderIndex + 1, inorderRight);
31        return root;
32    }
33}

方法二:迭代

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了99.23%的用户
  • 内存消耗:38.1 MB, 在所有 Java 提交中击败了96.95%的用户
 1class Solution {
 2
 3    public TreeNode buildTree(int[] preorder, int[] inorder) {
 4        if (preorder == null || preorder.length == 0) {
 5            return null;
 6        }
 7        // 定义根节点
 8        TreeNode root = new TreeNode(preorder[0]);
 9        // 使用双向队列模拟栈
10        Deque<TreeNode> stack = new LinkedList<>();
11        stack.push(root);
12        // 记录中序遍历的下标
13        int inorderIndex = 0;
14        for (int i = 1; i < preorder.length; i++) {
15            // 获取当前的根节点
16            int preorderValue = preorder[i];
17            // 查看栈顶元素
18            TreeNode node = stack.peek();
19            // 判断 preorderValue 是 node 的左节点还是右节点
20            // 如果栈顶节点不是当前左叶子节点
21            if (node.val != inorder[inorderIndex]) {
22                // 构建左子树,直到左叶子节点为止
23                node.left = new TreeNode(preorderValue);
24                stack.push(node.left);
25            } else {
26                // 移动
27                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
28                    node = stack.pop();
29                    inorderIndex++;
30                }
31                // 添加右节点
32                node.right = new TreeNode(preorderValue);
33                stack.push(node.right);
34            }
35        }
36        return root;
37    }
38}
从中序与后序遍历序列构造二叉树

看题解后

方法一:递归

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

  • 执行用时:3 ms, 在所有 Java 提交中击败了67.42%的用户
  • 内存消耗:38.3 MB, 在所有 Java 提交中击败了85.57%的用户
 1class Solution {
 2
 3    Map<Integer, Integer> map = new HashMap<>();
 4    int[] postorder;
 5    int postorderIndex;
 6
 7    public TreeNode buildTree(int[] inorder, int[] postorder) {
 8        for (int i = 0; i < inorder.length; i++) {
 9            map.put(inorder[i], i);
10        }
11        this.postorder = postorder;
12        postorderIndex = postorder.length - 1;
13        return myTree(0, postorder.length - 1);
14    }
15
16    public TreeNode myTree(int inorderLeft, int inorderRight) {
17        if (inorderLeft > inorderRight) {
18            return null;
19        }
20        // 获取根节点的值
21        int value = postorder[postorderIndex--];
22        // 查找根节点在中序遍历的位置
23        int inorderIndex = map.get(value);
24        // 构造节点
25        TreeNode node = new TreeNode(value);
26        // 右子树
27        node.right = myTree(inorderIndex + 1, inorderRight);
28        // 左子树
29        node.left = myTree(inorderLeft, inorderIndex - 1);
30        return node;
31    }
32}

方法二:迭代

  • 执行用时:2 ms, 在所有 Java 提交中击败了98.49%的用户
  • 内存消耗:37.8 MB, 在所有 Java 提交中击败了99.62%的用户
 1class Solution {
 2
 3    public TreeNode buildTree(int[] inorder, int[] postorder) {
 4        if (postorder == null || postorder.length == 0) {
 5            return null;
 6        }
 7        int inorderIndex = inorder.length - 1;
 8        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
 9        // 使用双端队列模拟栈
10        Deque<TreeNode> stack = new LinkedList<>();
11        stack.push(root);
12        for (int i = postorder.length - 2; i >= 0; i--) {
13            // 当前节点值,判断该节点应该存放在哪里
14            int value = postorder[i];
15            TreeNode node = stack.peek();
16            if (node.val != inorder[inorderIndex]) {
17                // 不相等则存放在右子树中
18                node.right = new TreeNode(value);
19                stack.push(node.right);
20            } else {
21                // 向上回溯
22                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
23                    node = stack.pop();
24                    inorderIndex--;
25                }
26                node.left = new TreeNode(value);
27                stack.push(node.left);
28            }
29        }
30        return root;
31    }
32}
根据前序和后序遍历构造二叉树

看题解后

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

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

方法一:递归

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

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:37.7 MB, 在所有 Java 提交中击败了92.88%的用户
 1class Solution {
 2    int[] pre;
 3    int[] post;
 4
 5    public TreeNode constructFromPrePost(int[] pre, int[] post) {
 6        this.pre = pre;
 7        this.post = post;
 8        return helper(0, pre.length - 1, 0, post.length - 1);
 9    }
10
11    public TreeNode helper(int preLeft, int preRight, int postLeft, int postRight) {
12        if (preLeft > preRight || postLeft > postRight) {
13            return null;
14        }
15        TreeNode root = new TreeNode(pre[preLeft]);
16        if (preLeft == preRight) {
17            return root;
18        }
19        int index = postLeft;
20        while (post[index] != pre[preLeft + 1]) {
21            index++;
22        }
23        // 左子树节点的个数
24        int count = index - postLeft;
25        root.left = helper(preLeft + 1, preLeft + 1 + count, postLeft, index);
26        root.right = helper(preLeft + 2 + count, preRight, index + 1, preRight - 1);
27        return root;
28    }
29}

09. 用两个栈实现队列

自己的想法

方法一:一个入,一个出

 1class CQueue {
 2  
 3    // 用来装入
 4    Deque<Integer> in;
 5    // 用来取出
 6    Deque<Integer> out;
 7
 8    public CQueue() {
 9        in = new LinkedList<>();
10        out = new LinkedList<>();
11    }
12
13    public void appendTail(int value) {
14        while (out.size() != 0) {
15            in.push(out.pop());
16        }
17        in.push(value);
18    }
19
20    public int deleteHead() {
21        while (in.size() != 0) {
22            out.push(in.pop());
23        }
24        return out.size() != 0 ? out.pop() : -1;
25    }
26}

方法二:只在删除做处理

 1class CQueue {
 2    LinkedList<Integer> stack1;
 3    LinkedList<Integer> stack2;
 4    public CQueue() {
 5        stack1 = new LinkedList<>();
 6        stack2 = new LinkedList<>();
 7    }
 8  
 9    public void appendTail(int value) {
10        stack1.add(value);
11    }
12  
13    public int deleteHead() {
14        if(stack2.isEmpty()){
15            if(stack1.isEmpty()) return -1;
16            while(!stack1.isEmpty()){
17                stack2.add(stack1.pop());
18            }
19            return stack2.pop();
20        }else {
21            return stack2.pop();
22        }
23    }
24}
用队列实现栈

看题解后

方法一:两个队列

 1class MyStack {
 2
 3    Queue<Integer> in;
 4    Queue<Integer> out;
 5    /** Initialize your data structure here. */
 6    public MyStack() {
 7        in = new LinkedList<>();
 8        out = new LinkedList<>();
 9    }
10  
11    /** Push element x onto stack. */
12    public void push(int x) {
13        in.offer(x);
14        while(out.size() != 0) {
15            in.offer(out.poll());
16        }
17        while(in.size() != 0) {
18            out.offer(in.poll());
19        }
20    }
21  
22    /** Removes the element on top of the stack and returns that element. */
23    public int pop() {
24        return out.poll();
25    }
26  
27    /** Get the top element. */
28    public int top() {
29        return out.peek();
30    }
31  
32    /** Returns whether the stack is empty. */
33    public boolean empty() {
34        return out.isEmpty();
35    }
36}

方法二:一个队列

 1class MyStack {
 2
 3    Queue<Integer> queue;
 4    /** Initialize your data structure here. */
 5    public MyStack() {
 6        queue = new LinkedList<>();
 7    }
 8  
 9    /** Push element x onto stack. */
10    public void push(int x) {
11        // 获取队列的长度
12        int size = queue.size();
13        queue.offer(x);
14        while(size-- != 0) {
15            queue.offer(queue.poll());
16        }
17    }
18  
19    /** Removes the element on top of the stack and returns that element. */
20    public int pop() {
21        return queue.poll();
22    }
23  
24    /** Get the top element. */
25    public int top() {
26        return queue.peek();
27    }
28  
29    /** Returns whether the stack is empty. */
30    public boolean empty() {
31        return queue.isEmpty();
32    }
33}
34
35/**
36 * Your MyStack object will be instantiated and called as such:
37 * MyStack obj = new MyStack();
38 * obj.push(x);
39 * int param_2 = obj.pop();
40 * int param_3 = obj.top();
41 * boolean param_4 = obj.empty();
42 */

10- I. 斐波那契数列

自己的想法

方法一:递归(超时)

 1class Solution {
 2    public int fib(int n) {
 3        if (n == 0) {
 4            return 0;
 5        }
 6        if (n == 1) {
 7            return 1;
 8        }
 9        return (fib(n - 1) + fib(n - 2)) % 1000000007;
10    }
11}

方法二:动态规划

 1class Solution {
 2    public int fib(int n) {
 3        if (n == 0) {
 4            return 0;
 5        }
 6        if (n == 1) {
 7            return 1;
 8        }
 9        int a = 0, b = 1;
10        while (n >= 2) {
11            int c = (a + b) % 1000000007;
12            a = b;
13            b = c;
14            n--;
15        }
16        return b;
17    }
18}

10- II. 青蛙跳台阶问题

自己的想法

方法一:动态规划

 1class Solution {
 2
 3    public int numWays(int n) {
 4        if (n == 0 || n == 1) {
 5            return 1;
 6        }
 7        int a = 1, b = 1;
 8        while (n >= 2) {
 9            int c = (a + b) % 1000000007;
10            a = b;
11            b = c;
12            n--;
13        }
14        return b;
15    }
16}

11. 旋转数组的最小数字

看题解后

方法一:二分查找

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.4 MB, 在所有 Java 提交中击败了27.24%的用户
 1class Solution {
 2
 3    public int minArray(int[] numbers) {
 4        int left = 0, right = numbers.length - 1;
 5        while (left < right) {
 6            int mid = (left + right) >>> 1;
 7            // 如果中间的数小于右边的数
 8            if (numbers[mid] < numbers[right]) {
 9                right = mid;
10            } else if (numbers[mid] > numbers[right]) {
11                left = mid + 1;
12            } else {
13                // 它们的值相同,所以无论 numbers[right] 是不是最小值,都有一个它的「替代品」numbers[mid],因此我们可以忽略二分查找区间的右端点。
14                right--;
15            }
16        }
17        return numbers[left];
18    }
19}

12. 矩阵中的路径

自己的想法

方法一:DFS

  • 执行用时:6 ms, 在所有 Java 提交中击败了65.95%的用户
  • 内存消耗:40.6 MB, 在所有 Java 提交中击败了7.57%的用户
 1class Solution {
 2    int n;
 3    int m;
 4
 5    public boolean exist(char[][] board, String word) {
 6        n = board.length;
 7        m = board[0].length;
 8        for (int i = 0; i < n; i++) {
 9            for (int j = 0; j < m; j++) {
10                if (is(board, word, i, j, 0)) {
11                    return true;
12                }
13            }
14        }
15        return false;
16    }
17
18    public boolean is(char[][] board, String word, int i, int j, int index) {
19        if (index == word.length()) {
20            return true;
21        }
22        // 越界、判断字符是否可用或字符不相等
23        if (i < 0 || i == n || j < 0 || j == m || board[i][j] != word.charAt(index)) {
24            return false;
25        }
26        board[i][j] = '\0';
27        if (is(board, word, i + 1, j, index + 1)
28            || is(board, word, i, j + 1, index + 1)
29            || is(board, word, i - 1, j, index + 1)
30            || is(board, word, i, j - 1, index + 1)) {
31                return true;
32            }
33        board[i][j] = word.charAt(index);
34        return false; 
35    }
36}

13. 机器人的运动范围

自己的想法

方法一:DFS

  从(0,0)出发,只用往右和下走,不用往左和上走。

  • 执行用时:1 ms, 在所有 Java 提交中击败了84.01%的用户
  • 内存消耗:35.5 MB, 在所有 Java 提交中击败了52.19%的用户
 1class Solution {
 2
 3    int m;
 4    int n;
 5    boolean[][] is;
 6
 7    public int movingCount(int m, int n, int k) {
 8        this.m = m;
 9        this.n = n;
10        is = new boolean[m][n];
11        return dfs(0, 0, k);
12    }
13
14    public int dfs(int i, int j, int k) {
15        // 不满足要求则结束
16        if (i < 0 || i == m || j < 0 || j == n || is[i][j] || is(i, j, k)) {
17            return 0;
18        }
19        is[i][j] = true;
20        // 只用向右和向下走
21        return 1 + dfs(i + 1, j, k) + dfs(i, j + 1, k);
22    }
23
24    // 不满足要求返回true
25    public boolean is(int i, int j, int k) {
26        int sum = 0;
27        while (i != 0) {
28            sum += i % 10;
29            i /= 10;
30        }
31        while (j != 0) {
32            sum += j % 10;
33            j /= 10;
34        }
35        return sum > k;
36    }
37}

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.3 MB, 在所有 Java 提交中击败了83.12%的用户
 1class Solution {
 2
 3    int m;
 4    int n;
 5    int k;
 6    boolean[][] is;
 7
 8    public int movingCount(int m, int n, int k) {
 9        this.k = k;
10        this.m = m;
11        this.n = n;
12        is = new boolean[m][n];
13        return dfs(0, 0, 0, 0);
14    }
15
16    public int dfs(int i, int j, int si, int sj) {
17        // 不满足要求则结束
18        if (i == m || j == n || is[i][j] || (si + sj) > k) {
19            return 0;
20        }
21        is[i][j] = true;
22        // 只用向右和向下走
23        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);
24    }
25}

方法二:BFS

  • 执行用时:7 ms, 在所有 Java 提交中击败了13.10%的用户
  • 内存消耗:37.6 MB, 在所有 Java 提交中击败了7.30%的用户
 1class Solution {
 2
 3    public int movingCount(int m, int n, int k) {
 4        int count = 0;
 5        boolean[][] is = new boolean[m][n];
 6        Deque<int[]> stack = new LinkedList<>();
 7        stack.push(new int[]{0, 0, 0, 0});
 8        while (stack.size() != 0) {
 9            // 取出栈顶元素
10            int[] array = stack.pop();
11            // 判断是否合法
12            if (array[0] == m || array[1] == n || is[array[0]][array[1]] || (array[2] + array[3]) > k) {
13                continue;
14            }
15            is[array[0]][array[1]] = true;
16            count++;
17            stack.push(new int[]{array[0] + 1, array[1], (array[0] + 1) % 10 != 0 ? array[2] + 1 : array[2] - 8, array[3]});
18            stack.push(new int[]{array[0], array[1] + 1, array[2], (array[1] + 1) % 10 != 0 ? array[3] + 1 : array[3] - 8});
19        }
20        return count;
21    }
22}

14- I. 剪绳子

看题解后

方法一:动态规划

  • 执行用时:1 ms, 在所有 Java 提交中击败了45.32%的用户
  • 内存消耗:35.4 MB, 在所有 Java 提交中击败了18.05%的用户
 1class Solution {
 2
 3    public int cuttingRope(int n) {
 4        // 因为最少分为两段
 5        if (n <= 3) {
 6            return 1 * (n - 1);
 7        }
 8        // 指定长度的最大值
 9        int[] dp = new int[n + 1];
10        // 3 以下的绳子不需要拆分,拆分反而变小
11        dp[1] = 1;
12        dp[2] = 2;
13        dp[3] = 3;
14        // 长度为 i
15        for (int i = 4; i <= n; i++) {
16            // 拆分的长度,循环一半向上取整即可
17            for (int j = 1; j < i / 2 + 1; j++) {
18                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
19            }
20        }
21        return dp[n];
22    }
23}

方法二:贪心

  将 n 切分为多块。

1假如 ni >= 5,拆分出一个3
2    3 * (ni - 3) >= ni
3         3ni - 9 >= ni
4             2ni >= 9  因为 ni 大于 5,所以成立
5当ni == 4,拆分为 4 = 2 * 2
6因为 2 * 2 * 2 < 3 * 3
7所以拆分的线段只有 2 和 3,且 2 的个数最多为两个
  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.5 MB, 在所有 Java 提交中击败了10.67%的用户
 1class Solution {
 2    public int cuttingRope(int n) {
 3        if (n <= 3) {
 4            return 1 * (n - 1);
 5        }
 6        int res = 1;
 7        if (n % 3 == 1) {
 8            n -= 4;
 9            res *= 4;
10        } else if (n % 3 == 2) {
11            n -= 2;
12            res *= 2;
13        }
14        return (int) (res * Math.pow(3, n / 3));
15    }
16}

14- II. 剪绳子 II

自己的想法

方法一: 贪心

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.3 MB, 在所有 Java 提交中击败了34.61%的用户
 1class Solution {
 2  
 3    public int cuttingRope(int n) {
 4        if (n <= 3) {
 5            return 1 * (n - 1);
 6        }
 7        int res = 1;
 8        if (n % 3 == 1) {
 9            n -= 4;
10            res *= 4;
11        } else if (n % 3 == 2) {
12            n -= 2;
13            res *= 2;
14        }
15        int count = n / 3;
16        long a = 1;
17        for (int i = 0; i < count; i++) {
18            a = (a * 3) % 1000000007;
19        }
20        return (int) (res * a % 1000000007);
21    }
22}

方法二:快速幂

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.3 MB, 在所有 Java 提交中击败了34.61%的用户
 1class Solution {
 2    public int cuttingRope(int n) {
 3        if (n <= 3) {
 4            return 1 * (n - 1);
 5        }
 6        int res = 1;
 7        if (n % 3 == 1) {
 8            n -= 4;
 9            res *= 4;
10        } else if (n % 3 == 2) {
11            n -= 2;
12            res *= 2;
13        }
14        return (int) (res * myPow(3, n / 3) % 1000000007);
15    }
16
17    public long myPow(long x, int b) {
18        long res = 1;
19        while (b != 0) {
20            // 如果当前位为1,则进行乘
21            if ((b & 1) == 1) {
22                res = res * x % 1000000007;
23            }
24            x = x * x % 1000000007;
25            b >>= 1;
26        }
27        return res;
28    }
29}

15. 二进制中1的个数

自己的想法

方法一:逐位判断

  因为可能是负数,所有需要无符号右移(>>>)。

  • 执行用时:1 ms, 在所有 Java 提交中击败了96.63%的用户
  • 内存消耗:35.6 MB, 在所有 Java 提交中击败了10.44%的用户
 1public class Solution {
 2    // you need to treat n as an unsigned value
 3    public int hammingWeight(int n) {
 4        int count = 0;
 5        while (n != 0) {
 6            // 判断最右比特位是否为 1
 7            if ((n & 1) == 1) {
 8                count++;
 9            }
10            n >>>= 1;
11        }
12        return count;
13    }
14}

看题解后

代码优化

 1class Solution {
 2    // you need to treat n as an unsigned value
 3    public int hammingWeight(int n) {
 4        int count = 0;
 5        while (n != 0) {
 6            count += n & 1;
 7            n >>>= 1;
 8        }
 9        return count;
10    }
11}

方法二:n & (n−1)

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

1n 	= 10101000
2n-1	= 10100111
3n&(n-1)	= 10100000
  • 执行用时:1 ms, 在所有 Java 提交中击败了96.63%的用户
  • 内存消耗:35.5 MB, 在所有 Java 提交中击败了18.84%的用户
 1class Solution {
 2    // you need to treat n as an unsigned value
 3    public int hammingWeight(int n) {
 4        int count = 0;
 5        while (n != 0) {
 6            n &= n - 1;
 7            count ++;
 8        }
 9        return count;
10    }
11}

16. 数值的整数次方

自己的想法

方法一:暴力破解(超时)

 1class Solution {
 2    public double myPow(double x, int n) {
 3        double result;
 4        if (n >= 0) {
 5            result = 1;
 6            while (n-- != 0) {
 7                result *= x;
 8            }
 9        } else {
10            // n 小于 0 时
11            result = x;
12            n = -n;
13            while (--n != 0) {
14                result *= x;
15            }
16            result = 1 / result;
17        }
18        return result;
19    }
20}

看题解后

方法二:快速幂(位运算)

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

40a7a874523e26cacae9c502a6e8cf8b58dba878739f17e6bb3ed6be76e97569Picture1.png

  • 执行用时:1 ms, 在所有 Java 提交中击败了98.46%的用户
  • 内存消耗:37.6 MB, 在所有 Java 提交中击败了62.13%的用户
 1class Solution {
 2    public double myPow(double x, int n) {
 3        double res = 1;
 4        long  b = n;
 5        // 如果这个数为负数则进行转换
 6        if (b < 0) {
 7            x = 1 / x;
 8            b = -b;
 9        }
10        while(b != 0) {
11            // 如果当前位为1,则进行乘
12            if ((b & 1) == 1) {
13                res *= x;
14            }
15            x *= x;
16            b >>= 1;
17        }
18        return res;  
19    }
20}

方法三:快速幂(二分)

  二分推导: 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%的用户
 1class Solution {
 2    public double myPow(double x, int n) {
 3        //当 n = 0 时,返回 1
 4        if(n == 0){
 5            return 1;
 6        }else if(n < 0){
 7            // 当 n < 0 时,返回 1/ x^(-n), 为了防止越界,所以需要-1
 8            return 1 / (x * myPow(x, - n - 1));
 9        }else if(n % 2 == 1){
10            // 为避免越界,提取 x
11            return x * myPow(x, n - 1);
12        }else{
13            return myPow(x * x, n / 2);
14        }   
15    }
16}

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

自己的想法

方法一:暴力

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.99%的用户
  • 内存消耗:46.8 MB, 在所有 Java 提交中击败了27.88%的用户
 1class Solution {
 2    public int[] printNumbers(int n) {
 3        int l = (int)Math.pow(10, n) - 1;
 4        int[] res = new int[l];
 5        for (int i = 0; i < l; i++) {
 6            res[i] = i + 1;
 7        }
 8        return res;
 9    }
10}

方法二:大数

  • 执行用时:8 ms, 在所有 Java 提交中击败了15.98%的用户
  • 内存消耗:46.7 MB, 在所有 Java 提交中击败了51.46%的用户
 1class Solution {
 2    // 结果集
 3    int[] res;
 4    // index 表示结果集的下标,n 表示数的位数
 5    int index, n;
 6    // 用于拼接字符串
 7    char[] num;
 8
 9    public int[] printNumbers(int n) {
10        this.n = n;
11        // 计算数的个数
12        res = new int[(int) Math.pow(10, n) - 1];
13        num = new char[n];
14        // 从第一位开始构造
15        dfs(0);
16        return res;
17    }
18
19    void dfs(int x) {
20        // 构造完毕,开始生成字符
21        if (x == n) {
22            int value = Integer.parseInt(String.valueOf(num));
23            // 如果不为 0,则添加
24            if (value != 0) {
25                res[index++] = value;
26            }
27            return;
28        }
29        // 全排列
30        for (char i = '0'; i <= '9'; i++) {
31            num[x] = i;
32            dfs(x + 1);
33        }
34    }
35}

18. 删除链表的节点

自己的想法

方法一

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:37.8 MB, 在所有 Java 提交中击败了64.47%的用户
 1class Solution {
 2    public ListNode deleteNode(ListNode head, int val) {
 3        if (head == null) {
 4            return null;
 5        }
 6        // 删除头节点
 7        if (head.val == val) {
 8            return head.next;
 9        }
10        ListNode node = head;
11        while (node.next != null) {
12            if (node.next.val == val) {
13                node.next = node.next.next;
14                break;
15            }
16            node = node.next;
17        }
18        return head;
19    }
20}

19. 正则表达式匹配

看题解后

方法一:动态规划

  • 执行用时:4 ms, 在所有 Java 提交中击败了69.50%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了17.66%的用户
 1class Solution {
 2    public boolean isMatch(String s, String p) {
 3        int m = s.length();
 4        int n = p.length();
 5        // dp[0][0] 代表 s 和 p 均为空字符串,dp[1][1] 代表 s 和 p 的第一个字符(即在 s 和 p 中下标为 0 的字符)
 6        boolean[][] dp = new boolean[m + 1][n + 1];
 7        dp[0][0] = true;
 8        for (int i = 0; i <= m; i++) {
 9            for (int j = 1; j <= n; j++) {
10                // p 的第 j 个字符为 *
11                if (p.charAt(j - 1) == '*') {
12                    // 匹配 s 的第 i 个字符和 p 的第 j-1 个字符
13                    if (matches(s, p, i, j - 1)) {
14                        // p 中 * 前面的字符在 s 中出现多次或者在 s 中只出现 1 次
15                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
16                    } else {
17                        // p 中 * 前面的在 s 中字符出现 0 次
18                        dp[i][j] = dp[i][j - 2];
19                    }
20                } else {
21                    // p 的第 j 个字符不为 *
22                    // 匹配 s 的第 i 个字符和 p 的第 j 个字符
23                    if (matches(s, p, i, j)) {
24                        // 匹配成功,状态转移;匹配不成功,默认是false
25                        dp[i][j] = dp[i - 1][j - 1];
26                    }
27                }
28            }
29        }
30        return dp[m][n];
31    }
32
33    private boolean matches(String s, String p, int i, int j) {
34        // 注意在字符串中的下标变换,0 表示没有字符
35        if (i == 0) {
36            return false;
37        }
38        // 如果当前匹配为 . 则通过
39        if (p.charAt(j - 1) == '.') {
40            return true;
41        }
42        // 否则判断字符是否相等
43        return s.charAt(i - 1) == p.charAt(j - 1);
44    }
45}

20. 表示数值的字符串

看题解后

方法一:有限状态自动机

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

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

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

Y6A4Z6N2UK34MB7E.png

  • 执行用时:7 ms, 在所有 Java 提交中击败了41.02%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了57.39%的用户
 1class Solution {
 2    public boolean isNumber(String s) {
 3        Map[] states = {
 4                new HashMap<Character,Integer>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
 5                new HashMap<Character,Integer>() {{ put('d', 2); put('.', 4); }},                           // 1.
 6                new HashMap<Character,Integer>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
 7                new HashMap<Character,Integer>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
 8                new HashMap<Character,Integer>() {{ put('d', 3); }},                                        // 4.
 9                new HashMap<Character,Integer>() {{ put('s', 6); put('d', 7); }},                           // 5.
10                new HashMap<Character,Integer>() {{ put('d', 7); }},                                        // 6.
11                new HashMap<Character,Integer>() {{ put('d', 7); put(' ', 8); }},                           // 7.
12                new HashMap<Character,Integer>() {{ put(' ', 8); }}                                         // 8.
13        };
14        int p = 0;
15        char t;
16        for (char c : s.toCharArray()) {
17            if (c >= '0' && c <= '9') {
18                t = 'd';
19            } else if (c == '+' || c == '-') {
20                t = 's';
21            } else if (c == 'e' || c == 'E') {
22                t = 'e';
23            } else if (c == '.' || c == ' ') {
24                t = c;
25            } else {
26                t = '?';
27            }
28            if (!states[p].containsKey(t)) {
29                return false;
30            }
31            p = (int) states[p].get(t);
32        }
33        return p == 2 || p == 3 || p == 7 || p == 8;
34    }
35}

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

自己的想法

方法一:首尾双指针

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了98.18%的用户
  • 内存消耗:46.2 MB, 在所有 Java 提交中击败了75.79%的用户
 1class Solution {
 2    public int[] exchange(int[] nums) {
 3        int left = 0;
 4        int right = nums.length - 1;
 5        while (left < right) {
 6            // 等于偶数则互换,位运算判偶
 7            if ((nums[left] & 1) == 0) {
 8                int tmp = nums[left];
 9                nums[left] = nums[right];
10                nums[right] = tmp; 
11                right--;
12            } else {
13                left++;
14            }
15        }
16        return nums;
17    }
18}

看题解后

方法二:快慢双指针(能保证数组原顺序)

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了98.18%的用户
  • 内存消耗:46.4 MB, 在所有 Java 提交中击败了51.89%的用户
 1class Solution {
 2    public int[] exchange(int[] nums) {
 3        int low = 0, fast = 0;
 4        while (fast < nums.length) {
 5            // 奇数则互换
 6            if ((nums[fast] & 1) == 1) {
 7                int tmp = nums[low];
 8                nums[low] = nums[fast];
 9                nums[fast] = tmp;
10                low++;
11            }
12            fast++;
13        }
14        return nums;
15    }
16}

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

自己的想法

方法一:快慢指针

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.5 MB, 在所有 Java 提交中击败了16.87%的用户
 1class Solution {
 2    public ListNode getKthFromEnd(ListNode head, int k) {
 3        // 快慢指针
 4        ListNode start = head, end = head;
 5        // 移动快指针
 6        while (k-- != 0) {
 7            end = end.next;
 8        }
 9        while (end != null) {
10            start = start.next;
11            end = end.next;
12        }
13        return start;
14    }
15}

24. 反转链表

自己的想法

方法一:使用栈

  • 执行用时:1 ms, 在所有 Java 提交中击败了5.78%的用户
  • 内存消耗:38 MB, 在所有 Java 提交中击败了82.31%的用户
 1class Solution {
 2    public ListNode reverseList(ListNode head) {
 3        Deque<ListNode> stack = new LinkedList<>();
 4        // 先将节点压入栈
 5        while (head != null) {
 6            stack.push(head);
 7            head = head.next;
 8        }
 9        ListNode root = new ListNode();
10        // 中间节点
11        ListNode node = root;
12        while (stack.size() != 0) {
13            node.next = stack.pop();
14            node = node.next;
15        }
16        // 消除环
17        node.next = null;
18        return root.next;
19    }
20}

看题解后

方法二:递归

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了11.01%的用户
 1class Solution {
 2    public ListNode reverseList(ListNode head) {
 3        if (head == null || head.next == null) {
 4            return head;
 5        }
 6        // 获取最后的节点
 7        ListNode node = reverseList(head.next);
 8        // 将下一个节点指向当前节点
 9        head.next.next = head;
10        // 防止环
11        head.next = null;
12        return node;
13    }
14}

方法三:迭代

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.3 MB, 在所有 Java 提交中击败了37.38%的用户
 1class Solution {
 2    public ListNode reverseList(ListNode head) {
 3        // 记录当前节点和前节点
 4        ListNode node = head;
 5        ListNode front = null;
 6        while (node != null) {
 7            // 取出下一个节点
 8            ListNode next = node.next;
 9            // 将当前节点指向前一个节点
10            node.next = front;
11            // 重定向前节点和当前节点
12            front = node;
13            node = next;
14        }
15        return front;
16    }
17}

25. 合并两个排序的链表

自己的想法

方法一:归并排序

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.31%的用户
  • 内存消耗:38.7 MB, 在所有 Java 提交中击败了28.42%的用户
 1class Solution {
 2    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 3        // 结果集
 4        ListNode node = new ListNode();
 5        ListNode root = node;
 6        while (l1 != null && l2 != null) {
 7            if (l1.val < l2.val) {
 8                node.next = l1;
 9                l1 = l1.next;
10            } else {
11                node.next = l2;
12                l2 = l2.next;
13            }
14            node = node.next;
15        }
16        // 处理剩下的节点
17        node.next = l1 != null ? l1 : l2;
18        return root.next;
19    }
20}

26. 树的子结构

自己的想法

方法一:层次遍历

  • 执行用时:4 ms, 在所有 Java 提交中击败了5.96%的用户
  • 内存消耗:40.6 MB, 在所有 Java 提交中击败了5.10%的用户
 1class Solution {
 2    public boolean isSubStructure(TreeNode A, TreeNode B) {
 3        if (A == null || B == null) {
 4            return false;
 5        }
 6        // 层次遍历
 7        Queue<TreeNode> queue = new LinkedList<>();
 8        queue.offer(A);
 9        while (queue.size() != 0) {
10            TreeNode node = queue.poll();
11            if (node.val == B.val) {
12                if (isEques(node, B)) {
13                    return true;
14                }
15            }
16            if (node.left != null) {
17                queue.offer(node.left);
18            }
19            if (node.right != null) {
20                queue.offer(node.right);
21            }
22        }
23        return false;
24    }
25
26    // 判断两个树是否相等
27    public boolean isEques(TreeNode A, TreeNode B) {
28        if (B == null) {
29            return true;
30        } else if (A == null) {
31            return false;
32        } else {
33            // 两个都不为 null,则判断当前值和其子树
34            return A.val == B.val && isEques(A.left, B.left) && isEques(A.right, B.right);
35        }
36    }
37}

看题解后

方法二:先序遍历

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:40.2 MB, 在所有 Java 提交中击败了49.38%的用户
 1class Solution {
 2    public boolean isSubStructure(TreeNode A, TreeNode B) {
 3        if (A == null || B == null) {
 4            return false;
 5        }
 6        // 先序遍历
 7        return isEquals(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
 8    }
 9
10    // 判断两个树是否相等
11    public boolean isEquals(TreeNode A, TreeNode B) {
12        if (B == null) {
13            return true;
14        } else if (A == null) {
15            return false;
16        } else {
17            // 两个都不为 null,则判断当前值和其子树
18            return A.val == B.val && isEquals(A.left, B.left) && isEquals(A.right, B.right);
19        }
20    }
21}

27. 二叉树的镜像

看题解后

方法一:递归

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.7 MB, 在所有 Java 提交中击败了79.84%的用户
 1class Solution {
 2    public TreeNode mirrorTree(TreeNode root) {
 3        if (root == null) {
 4            return root;
 5        }
 6        TreeNode left = mirrorTree(root.right);
 7        TreeNode right = mirrorTree(root.left);
 8        root.left = left;
 9        root.right = right;
10        return root;
11    }
12}

方法二:层次遍历

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.8 MB, 在所有 Java 提交中击败了46.82%的用户
 1class Solution {
 2    public TreeNode mirrorTree(TreeNode root) {
 3        if (root == null) {
 4            return null;
 5        }
 6        Queue<TreeNode> queue = new LinkedList<>();
 7        queue.offer(root);
 8        while (!queue.isEmpty()) {
 9            TreeNode node = queue.poll();
10            // 交换其左右子节点
11            TreeNode tmp = node.left;
12            node.left = node.right;
13            node.right = tmp;
14            if (node.left != null) {
15                queue.offer(node.left);
16            }
17            if (node.right != null) {
18                queue.offer(node.right);
19            }
20        }
21        return root;
22    }
23}

28. 对称的二叉树

看题解后

方法一:递归

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.4 MB, 在所有 Java 提交中击败了59.71%的用户
 1class Solution {
 2    public boolean isSymmetric(TreeNode root) {
 3        if (root == null) {
 4            return true;
 5        }
 6        return isEquals(root.left, root.right);
 7    }
 8  
 9    public boolean isEquals(TreeNode A, TreeNode B) {
10        if (A == null && B == null) {
11            return true;
12        }
13        if (A == null || B == null) {
14            return false;
15        }
16        return A.val == B.val && isEquals(A.left, B.right) && isEquals(A.right, B.left);
17    }
18}

29. 顺时针打印矩阵

自己的想法

方法一:模拟

  • 执行用时:3 ms, 在所有 Java 提交中击败了20.79%的用户
  • 内存消耗:39.9 MB, 在所有 Java 提交中击败了29.39%的用户
 1class Solution {
 2    public int[] spiralOrder(int[][] matrix) {
 3        if (matrix == null || matrix.length == 0) {
 4            return new int[0];
 5        }
 6        // 用来防止越界
 7        int n = matrix.length, m = matrix[0].length;
 8        // 计算矩阵中数的个数
 9        int length = n * m;
10        // 结果集
11        int[] result = new int[length];
12        // 移动的下标
13        int i = 0, j = 0;
14        // 用来控制移动的方向
15        int[][] move = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
16        // 控制 move 的下标
17        int mv = 0;
18        // 记录走过的下标
19        boolean[][] is = new boolean[n][m];
20        for (int index = 0; index < length; index++) {
21            // 存储当前数
22            result[index] = matrix[i][j];
23            is[i][j] = true;
24            // 移动下标
25            i += move[mv][0];
26            j += move[mv][1];
27            if (i < 0 || i == n || j < 0 || j == m || is[i][j]) {
28                // 如果下标不合法,则返回
29                i -= move[mv][0];
30                j -= move[mv][1];
31                mv = (mv + 1) % 4;
32                // 然后转向
33                i += move[mv][0];
34                j += move[mv][1];
35            }
36        }
37        return result;
38    }
39}

方法二:模拟

  使用一个 while 套 4 个 for。

  • 执行用时:1 ms, 在所有 Java 提交中击败了97.57%的用户
  • 内存消耗:39.7 MB, 在所有 Java 提交中击败了64.01%的用户
 1class Solution {
 2    public int[] spiralOrder(int[][] matrix) {
 3        if (matrix.length == 0) {
 4            return new int[0];
 5        }
 6        // 最大下标
 7        int n = matrix.length - 1, m = matrix[0].length - 1;
 8        // 移动的下标,存储下标
 9        int i = 0, j = 0, index = 0;
10        // 结果集
11        int[] result = new int[(n + 1) * (m + 1)];
12        while (i <= n && j <= m) {
13            // 往右走
14            for (int z = j; z <= m; z++) {
15                result[index++] = matrix[i][z];
16            }
17            i++;
18            // 判断是否越界
19            if (i > n) {
20                break;
21            }
22            // 往下走
23            for (int z = i; z <= n; z++) {
24                result[index++] = matrix[z][m];
25            }
26            m--;
27            if (j > m) {
28                break;
29            }
30            // 往左走
31            for (int z = m; z >= j; z--) {
32                result[index++] = matrix[n][z];
33            }
34            n--;
35            // 往上走
36            for (int z = n; z >= i; z--) {
37                result[index++] = matrix[z][j];
38            }
39            j++;
40        }
41        return result;
42    }
43}

30. 包含min函数的栈

看题解后

方法一

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

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

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

  • 执行用时:21 ms, 在所有 Java 提交中击败了99.24%的用户
  • 内存消耗:40.2 MB, 在所有 Java 提交中击败了79.89%的用户
 1class MinStack {
 2
 3    // 维护两个栈一个栈存储元素,一个栈存储较小的数
 4    Deque<Integer> stack;
 5    Deque<Integer> min;
 6
 7    public MinStack() {
 8        stack = new LinkedList<>();
 9        min = new LinkedList<>();
10    }
11
12    public void push(int x) {
13        stack.push(x);
14        if (min.size() == 0 || min.peek() >= x) {
15            min.push(x);
16        }
17    }
18
19    public void pop() {
20        // Integer 引用类型使用 equals 比较
21        if (min.peek().equals(stack.pop())) {
22            min.pop();
23        }
24    }
25
26    public int top() {
27        return stack.peek();
28    }
29
30    public int min() {
31        return min.peek();
32    }
33}

31. 栈的压入、弹出序列

看题解后

方法一:模拟栈

  • 执行用时:3 ms, 在所有 Java 提交中击败了36.93%的用户
  • 内存消耗:38 MB, 在所有 Java 提交中击败了85.18%的用户
 1class Solution {
 2    public boolean validateStackSequences(int[] pushed, int[] popped) {
 3        Deque<Integer> stack = new LinkedList<>();
 4        int i = 0;
 5        // 将当前数组的所有的数据入栈
 6        for (int value : pushed) {
 7            stack.push(value);
 8            // 如果栈不为空,则判断和 popped[i] 是否相等
 9            while (stack.size() != 0 && stack.peek() == popped[i]) {
10                // 不相等则弹出
11                stack.pop();
12                i++;
13            }
14        }
15        // 遍历完,则成立
16        return i == pushed.length;
17    }
18}

方法二:双指针

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.2 MB, 在所有 Java 提交中击败了45.39%的用户
 1class Solution {
 2    public boolean validateStackSequences(int[] pushed, int[] popped) {
 3        // i 指向 pushed,j 指向 popped
 4        int i = 0, j = 0;
 5        // pushed 数组不会改变,改变的只是下表 i
 6        for (int num : pushed) {
 7            // 覆盖值
 8            pushed[i] = num;
 9            while (i >= 0 && pushed[i] == popped[j]) {
10                j++;
11                i--;
12            }
13            // 如果此时不等于 pop 指针指到的值
14            i++;
15        }
16        return i == 0;
17    }
18}

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

自己的想法

方法一:层次遍历

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.71%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了55.00%的用户
 1class Solution {
 2    public int[] levelOrder(TreeNode root) {
 3        if (root == null) {
 4            return new int[0];
 5        }
 6        List<Integer> list = new ArrayList<>();
 7        Queue<TreeNode> queue = new LinkedList<>();
 8        queue.offer(root);
 9        while (queue.size() != 0) {
10            TreeNode node = queue.poll();
11            list.add(node.val);
12            if (node.left != null) {
13                queue.offer(node.left);
14            }
15            if (node.right != null) {
16                queue.offer(node.right);
17            }
18        }
19        int[] array = new int[list.size()];
20        for (int i = 0; i < array.length; i++) {
21            array[i] = list.get(i);
22        }
23        return array;
24    }
25}

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

看题解后

方法一:按层遍历(迭代)

  • 执行用时:1 ms, 在所有 Java 提交中击败了94.79%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了61.40%的用户
 1class Solution {
 2    public List<List<Integer>> levelOrder(TreeNode root) {
 3        List<List<Integer>> lists = new ArrayList<>();
 4        if (root == null) {
 5            return new ArrayList<>();
 6        }
 7        Queue<TreeNode> queue = new LinkedList<>();
 8        queue.offer(root);
 9        while (queue.size() != 0) {
10            List<Integer> list = new ArrayList<>();
11            for (int i = queue.size(); i > 0; i--) {
12                TreeNode node = queue.poll();
13                list.add(node.val);
14                if (node.left != null) {
15                    queue.offer(node.left);
16                }
17                if (node.right != null) {
18                    queue.offer(node.right);
19                }
20            }
21            lists.add(list);
22        }
23        return lists;
24    }
25}

方法二:先序遍历(递归)

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了60.82%的用户
 1class Solution {
 2    List<List<Integer>> res = new ArrayList<>();
 3
 4    public List<List<Integer>> levelOrder(TreeNode root) {
 5        bfs(root, 0);
 6        return res;
 7    }
 8
 9    public void bfs(TreeNode node, int level) {
10        if (node == null) {
11            return;
12        }
13        // 创建新的集合
14        if (res.size() == level) {
15            res.add(new ArrayList<>());
16        }
17        res.get(level).add(node.val);
18        bfs(node.left, level + 1);
19        bfs(node.right, level + 1);
20    }
21}

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

看题解后

方法一:双端队列

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.89%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了79.41%的用户
 1class Solution {
 2    public List<List<Integer>> levelOrder(TreeNode root) {
 3        List<List<Integer>> lists = new ArrayList<>();
 4        if (root == null) {
 5            return new ArrayList<>();
 6        }
 7        Queue<TreeNode> queue = new LinkedList<>();
 8        queue.offer(root);
 9        while (queue.size() != 0) {
10            LinkedList<Integer> list = new LinkedList<>();
11            for (int i = queue.size(); i > 0; i--) {
12                TreeNode node = queue.poll();
13                // 偶数正常
14                if ((lists.size() & 1) == 0) {
15                    list.addLast(node.val);
16                } else {
17                    list.addFirst(node.val);
18                }
19                if (node.left != null) {
20                    queue.offer(node.left);
21                }
22                if (node.right != null) {
23                    queue.offer(node.right);
24                }
25            }
26            lists.add(list);
27        }
28        return lists;
29    }
30}

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

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

看题解后

方法一:递归

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.9 MB, 在所有 Java 提交中击败了45.51%的用户
 1class Solution {
 2    public boolean verifyPostorder(int[] postorder) {
 3        return recur(postorder, 0, postorder.length - 1);
 4    }
 5
 6    boolean recur(int[] postorder, int i, int j) {
 7        // 越界则为 true
 8        if (i >= j) {
 9            return true;
10        }
11        // postorder[j] 是根
12        int p = i;
13        // 小于根节点的节点都在左子树
14        while (postorder[p] < postorder[j]) {
15            p++;
16        }
17        int m = p;
18        // 判断剩下的节点是否都属于右子树
19        while (postorder[p] > postorder[j]) {
20            p++;
21        }
22        // 如果不属于,则结束
23        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
24    }
25}

方法二:单调栈**(不会)**

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

方法一:DFS

  • 执行用时:2 ms, 在所有 Java 提交中击败了27.56%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了32.34%的用户
 1class Solution {
 2
 3    List<List<Integer>> result = new ArrayList<>();
 4    int target;
 5
 6    public List<List<Integer>> pathSum(TreeNode root, int target) {
 7        this.target = target;
 8        if (root != null) {
 9            List<Integer> list = new LinkedList<>();
10            list.add(root.val);
11            dfs(root, list, root.val);
12        }
13        return result;
14    }
15
16    public void dfs(TreeNode node, List<Integer> list, int sum) {
17        if (sum == target) {
18            // 如果相等,则判断是否为根节点
19            if (node.left == null && node.right == null) {
20                result.add(new ArrayList<>(list));
21            }
22        }
23        // 遍历左子树
24        if (node.left != null) {
25            list.add(node.left.val);
26            dfs(node.left, list, sum + node.left.val);
27            list.remove(list.size() - 1);
28
29        }
30        // 遍历右子树
31        if (node.right != null) {
32            list.add(node.right.val);
33            dfs(node.right, list, sum + node.right.val);
34            list.remove(list.size() - 1);
35        }
36    }
37}

看题解后

代码优化

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了93.78%的用户
 1class Solution {
 2    LinkedList<List<Integer>> result = new LinkedList<>();
 3    LinkedList<Integer> path = new LinkedList<>();
 4
 5    public List<List<Integer>> pathSum(TreeNode root, int target) {
 6        recur(root, target);
 7        return result;
 8    }
 9
10    void recur(TreeNode root, int sum) {
11        if (root == null) {
12            return;
13        }
14        path.add(root.val);
15        sum -= root.val;
16        if (sum == 0 && root.left == null && root.right == null) {
17            result.add(new LinkedList<>(path));
18        }
19        recur(root.left, sum);
20        recur(root.right, sum);
21        // 回溯
22        path.removeLast();
23    }
24}

35. 复杂链表的复制

看题解后

方法一:拼接+拆分

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.2 MB, 在所有 Java 提交中击败了45.05%的用户
 1class Solution {
 2
 3    public Node copyRandomList(Node head) {
 4        if (head == null) {
 5            return null;
 6        }
 7        Node node = head;
 8        // 拼接,复制节点
 9        while (node != null) {
10            // 创建新节点
11            Node tmp = new Node(node.val);
12            // 链接
13            tmp.next = node.next;
14            node.next = tmp;
15            node = node.next.next;
16        }
17        // 构建 Random
18        node = head;
19        while (node != null) {
20            if (node.random != null) {
21                node.next.random = node.random.next;
22            }
23            node = node.next.next;
24        }
25        // 拆分两个链表
26        node = head.next;
27        // pre 用于复原原链表,res 存储新链表
28        Node pre = head, res = head.next;
29        while (node.next != null) {
30            // 指向原链表
31            pre.next = node.next;
32            // 指向新建的链表
33            node.next = node.next.next;
34            node = node.next;
35            pre = pre.next;
36        }
37        pre.next = null;
38        return res;
39    }
40}

方法二:哈希表

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38 MB, 在所有 Java 提交中击败了66.28%的用户
 1class Solution {
 2    public Node copyRandomList(Node head) {
 3        if (head == null) {
 4            return null;
 5        }
 6        Node node = head;
 7        Map<Node, Node> map = new HashMap<>();
 8        // 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
 9        while (node != null) {
10            map.put(node, new Node(node.val));
11            node = node.next;
12        }
13        node = head;
14        // 构建新链表的 next 和 random 指向
15        while (node != null) {
16            map.get(node).next = map.get(node.next);
17            map.get(node).random = map.get(node.random);
18            node = node.next;
19        }
20        // 5. 返回新链表的头节点
21        return map.get(head);
22    }
23}

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

看题解后

方法一:中序遍历

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:37.9 MB, 在所有 Java 提交中击败了32.30%的用户
 1class Solution {
 2    // pre 记录前一个节点
 3    Node pre, head;
 4
 5    public Node treeToDoublyList(Node root) {
 6        if (root == null) {
 7            return null;
 8        }
 9        dfs(root);
10        head.left = pre;
11        pre.right = head;
12        return head;
13    }
14
15    void dfs(Node node) {
16        if (node == null) {
17            return;
18        }
19        dfs(node.left);
20        if (pre != null) {
21            // 前一个节点的后继指向当前节点
22            pre.right = node;
23        } else {
24            // 如果 pre 为空,则表示该节点最小,则为 head
25            head = node;
26        }
27        // 当前节点指向前一个节点
28        node.left = pre;
29        // 更换前节点
30        pre = node;
31        dfs(node.right);
32
33        new Object();
34    }
35}

37. 序列化二叉树

看题解后

方法一:利用层次遍历

  • 执行用时:24 ms, 在所有 Java 提交中击败了60.73%的用户
  • 内存消耗:40.1 MB, 在所有 Java 提交中击败了81.28%的用户
 1class Codec {
 2
 3    public String serialize(TreeNode root) {
 4        if (root == null) {
 5            return "[]";
 6        }
 7        StringBuilder res = new StringBuilder("[");
 8        Queue<TreeNode> queue = new LinkedList<>();
 9        queue.add(root);
10        while (!queue.isEmpty()) {
11            TreeNode node = queue.poll();
12            if (node != null) {
13                // 添加当前值
14                res.append(node.val).append(",");
15                queue.add(node.left);
16                queue.add(node.right);
17            } else {
18                res.append("null,");
19            }
20        }
21        // 删除最后的逗号
22        res.deleteCharAt(res.length() - 1);
23        res.append("]");
24        return res.toString();
25    }
26
27    public TreeNode deserialize(String data) {
28        if (data.equals("[]")) {
29            return null;
30        }
31        // 去掉字符串的括号,并按逗号进行拆分
32        String[] str = data.substring(1, data.length() - 1).split(",");
33        // 生成根节点
34        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
35        Queue<TreeNode> queue = new LinkedList<>();
36        queue.add(root);
37        int i = 1;
38        while (!queue.isEmpty()) {
39            TreeNode node = queue.poll();
40            // 如果下个不为空,则表示左节点不为空
41            if (!str[i].equals("null")) {
42                node.left = new TreeNode(Integer.parseInt(str[i]));
43                queue.add(node.left);
44            }
45            i++;
46            if (!str[i].equals("null")) {
47                node.right = new TreeNode(Integer.parseInt(str[i]));
48                queue.add(node.right);
49            }
50            i++;
51        }
52        return root;
53    }
54}

38. 字符串的排列

自己的想法

方法一:DFS

  • 执行用时:6 ms, 在所有 Java 提交中击败了99.10%的用户
  • 内存消耗:42.9 MB, 在所有 Java 提交中击败了70.57%的用户
 1class Solution {
 2    // 原字符串
 3    char[] array;
 4    // 字符串的长度
 5    int n;
 6    // 组成的字符串
 7    char[] c;
 8    // 记录那些字符使用过
 9    boolean[] is;
10    // 生成的字符串
11    List<String> list;
12
13    public String[] permutation(String s) {
14        array = s.toCharArray();
15        n = array.length;
16        // 排序
17        Arrays.sort(array);
18        // 组成的字符串
19        c = new char[n];
20        // 记录那些字符使用过
21        is = new boolean[n];
22        list = new ArrayList<>();
23        dfs(0);
24        // 生成结果集
25        return list.toArray(new String[0]);
26    }
27
28    public void dfs(int index) {
29        if (index == n) {
30            list.add(new String(c));
31            return;
32        }
33        for (int i = 0; i < n; i++) {
34            // 当前字符未使用过,或前一个字符和该字符相等,而前一个字符未使用过。
35            if (is[i] || (i > 0 && array[i] == array[i - 1] && !is[i - 1])) {
36                continue;
37            }
38            is[i] = true;
39            c[index] = array[i];
40            // 递归
41            dfs(index + 1);
42            is[i] = false;
43        }
44    }
45}

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

其他方法:哈希表,排序(数组中点的元素一定为众数)

看题解后

方法一:摩尔投票法

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.97%的用户
  • 内存消耗:41.8 MB, 在所有 Java 提交中击败了55.74%的用户
 1class Solution {
 2    public int majorityElement(int[] nums) {
 3        // 记录当前数出现的次数
 4        int count = 1;
 5        int index = 0;
 6        for (int i = 1; i < nums.length; i++) {
 7            if (nums[i] == nums[index]) {
 8                count++;
 9            } else {
10                // 如果之前的数被清空,则重新初始化
11                if (--count == 0) {
12                    index = i;
13                    count = 1;
14                }
15            }
16        }
17        return nums[index];
18    }
19}

代码简化:

 1class Solution {
 2    public int majorityElement(int[] nums) {
 3        // 众数为 value,票数为 count
 4        int value = 0, count = 0;
 5        for (int num : nums) {
 6            if (count == 0) {
 7                value = num;
 8            }
 9            count += num == value ? 1 : -1;
10        }
11        return value;
12    }
13}

方法二:位运算

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

  • 执行用时:15 ms, 在所有 Java 提交中击败了22.74%的用户
  • 内存消耗:41.5 MB, 在所有 Java 提交中击败了89.89%的用户
 1class Solution {
 2    public int majorityElement(int[] nums) {
 3        int result = 0;
 4        int length = nums.length;
 5        // 在 java 中 int 类型是 32 位,我们遍历每一位
 6        for (int i = 0, bit = 1; i < 32; i++, bit <<= 1) {
 7            // bitCounts 表示所有数字在 i 位置 1 的个数
 8            int bitCounts = 0;
 9            for (int num : nums) {
10                //判断数字 num 的第 i 位置是否为 1
11                if ((num & bit) == bit) {
12                    // 如果是 1,bitCounts 就加1
13                    bitCounts++;
14                }
15                // 如果 bitCounts 大于数组的一半,那么众数这个位置肯定是 1,然后通过 result |= bit 运算
16                if (bitCounts > length / 2) {
17                    result |= bit;
18                    break;
19                }
20            }
21        }
22        return result;
23    }
24}

40. 最小的k个数

看题解后

方法一:快排

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了99.60%的用户
  • 内存消耗:39.4 MB, 在所有 Java 提交中击败了94.82%的用户
 1class Solution {
 2
 3    public int[] getLeastNumbers(int[] arr, int k) {
 4        if (k == 0 || arr.length == 0) {
 5            return new int[0];
 6        }
 7        // 最后一个参数表示我们要找的是下标为 k-1 的数
 8        return quickSearch(arr, 0, arr.length - 1, k - 1);
 9    }
10
11    private int[] quickSearch(int[] nums, int left, int right, int k) {
12        // 每快排切分 1 次,找到排序后下标为 j 的元素
13        int j = partition(nums, left, right);
14        // 如果 j 恰好等于 k 就返回 j 以及 j 左边所有的数;
15        if (j == k) {
16            return Arrays.copyOf(nums, j + 1);
17        }
18        // 否则根据下标 j 与 k 的大小关系来决定继续切分左段还是右段。
19        return j > k ? quickSearch(nums, left, j - 1, k) : quickSearch(nums, j + 1, right, k);
20    }
21
22    // 快排切分,返回下标 j,使得比 nums[j] 小的数都在 j 的左边,比 nums[j] 大的数都在 j 的右边。
23    private int partition(int[] nums, int left, int right) {
24        int value = nums[left];
25        int start = left + 1, end = right;
26        // 快排单向扫描
27        while (start <= end) {
28            if (nums[start] <= value) {
29                start++;
30            } else {
31                int t = nums[end];
32                nums[end] = nums[start];
33                nums[start] = t;
34                end--;
35            }
36        }
37        nums[left] = nums[end];
38        nums[end] = value;
39        return end;
40    }
41}

方法二:大根堆(前 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%的用户
 1class Solution {
 2    public int[] getLeastNumbers(int[] arr, int k) {
 3        if (k == 0 || arr.length == 0) {
 4            return new int[0];
 5        }
 6        // 默认是小根堆,实现大根堆需要重写一下比较器。
 7        Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
 8        for (int num : arr) {
 9            // 若目前堆的大小小于K,将当前数字放入堆中
10            if (queue.size() < k) {
11                queue.offer(num);
12            } else if (num < queue.peek()) {
13                // 反之如果当前数字比大根堆堆顶小,先poll掉堆顶,再将该数字放入堆中。
14                queue.poll();
15                queue.offer(num);
16            }
17        }
18        // 返回堆中的元素
19        int[] res = new int[queue.size()];
20        int index = 0;
21        for (int num : queue) {
22            res[index++] = num;
23        }
24        return res;
25    }
26}

方法三:二叉搜索树(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%的用户
 1class Solution {
 2
 3    public int[] getLeastNumbers(int[] arr, int k) {
 4        if (k == 0 || arr.length == 0) {
 5            return new int[0];
 6        }
 7        // TreeMap 的 key 是数字, value 是该数字的个数。
 8        TreeMap<Integer, Integer> map = new TreeMap<>();
 9        // count 表示当前 map 总共存了多少个数字。
10        int count = 0;
11        for (int num : arr) {
12            // 遍历数组,若当前 map 中的数字个数小于 k,则 map 中当前数字对应个数 +1
13            if (count < k) {
14                map.put(num, map.getOrDefault(num, 0) + 1);
15                count++;
16                continue;
17            }
18            // 取出map中最大的Key(即最大的数字), 判断当前数字与map中最大数字的大小关系:
19            Map.Entry<Integer, Integer> entry = map.lastEntry();
20            // 若当前数字比 map 中最大的数字小,则将当前数字加入 map 中,并将 map 中的最大数字的个数-1。
21            if (num < entry.getKey()) {
22                map.put(num, map.getOrDefault(num, 0) + 1);
23                if (entry.getValue() == 1) {
24                    map.pollLastEntry();
25                } else {
26                    map.put(entry.getKey(), entry.getValue() - 1);
27                }
28            }
29        }
30        // 最后返回 map 中的元素
31        int[] res = new int[k];
32        int index = 0;
33        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
34            // 个数
35            int c = entry.getValue();
36            while (c-- > 0) {
37                res[index++] = entry.getKey();
38            }
39        }
40        return res;
41    }
42}
优先队列(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%的用户
 1class Solution {
 2    public int findKthLargest(int[] arr, int k) {
 3        // 默认是小根堆
 4        Queue<Integer> queue = new PriorityQueue<>();
 5        for (int num : arr) {
 6            // 若目前堆的大小小于K,将当前数字放入堆中
 7            if (queue.size() < k) {
 8                queue.offer(num);
 9            } else if (num > queue.peek()) {
10                // 反之如果当前数字比大根堆堆顶大,先 poll 掉堆顶,再将该数字放入堆中。
11                queue.poll();
12                queue.offer(num);
13            }
14        }
15        return queue.peek();
16    }
17}

方法二:快排

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

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.21%的用户
  • 内存消耗:38.7 MB, 在所有 Java 提交中击败了69.98%的用户
 1class Solution {
 2    public int findKthLargest(int[] arr, int k) {
 3        return sort(arr, 0, arr.length - 1, k - 1);
 4    }
 5
 6    // 按降序排序
 7    public int sort(int[] arr, int left, int right, int k) {
 8        int mid =  partition(arr, left, right);
 9        if (mid == k) {
10            return arr[mid];
11        }
12        return mid > k ? sort(arr, left, mid - 1, k) : sort(arr, mid + 1, right, k);
13    }
14
15    public int partition(int[] arr, int left, int right) {
16        int value = arr[left];
17        int start = left + 1, end = right;
18        while (start <= end) {
19            if (arr[start] >= value) {
20                start++;
21            } else {
22                int tmp = arr[start];
23                arr[start] = arr[end];
24                arr[end] = tmp;
25                end--;
26            }
27        }
28        arr[left] = arr[end];
29        arr[end] = value;
30        return end;
31    }
32}

41. 数据流中的中位数

看题解后

方法一:优先队列

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

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

注意:

1        int a = 5;
2        System.out.println(a / 3);// 1
3        System.out.println(a / 3.0);// 1.6666666666666667
  • 执行用时:85 ms, 在所有 Java 提交中击败了55.33%的用户
  • 内存消耗:49.8 MB, 在所有 Java 提交中击败了17.73%的用户
 1class MedianFinder {
 2
 3    // 定义两个优先队列,一个小顶堆,一个大顶堆
 4    PriorityQueue<Integer> a;
 5    PriorityQueue<Integer> b;
 6
 7    public MedianFinder() {
 8        // 存储较大的数
 9        a = new PriorityQueue<>();
10        // 存储较小的数
11        b = new PriorityQueue<>((a, b) -> b - a);
12    }
13
14    public void addNum(int num) {
15        if (a.size() != b.size()) {
16            // 对于一个新元素,将最小的给 b
17            a.offer(num);
18            // 最小的给 b
19            b.offer(a.poll());
20        } else {
21            // 对于一个新元素,将最大的给 a
22            b.offer(num);
23            // 将最大的给 a
24            a.offer(b.poll());
25        }
26    }
27
28    public double findMedian() {
29        return a.size() != b.size() ? a.peek() : (a.peek() + b.peek()) / 2.0;
30    }
31}

42. 连续子数组的最大和

看题解后

方法一:动态规划

  • 执行用时:1 ms, 在所有 Java 提交中击败了98.49%的用户
  • 内存消耗:44.9 MB, 在所有 Java 提交中击败了58.34%的用户
 1class Solution {
 2    public int maxSubArray(int[] nums) {
 3        int result = Integer.MIN_VALUE, max = 0;
 4        for (int num : nums) {
 5            // 对于每个数都有选和不选两种
 6            max = Math.max(max + num, num);
 7            result = Math.max(result, max);
 8        }
 9        return result;
10    }
11}

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

 1class Solution {
 2    public int maxSubArray(int[] nums) {
 3        int res = nums[0];
 4        for (int i = 1; i < nums.length; i++) {
 5            // 如果之前的数和小于 0,则不选
 6            nums[i] += Math.max(nums[i - 1], 0);
 7            res = Math.max(res, nums[i]);
 8        }
 9        return res;
10    }
11}

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

看题解后

方法一

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

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

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

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

346CTWMIMRO7GH1IQ.png

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

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

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

GZKJ6ELKTCWRXV1MRY.png

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

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

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

ADD1VIPUITGB9GREQ1U.png

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.2 MB, 在所有 Java 提交中击败了50.38%的用户
 1class Solution {
 2    public int countDigitOne(int n) {
 3        // 1 表示当前是个位
 4        int digit = 1, res = 0;
 5        // high 高位,cur 当前数,low 低位
 6        int high = n / 10, cur = n % 10, low = 0;
 7        while (high != 0 || cur != 0) {
 8            // 如果个位是 0
 9            if (cur == 0) {
10                res += high * digit;
11            } else if (cur == 1) {
12                res += high * digit + low + 1;
13            } else {
14                res += (high + 1) * digit;
15            }
16            // 将 cur 加入 low ,组成下轮 low
17            low += cur * digit;
18            // 下轮 cur 是本轮 high 的最低位
19            cur = high % 10;
20            // 将本轮 high 最低位删除,得到下轮 high
21            high /= 10;
22            // 位因子每轮 × 10
23            digit *= 10;
24        }
25        return res;
26    }
27}

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

看题解后

方法一

YUD5OKFOS0RUVUYTY.png

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

W3RB3H5TW22FPKD6K0.png


标题:剑指 offer——LeetCode
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2021/05/06/1620312198363.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!