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 操作即可。
- 执行用时：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 ）
- 开始的空格
- 幂符号前的正负号
- 小数点前的数字
- 小数点、小数点后的数字
- 当小数点前为空格时，小数点、小数点后的数字
- 幂符号
- 幂符号后的正负号
- 幂符号后的数字
- 结尾的空格
- 执行用时：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
- 当 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
- 当 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
- 执行用时：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. 数字序列中某一位的数字
看题解后
方法一：
所求数位 ① 在某个 digitdigit 位数中； ② 为从数字 startstart 开始的第 nn 个数位。
标题：剑指 offer——LeetCode
作者：Yi-Xing
地址：http://zyxwmj.top/articles/2021/05/06/1620312198363.html
博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！