03. 数组中重复的数字
自己的想法
方法一:标记数组
- 执行用时:1 ms, 在所有 Java 提交中击败了83.99%的用户
- 内存消耗:45.8 MB, 在所有 Java 提交中击败了94.72%的用户
class Solution {
public int findRepeatNumber(int[] nums) {
boolean[] is = new boolean[nums.length];
for (int i : nums) {
if (is[i]) {
return i;
}
is[i] = true;
}
return 0;
}
}
看题解后
方法二:置换
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:45.9 MB, 在所有 Java 提交中击败了92.22%的用户
class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 如果当前数不在它对应的下标,则进行互换
while (nums[i] != i) {
// 如果它对应的下标就是该数,则说明该数已经出现过了
if (nums[nums[i]] == nums[i]) {
return nums[i];
}
// 进行互换
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return 0;
}
}
04. 二维数组中的查找
自己的想法
方法一:从上往下找
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:44.2 MB, 在所有 Java 提交中击败了47.22%的用户
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0) {
return false;
}
int h = 0, l = 0;
int n = matrix.length, m = matrix[0].length;
while (l >= 0 && h < n && l < m) {
// 相等直接返回
if (matrix[h][l] == target) {
return true;
} else if (target < matrix[h][l]) {
// 向左走
l--;
} else if (l + 1 < m && target >= matrix[h][l + 1]) {
// 向右走
l++;
} else if (h + 1 < n && target >= matrix[h + 1][l]) {
// 右边无法走往下走
h++;
} else {
// 往左下走
l--;
h++;
}
}
return false;
}
}
看题解后
方法二:从下往上找
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:44.1 MB, 在所有 Java 提交中击败了76.34%的用户
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0) {
return false;
}
int i = matrix.length - 1, j = 0, m = matrix[0].length;
while (i >= 0 && j < m) {
if (target > matrix[i][j]) {
// 往右走
j++;
} else if (target < matrix[i][j]) {
// 往上走
i--;
} else {
return true;
}
}
return false;
}
}
05. 替换空格
自己的想法
方法一:使用 API
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:36.2 MB, 在所有 Java 提交中击败了82.08%的用户
class Solution {
public String replaceSpace(String s) {
return s.replace(" ", "+");
}
}
方法二:字符数组
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:36.3 MB, 在所有 Java 提交中击败了64.99%的用户
class Solution {
public String replaceSpace(String s) {
char[] array = new char[s.length() * 3];
// 新数组的下标
int index = 0;
// 变量字符串的字符
for (char c : s.toCharArray()) {
if (c == ' ') {
array[index++] = '%';
array[index++] = '2';
array[index++] = '0';
} else {
array[index++] = c;
}
}
return new String(array, 0, index);
}
}
06. 从尾到头打印链表
自己的想法
方法一:递归
- 执行用时:1 ms, 在所有 Java 提交中击败了72.99%的用户
- 内存消耗:39.6 MB, 在所有 Java 提交中击败了15.04%的用户
class Solution {
List<Integer> list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
recursion(head);
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
public void recursion(ListNode head) {
if (head == null) {
return;
}
recursion(head.next);
list.add(head.val);
}
}
方法二:栈
- 执行用时:1 ms, 在所有 Java 提交中击败了72.99%的用户
- 内存消耗:38.9 MB, 在所有 Java 提交中击败了88.66%的用户
class Solution {
public int[] reversePrint(ListNode head) {
Deque<Integer> stack = new LinkedList<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
int size = stack.size();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = stack.pop();
}
return result;
}
}
看题解后
方法三:不使用额外空间
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:39.1 MB, 在所有 Java 提交中击败了55.26%的用户
class Solution {
public int[] reversePrint(ListNode head) {
int length = 0;
ListNode num = head;
// 获取链表长度
while (num != null) {
length++;
num = num.next;
}
int[] result = new int[length];
for (int i = length - 1; i >= 0; i--) {
result[i] = head.val;
head = head.next;
}
return result;
}
}
07. 重建二叉树
二叉树前序遍历的顺序为:
- 先遍历根节点;
- 随后递归地遍历左子树;
- 最后递归地遍历右子树。
二叉树中序遍历的顺序为:
- 先递归地遍历左子树;
- 随后遍历根节点;
- 最后递归地遍历右子树。
对于任意一颗树而言,前序遍历的形式总是:
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是:
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
看题解后
方法一:递归
- 执行用时:2 ms, 在所有 Java 提交中击败了99.23%的用户
- 内存消耗:38.8 MB, 在所有 Java 提交中击败了34.19%的用户
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 将中序遍历的数组加入集合中,方便查找根节点
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return myTree(preorder, 0, preorder.length - 1, 0);
}
public TreeNode myTree(int[] preorder, int preorderLeft, int preorderRight, int inorderLeft) {
if (preorderLeft > preorderRight) {
return null;
}
// 前序遍历的左边的节点就是根节点
int preorderValue = preorder[preorderLeft];
// 获取中序遍历的根节点下标
int inorderIndex = map.get(preorderValue);
// 构造根节点
TreeNode root = new TreeNode(preorderValue);
// 根据中序遍历得到左子树的长度
int leftLength = inorderIndex - inorderLeft;
// 获取左节点
root.left = myTree(preorder, preorderLeft + 1, preorderLeft + leftLength, inorderLeft);
// 获取右节点
root.right = myTree(preorder, preorderLeft + leftLength + 1, preorderRight, inorderIndex + 1);
return root;
}
}
代码优化:
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 将中序遍历的数组加入集合中,方便查找根节点
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
this.preorder = preorder;
return myTree(0, 0, preorder.length - 1);
}
// root == preorderLeft,left == inorderLeft,right == preorderRight
public TreeNode myTree(int root, int left, int right) {
if (left > right) {
return null;
}
// 获取中序遍历的根节点下标
int inorderIndex = map.get(preorder[root]);
// 构造根节点
TreeNode node = new TreeNode(preorder[root]);
// 获取左节点
node.left = myTree(root + 1, left, inorderIndex - 1);
// 获取右节点
node.right = myTree(inorderIndex - left + root + 1, inorderIndex + 1, right);
return node;
}
}
最好理解的代码:
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int[] preorder;
int preorderIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 将中序遍历的数组加入集合中,方便查找根节点
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
this.preorder = preorder;
preorderIndex = 0;
return myTree(0, preorder.length - 1);
}
public TreeNode myTree(int inorderLeft, int inorderRight) {
if (inorderLeft > inorderRight) {
return null;
}
// 前序遍历的左边的节点就是根节点
int preorderValue = preorder[preorderIndex++];
// 获取中序遍历的根节点下标
int inorderIndex = map.get(preorderValue);
// 构造根节点
TreeNode root = new TreeNode(preorderValue);
// 获取左节点
root.left = myTree(inorderLeft, inorderIndex - 1);
// 获取右节点
root.right = myTree(inorderIndex + 1, inorderRight);
return root;
}
}
方法二:迭代
前序遍历,从根节点 root
开始,只要有左子节点,就一直会往左下方走,直到最左下角。 而中序遍历,是从最左下角往上,如果碰到节点有右子节点,则会转向。因此,代码中的 if
块是用前序数组一直构建左子树,如果碰到了 inorder[inorderIndex]
,表示到了左下角,这时就需要往上走并处理右子树,也就是 while
代码块。
- 执行用时:2 ms, 在所有 Java 提交中击败了99.23%的用户
- 内存消耗:38.1 MB, 在所有 Java 提交中击败了96.95%的用户
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
// 定义根节点
TreeNode root = new TreeNode(preorder[0]);
// 使用双向队列模拟栈
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
// 记录中序遍历的下标
int inorderIndex = 0;
for (int i = 1; i < preorder.length; i++) {
// 获取当前的根节点
int preorderValue = preorder[i];
// 查看栈顶元素
TreeNode node = stack.peek();
// 判断 preorderValue 是 node 的左节点还是右节点
// 如果栈顶节点不是当前左叶子节点
if (node.val != inorder[inorderIndex]) {
// 构建左子树,直到左叶子节点为止
node.left = new TreeNode(preorderValue);
stack.push(node.left);
} else {
// 移动
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
// 添加右节点
node.right = new TreeNode(preorderValue);
stack.push(node.right);
}
}
return root;
}
}
从中序与后序遍历序列构造二叉树
看题解后
方法一:递归
利用后序数组从后往前遍历,从右往左构造二叉树
- 执行用时:3 ms, 在所有 Java 提交中击败了67.42%的用户
- 内存消耗:38.3 MB, 在所有 Java 提交中击败了85.57%的用户
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int[] postorder;
int postorderIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
this.postorder = postorder;
postorderIndex = postorder.length - 1;
return myTree(0, postorder.length - 1);
}
public TreeNode myTree(int inorderLeft, int inorderRight) {
if (inorderLeft > inorderRight) {
return null;
}
// 获取根节点的值
int value = postorder[postorderIndex--];
// 查找根节点在中序遍历的位置
int inorderIndex = map.get(value);
// 构造节点
TreeNode node = new TreeNode(value);
// 右子树
node.right = myTree(inorderIndex + 1, inorderRight);
// 左子树
node.left = myTree(inorderLeft, inorderIndex - 1);
return node;
}
}
方法二:迭代
- 执行用时:2 ms, 在所有 Java 提交中击败了98.49%的用户
- 内存消耗:37.8 MB, 在所有 Java 提交中击败了99.62%的用户
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || postorder.length == 0) {
return null;
}
int inorderIndex = inorder.length - 1;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
// 使用双端队列模拟栈
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
for (int i = postorder.length - 2; i >= 0; i--) {
// 当前节点值,判断该节点应该存放在哪里
int value = postorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
// 不相等则存放在右子树中
node.right = new TreeNode(value);
stack.push(node.right);
} else {
// 向上回溯
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex--;
}
node.left = new TreeNode(value);
stack.push(node.left);
}
}
return root;
}
}
根据前序和后序遍历构造二叉树
看题解后
前序遍历为:[根节点, [前序遍历左分支], [前序遍历右分支]]
后序遍历为:[[后序遍历左分支], [后序遍历右分支], 根节点]
方法一:递归
根节点为 pre[preLeft]
,并且它在后序中的位置为 postRight
,因此这里我们需要找到能区分左右子树的节点。左子树的根节点为 pre[preLeft+1]
,因此只要找到它在后序中的位置就可以分开左右子树。
- 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:37.7 MB, 在所有 Java 提交中击败了92.88%的用户
class Solution {
int[] pre;
int[] post;
public TreeNode constructFromPrePost(int[] pre, int[] post) {
this.pre = pre;
this.post = post;
return helper(0, pre.length - 1, 0, post.length - 1);
}
public TreeNode helper(int preLeft, int preRight, int postLeft, int postRight) {
if (preLeft > preRight || postLeft > postRight) {
return null;
}
TreeNode root = new TreeNode(pre[preLeft]);
if (preLeft == preRight) {
return root;
}
int index = postLeft;
while (post[index] != pre[preLeft + 1]) {
index++;
}
// 左子树节点的个数
int count = index - postLeft;
root.left = helper(preLeft + 1, preLeft + 1 + count, postLeft, index);
root.right = helper(preLeft + 2 + count, preRight, index + 1, preRight - 1);
return root;
}
}
09. 用两个栈实现队列
自己的想法
方法一:一个入,一个出
class CQueue {
// 用来装入
Deque<Integer> in;
// 用来取出
Deque<Integer> out;
public CQueue() {
in = new LinkedList<>();
out = new LinkedList<>();
}
public void appendTail(int value) {
while (out.size() != 0) {
in.push(out.pop());
}
in.push(value);
}
public int deleteHead() {
while (in.size() != 0) {
out.push(in.pop());
}
return out.size() != 0 ? out.pop() : -1;
}
}
方法二:只在删除做处理
class CQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if(stack2.isEmpty()){
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()){
stack2.add(stack1.pop());
}
return stack2.pop();
}else {
return stack2.pop();
}
}
}
用队列实现栈
看题解后
方法一:两个队列
class MyStack {
Queue<Integer> in;
Queue<Integer> out;
/** Initialize your data structure here. */
public MyStack() {
in = new LinkedList<>();
out = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
in.offer(x);
while(out.size() != 0) {
in.offer(out.poll());
}
while(in.size() != 0) {
out.offer(in.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return out.poll();
}
/** Get the top element. */
public int top() {
return out.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return out.isEmpty();
}
}
方法二:一个队列
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
// 获取队列的长度
int size = queue.size();
queue.offer(x);
while(size-- != 0) {
queue.offer(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
10- I. 斐波那契数列
自己的想法
方法一:递归(超时)
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return (fib(n - 1) + fib(n - 2)) % 1000000007;
}
}
方法二:动态规划
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int a = 0, b = 1;
while (n >= 2) {
int c = (a + b) % 1000000007;
a = b;
b = c;
n--;
}
return b;
}
}
10- II. 青蛙跳台阶问题
自己的想法
方法一:动态规划
class Solution {
public int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
int a = 1, b = 1;
while (n >= 2) {
int c = (a + b) % 1000000007;
a = b;
b = c;
n--;
}
return b;
}
}
11. 旋转数组的最小数字
看题解后
方法一:二分查找
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.4 MB, 在所有 Java 提交中击败了27.24%的用户
class Solution {
public int minArray(int[] numbers) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int mid = (left + right) >>> 1;
// 如果中间的数小于右边的数
if (numbers[mid] < numbers[right]) {
right = mid;
} else if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else {
// 它们的值相同,所以无论 numbers[right] 是不是最小值,都有一个它的「替代品」numbers[mid],因此我们可以忽略二分查找区间的右端点。
right--;
}
}
return numbers[left];
}
}
12. 矩阵中的路径
自己的想法
方法一:DFS
- 执行用时:6 ms, 在所有 Java 提交中击败了65.95%的用户
- 内存消耗:40.6 MB, 在所有 Java 提交中击败了7.57%的用户
class Solution {
int n;
int m;
public boolean exist(char[][] board, String word) {
n = board.length;
m = board[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (is(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
public boolean is(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) {
return true;
}
// 越界、判断字符是否可用或字符不相等
if (i < 0 || i == n || j < 0 || j == m || board[i][j] != word.charAt(index)) {
return false;
}
board[i][j] = '\0';
if (is(board, word, i + 1, j, index + 1)
|| is(board, word, i, j + 1, index + 1)
|| is(board, word, i - 1, j, index + 1)
|| is(board, word, i, j - 1, index + 1)) {
return true;
}
board[i][j] = word.charAt(index);
return false;
}
}
13. 机器人的运动范围
自己的想法
方法一:DFS
从(0,0)出发,只用往右和下走,不用往左和上走。
- 执行用时:1 ms, 在所有 Java 提交中击败了84.01%的用户
- 内存消耗:35.5 MB, 在所有 Java 提交中击败了52.19%的用户
class Solution {
int m;
int n;
boolean[][] is;
public int movingCount(int m, int n, int k) {
this.m = m;
this.n = n;
is = new boolean[m][n];
return dfs(0, 0, k);
}
public int dfs(int i, int j, int k) {
// 不满足要求则结束
if (i < 0 || i == m || j < 0 || j == n || is[i][j] || is(i, j, k)) {
return 0;
}
is[i][j] = true;
// 只用向右和向下走
return 1 + dfs(i + 1, j, k) + dfs(i, j + 1, k);
}
// 不满足要求返回true
public boolean is(int i, int j, int k) {
int sum = 0;
while (i != 0) {
sum += i % 10;
i /= 10;
}
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum > k;
}
}
优化计算行列坐标的数位之和
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.3 MB, 在所有 Java 提交中击败了83.12%的用户
class Solution {
int m;
int n;
int k;
boolean[][] is;
public int movingCount(int m, int n, int k) {
this.k = k;
this.m = m;
this.n = n;
is = new boolean[m][n];
return dfs(0, 0, 0, 0);
}
public int dfs(int i, int j, int si, int sj) {
// 不满足要求则结束
if (i == m || j == n || is[i][j] || (si + sj) > k) {
return 0;
}
is[i][j] = true;
// 只用向右和向下走
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
}
}
方法二:BFS
- 执行用时:7 ms, 在所有 Java 提交中击败了13.10%的用户
- 内存消耗:37.6 MB, 在所有 Java 提交中击败了7.30%的用户
class Solution {
public int movingCount(int m, int n, int k) {
int count = 0;
boolean[][] is = new boolean[m][n];
Deque<int[]> stack = new LinkedList<>();
stack.push(new int[]{0, 0, 0, 0});
while (stack.size() != 0) {
// 取出栈顶元素
int[] array = stack.pop();
// 判断是否合法
if (array[0] == m || array[1] == n || is[array[0]][array[1]] || (array[2] + array[3]) > k) {
continue;
}
is[array[0]][array[1]] = true;
count++;
stack.push(new int[]{array[0] + 1, array[1], (array[0] + 1) % 10 != 0 ? array[2] + 1 : array[2] - 8, array[3]});
stack.push(new int[]{array[0], array[1] + 1, array[2], (array[1] + 1) % 10 != 0 ? array[3] + 1 : array[3] - 8});
}
return count;
}
}
14- I. 剪绳子
看题解后
方法一:动态规划
- 执行用时:1 ms, 在所有 Java 提交中击败了45.32%的用户
- 内存消耗:35.4 MB, 在所有 Java 提交中击败了18.05%的用户
class Solution {
public int cuttingRope(int n) {
// 因为最少分为两段
if (n <= 3) {
return 1 * (n - 1);
}
// 指定长度的最大值
int[] dp = new int[n + 1];
// 3 以下的绳子不需要拆分,拆分反而变小
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// 长度为 i
for (int i = 4; i <= n; i++) {
// 拆分的长度,循环一半向上取整即可
for (int j = 1; j < i / 2 + 1; j++) {
dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
}
}
return dp[n];
}
}
方法二:贪心
将 n 切分为多块。
假如 ni >= 5,拆分出一个3
3 * (ni - 3) >= ni
3ni - 9 >= ni
2ni >= 9 因为 ni 大于 5,所以成立
当ni == 4,拆分为 4 = 2 * 2
因为 2 * 2 * 2 < 3 * 3
所以拆分的线段只有 2 和 3,且 2 的个数最多为两个
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.5 MB, 在所有 Java 提交中击败了10.67%的用户
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return 1 * (n - 1);
}
int res = 1;
if (n % 3 == 1) {
n -= 4;
res *= 4;
} else if (n % 3 == 2) {
n -= 2;
res *= 2;
}
return (int) (res * Math.pow(3, n / 3));
}
}
14- II. 剪绳子 II
自己的想法
方法一: 贪心
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.3 MB, 在所有 Java 提交中击败了34.61%的用户
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return 1 * (n - 1);
}
int res = 1;
if (n % 3 == 1) {
n -= 4;
res *= 4;
} else if (n % 3 == 2) {
n -= 2;
res *= 2;
}
int count = n / 3;
long a = 1;
for (int i = 0; i < count; i++) {
a = (a * 3) % 1000000007;
}
return (int) (res * a % 1000000007);
}
}
方法二:快速幂
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.3 MB, 在所有 Java 提交中击败了34.61%的用户
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return 1 * (n - 1);
}
int res = 1;
if (n % 3 == 1) {
n -= 4;
res *= 4;
} else if (n % 3 == 2) {
n -= 2;
res *= 2;
}
return (int) (res * myPow(3, n / 3) % 1000000007);
}
public long myPow(long x, int b) {
long res = 1;
while (b != 0) {
// 如果当前位为1,则进行乘
if ((b & 1) == 1) {
res = res * x % 1000000007;
}
x = x * x % 1000000007;
b >>= 1;
}
return res;
}
}
15. 二进制中1的个数
自己的想法
方法一:逐位判断
因为可能是负数,所有需要无符号右移(>>>)。
- 执行用时:1 ms, 在所有 Java 提交中击败了96.63%的用户
- 内存消耗:35.6 MB, 在所有 Java 提交中击败了10.44%的用户
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
// 判断最右比特位是否为 1
if ((n & 1) == 1) {
count++;
}
n >>>= 1;
}
return count;
}
}
看题解后
代码优化
class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}
}
方法二:n & (n−1)
每次 n&(n-1) 可以消除最右的1。
n = 10101000
n-1 = 10100111
n&(n-1) = 10100000
- 执行用时:1 ms, 在所有 Java 提交中击败了96.63%的用户
- 内存消耗:35.5 MB, 在所有 Java 提交中击败了18.84%的用户
class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count ++;
}
return count;
}
}
16. 数值的整数次方
自己的想法
方法一:暴力破解(超时)
class Solution {
public double myPow(double x, int n) {
double result;
if (n >= 0) {
result = 1;
while (n-- != 0) {
result *= x;
}
} else {
// n 小于 0 时
result = x;
n = -n;
while (--n != 0) {
result *= x;
}
result = 1 / result;
}
return result;
}
}
看题解后
方法二:快速幂(位运算)
Java 代码中 int32 变量 n∈[−2147483648,2147483647]
,因此当 n=−2147483648
时执行 n = -n
会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ,后面用 b 操作即可。
- 执行用时:1 ms, 在所有 Java 提交中击败了98.46%的用户
- 内存消耗:37.6 MB, 在所有 Java 提交中击败了62.13%的用户
class Solution {
public double myPow(double x, int n) {
double res = 1;
long b = n;
// 如果这个数为负数则进行转换
if (b < 0) {
x = 1 / x;
b = -b;
}
while(b != 0) {
// 如果当前位为1,则进行乘
if ((b & 1) == 1) {
res *= x;
}
x *= x;
b >>= 1;
}
return res;
}
}
方法三:快速幂(二分)
二分推导: $x^n = x^{n/2} * x^{n/2} = (x^2)^{n/2}$ ,令 n/2 为整数,则需要分为奇偶两种情况:
当 n 为偶数:$x^n = (x^2)^{n/2}$;
当 n 为奇数:$x^n = (x^2)^{n/2}$,即会多出一项 x;
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.1 MB, 在所有 Java 提交中击败了5.00%的用户
class Solution {
public double myPow(double x, int n) {
//当 n = 0 时,返回 1
if(n == 0){
return 1;
}else if(n < 0){
// 当 n < 0 时,返回 1/ x^(-n), 为了防止越界,所以需要-1
return 1 / (x * myPow(x, - n - 1));
}else if(n % 2 == 1){
// 为避免越界,提取 x
return x * myPow(x, n - 1);
}else{
return myPow(x * x, n / 2);
}
}
}
17. 打印从1到最大的n位数
自己的想法
方法一:暴力
- 执行用时:1 ms, 在所有 Java 提交中击败了99.99%的用户
- 内存消耗:46.8 MB, 在所有 Java 提交中击败了27.88%的用户
class Solution {
public int[] printNumbers(int n) {
int l = (int)Math.pow(10, n) - 1;
int[] res = new int[l];
for (int i = 0; i < l; i++) {
res[i] = i + 1;
}
return res;
}
}
方法二:大数
- 执行用时:8 ms, 在所有 Java 提交中击败了15.98%的用户
- 内存消耗:46.7 MB, 在所有 Java 提交中击败了51.46%的用户
class Solution {
// 结果集
int[] res;
// index 表示结果集的下标,n 表示数的位数
int index, n;
// 用于拼接字符串
char[] num;
public int[] printNumbers(int n) {
this.n = n;
// 计算数的个数
res = new int[(int) Math.pow(10, n) - 1];
num = new char[n];
// 从第一位开始构造
dfs(0);
return res;
}
void dfs(int x) {
// 构造完毕,开始生成字符
if (x == n) {
int value = Integer.parseInt(String.valueOf(num));
// 如果不为 0,则添加
if (value != 0) {
res[index++] = value;
}
return;
}
// 全排列
for (char i = '0'; i <= '9'; i++) {
num[x] = i;
dfs(x + 1);
}
}
}
18. 删除链表的节点
自己的想法
方法一:
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:37.8 MB, 在所有 Java 提交中击败了64.47%的用户
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
// 删除头节点
if (head.val == val) {
return head.next;
}
ListNode node = head;
while (node.next != null) {
if (node.next.val == val) {
node.next = node.next.next;
break;
}
node = node.next;
}
return head;
}
}
19. 正则表达式匹配
看题解后
方法一:动态规划
- 执行用时:4 ms, 在所有 Java 提交中击败了69.50%的用户
- 内存消耗:38.5 MB, 在所有 Java 提交中击败了17.66%的用户
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// dp[0][0] 代表 s 和 p 均为空字符串,dp[1][1] 代表 s 和 p 的第一个字符(即在 s 和 p 中下标为 0 的字符)
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// p 的第 j 个字符为 *
if (p.charAt(j - 1) == '*') {
// 匹配 s 的第 i 个字符和 p 的第 j-1 个字符
if (matches(s, p, i, j - 1)) {
// p 中 * 前面的字符在 s 中出现多次或者在 s 中只出现 1 次
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
// p 中 * 前面的在 s 中字符出现 0 次
dp[i][j] = dp[i][j - 2];
}
} else {
// p 的第 j 个字符不为 *
// 匹配 s 的第 i 个字符和 p 的第 j 个字符
if (matches(s, p, i, j)) {
// 匹配成功,状态转移;匹配不成功,默认是false
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
private boolean matches(String s, String p, int i, int j) {
// 注意在字符串中的下标变换,0 表示没有字符
if (i == 0) {
return false;
}
// 如果当前匹配为 . 则通过
if (p.charAt(j - 1) == '.') {
return true;
}
// 否则判断字符是否相等
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
20. 表示数值的字符串
看题解后
方法一:有限状态自动机
字符类型:空格「 」、数字「 0—9」、正负号「 +− 」、小数点「 . 」 、幂符号「 eE 」。
按照字符串从左到右的顺序,定义以下 9 种状态:(合法的结束状态有 2, 3, 7, 8 )
- 开始的空格
- 幂符号前的正负号
- 小数点前的数字
- 小数点、小数点后的数字
- 当小数点前为空格时,小数点、小数点后的数字
- 幂符号
- 幂符号后的正负号
- 幂符号后的数字
- 结尾的空格
- 执行用时:7 ms, 在所有 Java 提交中击败了41.02%的用户
- 内存消耗:38.5 MB, 在所有 Java 提交中击败了57.39%的用户
class Solution {
public boolean isNumber(String s) {
Map[] states = {
new HashMap<Character,Integer>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
new HashMap<Character,Integer>() {{ put('d', 2); put('.', 4); }}, // 1.
new HashMap<Character,Integer>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
new HashMap<Character,Integer>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
new HashMap<Character,Integer>() {{ put('d', 3); }}, // 4.
new HashMap<Character,Integer>() {{ put('s', 6); put('d', 7); }}, // 5.
new HashMap<Character,Integer>() {{ put('d', 7); }}, // 6.
new HashMap<Character,Integer>() {{ put('d', 7); put(' ', 8); }}, // 7.
new HashMap<Character,Integer>() {{ put(' ', 8); }} // 8.
};
int p = 0;
char t;
for (char c : s.toCharArray()) {
if (c >= '0' && c <= '9') {
t = 'd';
} else if (c == '+' || c == '-') {
t = 's';
} else if (c == 'e' || c == 'E') {
t = 'e';
} else if (c == '.' || c == ' ') {
t = c;
} else {
t = '?';
}
if (!states[p].containsKey(t)) {
return false;
}
p = (int) states[p].get(t);
}
return p == 2 || p == 3 || p == 7 || p == 8;
}
}
21. 调整数组顺序使奇数位于偶数前面
自己的想法
方法一:首尾双指针
首尾两个指针,左边的指针指向奇数,右边的指针指向偶数。移动左指针,当左边指针指向了偶数,则和右边的指针指向的数进行互换,并移动右指针。
- 执行用时:2 ms, 在所有 Java 提交中击败了98.18%的用户
- 内存消耗:46.2 MB, 在所有 Java 提交中击败了75.79%的用户
class Solution {
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// 等于偶数则互换,位运算判偶
if ((nums[left] & 1) == 0) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
right--;
} else {
left++;
}
}
return nums;
}
}
看题解后
方法二:快慢双指针(能保证数组原顺序)
快慢两个指针,慢指针指向奇数,快指针指向时偶数。移动快指针,当快指针指向了奇数,则和慢指针指向的数进行互换,并移动慢指针。
- 执行用时:2 ms, 在所有 Java 提交中击败了98.18%的用户
- 内存消耗:46.4 MB, 在所有 Java 提交中击败了51.89%的用户
class Solution {
public int[] exchange(int[] nums) {
int low = 0, fast = 0;
while (fast < nums.length) {
// 奇数则互换
if ((nums[fast] & 1) == 1) {
int tmp = nums[low];
nums[low] = nums[fast];
nums[fast] = tmp;
low++;
}
fast++;
}
return nums;
}
}
22. 链表中倒数第k个节点
自己的想法
方法一:快慢指针
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:36.5 MB, 在所有 Java 提交中击败了16.87%的用户
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// 快慢指针
ListNode start = head, end = head;
// 移动快指针
while (k-- != 0) {
end = end.next;
}
while (end != null) {
start = start.next;
end = end.next;
}
return start;
}
}
24. 反转链表
自己的想法
方法一:使用栈
- 执行用时:1 ms, 在所有 Java 提交中击败了5.78%的用户
- 内存消耗:38 MB, 在所有 Java 提交中击败了82.31%的用户
class Solution {
public ListNode reverseList(ListNode head) {
Deque<ListNode> stack = new LinkedList<>();
// 先将节点压入栈
while (head != null) {
stack.push(head);
head = head.next;
}
ListNode root = new ListNode();
// 中间节点
ListNode node = root;
while (stack.size() != 0) {
node.next = stack.pop();
node = node.next;
}
// 消除环
node.next = null;
return root.next;
}
}
看题解后
方法二:递归
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.5 MB, 在所有 Java 提交中击败了11.01%的用户
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 获取最后的节点
ListNode node = reverseList(head.next);
// 将下一个节点指向当前节点
head.next.next = head;
// 防止环
head.next = null;
return node;
}
}
方法三:迭代
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.3 MB, 在所有 Java 提交中击败了37.38%的用户
class Solution {
public ListNode reverseList(ListNode head) {
// 记录当前节点和前节点
ListNode node = head;
ListNode front = null;
while (node != null) {
// 取出下一个节点
ListNode next = node.next;
// 将当前节点指向前一个节点
node.next = front;
// 重定向前节点和当前节点
front = node;
node = next;
}
return front;
}
}
25. 合并两个排序的链表
自己的想法
方法一:归并排序
- 执行用时:1 ms, 在所有 Java 提交中击败了99.31%的用户
- 内存消耗:38.7 MB, 在所有 Java 提交中击败了28.42%的用户
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 结果集
ListNode node = new ListNode();
ListNode root = node;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
// 处理剩下的节点
node.next = l1 != null ? l1 : l2;
return root.next;
}
}
26. 树的子结构
自己的想法
方法一:层次遍历
- 执行用时:4 ms, 在所有 Java 提交中击败了5.96%的用户
- 内存消耗:40.6 MB, 在所有 Java 提交中击败了5.10%的用户
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
// 层次遍历
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(A);
while (queue.size() != 0) {
TreeNode node = queue.poll();
if (node.val == B.val) {
if (isEques(node, B)) {
return true;
}
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return false;
}
// 判断两个树是否相等
public boolean isEques(TreeNode A, TreeNode B) {
if (B == null) {
return true;
} else if (A == null) {
return false;
} else {
// 两个都不为 null,则判断当前值和其子树
return A.val == B.val && isEques(A.left, B.left) && isEques(A.right, B.right);
}
}
}
看题解后
方法二:先序遍历
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:40.2 MB, 在所有 Java 提交中击败了49.38%的用户
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
// 先序遍历
return isEquals(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
// 判断两个树是否相等
public boolean isEquals(TreeNode A, TreeNode B) {
if (B == null) {
return true;
} else if (A == null) {
return false;
} else {
// 两个都不为 null,则判断当前值和其子树
return A.val == B.val && isEquals(A.left, B.left) && isEquals(A.right, B.right);
}
}
}
27. 二叉树的镜像
看题解后
方法一:递归
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.7 MB, 在所有 Java 提交中击败了79.84%的用户
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = mirrorTree(root.right);
TreeNode right = mirrorTree(root.left);
root.left = left;
root.right = right;
return root;
}
}
方法二:层次遍历
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.8 MB, 在所有 Java 提交中击败了46.82%的用户
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 交换其左右子节点
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
28. 对称的二叉树
看题解后
方法一:递归
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:36.4 MB, 在所有 Java 提交中击败了59.71%的用户
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isEquals(root.left, root.right);
}
public boolean isEquals(TreeNode A, TreeNode B) {
if (A == null && B == null) {
return true;
}
if (A == null || B == null) {
return false;
}
return A.val == B.val && isEquals(A.left, B.right) && isEquals(A.right, B.left);
}
}
29. 顺时针打印矩阵
自己的想法
方法一:模拟
- 执行用时:3 ms, 在所有 Java 提交中击败了20.79%的用户
- 内存消耗:39.9 MB, 在所有 Java 提交中击败了29.39%的用户
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return new int[0];
}
// 用来防止越界
int n = matrix.length, m = matrix[0].length;
// 计算矩阵中数的个数
int length = n * m;
// 结果集
int[] result = new int[length];
// 移动的下标
int i = 0, j = 0;
// 用来控制移动的方向
int[][] move = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 控制 move 的下标
int mv = 0;
// 记录走过的下标
boolean[][] is = new boolean[n][m];
for (int index = 0; index < length; index++) {
// 存储当前数
result[index] = matrix[i][j];
is[i][j] = true;
// 移动下标
i += move[mv][0];
j += move[mv][1];
if (i < 0 || i == n || j < 0 || j == m || is[i][j]) {
// 如果下标不合法,则返回
i -= move[mv][0];
j -= move[mv][1];
mv = (mv + 1) % 4;
// 然后转向
i += move[mv][0];
j += move[mv][1];
}
}
return result;
}
}
方法二:模拟
使用一个 while 套 4 个 for。
- 执行用时:1 ms, 在所有 Java 提交中击败了97.57%的用户
- 内存消耗:39.7 MB, 在所有 Java 提交中击败了64.01%的用户
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
// 最大下标
int n = matrix.length - 1, m = matrix[0].length - 1;
// 移动的下标,存储下标
int i = 0, j = 0, index = 0;
// 结果集
int[] result = new int[(n + 1) * (m + 1)];
while (i <= n && j <= m) {
// 往右走
for (int z = j; z <= m; z++) {
result[index++] = matrix[i][z];
}
i++;
// 判断是否越界
if (i > n) {
break;
}
// 往下走
for (int z = i; z <= n; z++) {
result[index++] = matrix[z][m];
}
m--;
if (j > m) {
break;
}
// 往左走
for (int z = m; z >= j; z--) {
result[index++] = matrix[n][z];
}
n--;
// 往上走
for (int z = n; z >= i; z--) {
result[index++] = matrix[z][j];
}
j++;
}
return result;
}
}
30. 包含min函数的栈
看题解后
方法一:
创建一个栈用于存储最小值,在任意一个时刻,栈内元素的最小值就存储在该栈的栈顶。
- 每次添加元素时,和这个栈顶元素做比较,小于等于则存储。
- 每次弹出元素时,和这个栈顶元素做比较,等于则也将该栈中的元素弹出。
top() 方法和 peek() 方法作用一样。
- 执行用时:21 ms, 在所有 Java 提交中击败了99.24%的用户
- 内存消耗:40.2 MB, 在所有 Java 提交中击败了79.89%的用户
class MinStack {
// 维护两个栈一个栈存储元素,一个栈存储较小的数
Deque<Integer> stack;
Deque<Integer> min;
public MinStack() {
stack = new LinkedList<>();
min = new LinkedList<>();
}
public void push(int x) {
stack.push(x);
if (min.size() == 0 || min.peek() >= x) {
min.push(x);
}
}
public void pop() {
// Integer 引用类型使用 equals 比较
if (min.peek().equals(stack.pop())) {
min.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return min.peek();
}
}
31. 栈的压入、弹出序列
看题解后
方法一:模拟栈
- 执行用时:3 ms, 在所有 Java 提交中击败了36.93%的用户
- 内存消耗:38 MB, 在所有 Java 提交中击败了85.18%的用户
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<>();
int i = 0;
// 将当前数组的所有的数据入栈
for (int value : pushed) {
stack.push(value);
// 如果栈不为空,则判断和 popped[i] 是否相等
while (stack.size() != 0 && stack.peek() == popped[i]) {
// 不相等则弹出
stack.pop();
i++;
}
}
// 遍历完,则成立
return i == pushed.length;
}
}
方法二:双指针
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.2 MB, 在所有 Java 提交中击败了45.39%的用户
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// i 指向 pushed,j 指向 popped
int i = 0, j = 0;
// pushed 数组不会改变,改变的只是下表 i
for (int num : pushed) {
// 覆盖值
pushed[i] = num;
while (i >= 0 && pushed[i] == popped[j]) {
j++;
i--;
}
// 如果此时不等于 pop 指针指到的值
i++;
}
return i == 0;
}
}
32 - I. 从上到下打印二叉树
自己的想法
方法一:层次遍历
- 执行用时:1 ms, 在所有 Java 提交中击败了99.71%的用户
- 内存消耗:38.6 MB, 在所有 Java 提交中击败了55.00%的用户
class Solution {
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.size() != 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
int[] array = new int[list.size()];
for (int i = 0; i < array.length; i++) {
array[i] = list.get(i);
}
return array;
}
}
32 - II. 从上到下打印二叉树 II
看题解后
方法一:按层遍历(迭代)
- 执行用时:1 ms, 在所有 Java 提交中击败了94.79%的用户
- 内存消耗:38.6 MB, 在所有 Java 提交中击败了61.40%的用户
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) {
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.size() != 0) {
List<Integer> list = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
lists.add(list);
}
return lists;
}
}
方法二:先序遍历(递归)
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.6 MB, 在所有 Java 提交中击败了60.82%的用户
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
bfs(root, 0);
return res;
}
public void bfs(TreeNode node, int level) {
if (node == null) {
return;
}
// 创建新的集合
if (res.size() == level) {
res.add(new ArrayList<>());
}
res.get(level).add(node.val);
bfs(node.left, level + 1);
bfs(node.right, level + 1);
}
}
32 - III. 从上到下打印二叉树 III
看题解后
方法一:双端队列
- 执行用时:1 ms, 在所有 Java 提交中击败了99.89%的用户
- 内存消耗:38.5 MB, 在所有 Java 提交中击败了79.41%的用户
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) {
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.size() != 0) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
// 偶数正常
if ((lists.size() & 1) == 0) {
list.addLast(node.val);
} else {
list.addFirst(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
lists.add(list);
}
return lists;
}
}
33. 二叉搜索树的后序遍历序列
- 后序遍历定义:[ 左子树 | 右子树 | 根节点 ]。
- 二叉搜索树定义:左子树中所有节点的值 < 根节点的值;右子树中所有节点的值 > 根节点的值。
看题解后
方法一:递归
最后一个元素一定是根节点,利用二叉搜索树的性质根据根节点划分左右子树。
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.9 MB, 在所有 Java 提交中击败了45.51%的用户
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int i, int j) {
// 越界则为 true
if (i >= j) {
return true;
}
// postorder[j] 是根
int p = i;
// 小于根节点的节点都在左子树
while (postorder[p] < postorder[j]) {
p++;
}
int m = p;
// 判断剩下的节点是否都属于右子树
while (postorder[p] > postorder[j]) {
p++;
}
// 如果不属于,则结束
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
}
方法二:单调栈**(不会)**
34. 二叉树中和为某一值的路径
方法一:DFS
- 执行用时:2 ms, 在所有 Java 提交中击败了27.56%的用户
- 内存消耗:38.9 MB, 在所有 Java 提交中击败了32.34%的用户
class Solution {
List<List<Integer>> result = new ArrayList<>();
int target;
public List<List<Integer>> pathSum(TreeNode root, int target) {
this.target = target;
if (root != null) {
List<Integer> list = new LinkedList<>();
list.add(root.val);
dfs(root, list, root.val);
}
return result;
}
public void dfs(TreeNode node, List<Integer> list, int sum) {
if (sum == target) {
// 如果相等,则判断是否为根节点
if (node.left == null && node.right == null) {
result.add(new ArrayList<>(list));
}
}
// 遍历左子树
if (node.left != null) {
list.add(node.left.val);
dfs(node.left, list, sum + node.left.val);
list.remove(list.size() - 1);
}
// 遍历右子树
if (node.right != null) {
list.add(node.right.val);
dfs(node.right, list, sum + node.right.val);
list.remove(list.size() - 1);
}
}
}
看题解后
代码优化
- 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.5 MB, 在所有 Java 提交中击败了93.78%的用户
class Solution {
LinkedList<List<Integer>> result = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
recur(root, target);
return result;
}
void recur(TreeNode root, int sum) {
if (root == null) {
return;
}
path.add(root.val);
sum -= root.val;
if (sum == 0 && root.left == null && root.right == null) {
result.add(new LinkedList<>(path));
}
recur(root.left, sum);
recur(root.right, sum);
// 回溯
path.removeLast();
}
}
35. 复杂链表的复制
看题解后
方法一:拼接+拆分
构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> ……
的拼接链表,然后在通过新链表链接 Random。最后拆分两个链表,题目隐含不能破坏原链表,所以拆分时,需要恢复原链表。
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38.2 MB, 在所有 Java 提交中击败了45.05%的用户
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node node = head;
// 拼接,复制节点
while (node != null) {
// 创建新节点
Node tmp = new Node(node.val);
// 链接
tmp.next = node.next;
node.next = tmp;
node = node.next.next;
}
// 构建 Random
node = head;
while (node != null) {
if (node.random != null) {
node.next.random = node.random.next;
}
node = node.next.next;
}
// 拆分两个链表
node = head.next;
// pre 用于复原原链表,res 存储新链表
Node pre = head, res = head.next;
while (node.next != null) {
// 指向原链表
pre.next = node.next;
// 指向新建的链表
node.next = node.next.next;
node = node.next;
pre = pre.next;
}
pre.next = null;
return res;
}
}
方法二:哈希表
使用 Map 节点构造,原节点和新节点的 Map 映射。
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38 MB, 在所有 Java 提交中击败了66.28%的用户
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node node = head;
Map<Node, Node> map = new HashMap<>();
// 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
while (node != null) {
map.put(node, new Node(node.val));
node = node.next;
}
node = head;
// 构建新链表的 next 和 random 指向
while (node != null) {
map.get(node).next = map.get(node.next);
map.get(node).random = map.get(node.random);
node = node.next;
}
// 5. 返回新链表的头节点
return map.get(head);
}
}
36. 二叉搜索树与双向链表
看题解后
方法一:中序遍历
左指针指向前驱,右指针指向后继。使用 pre 记录前一个节点,head 记录最小的节点。
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:37.9 MB, 在所有 Java 提交中击败了32.30%的用户
class Solution {
// pre 记录前一个节点
Node pre, head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node node) {
if (node == null) {
return;
}
dfs(node.left);
if (pre != null) {
// 前一个节点的后继指向当前节点
pre.right = node;
} else {
// 如果 pre 为空,则表示该节点最小,则为 head
head = node;
}
// 当前节点指向前一个节点
node.left = pre;
// 更换前节点
pre = node;
dfs(node.right);
new Object();
}
}
37. 序列化二叉树
看题解后
方法一:利用层次遍历
- 执行用时:24 ms, 在所有 Java 提交中击败了60.73%的用户
- 内存消耗:40.1 MB, 在所有 Java 提交中击败了81.28%的用户
class Codec {
public String serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
// 添加当前值
res.append(node.val).append(",");
queue.add(node.left);
queue.add(node.right);
} else {
res.append("null,");
}
}
// 删除最后的逗号
res.deleteCharAt(res.length() - 1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if (data.equals("[]")) {
return null;
}
// 去掉字符串的括号,并按逗号进行拆分
String[] str = data.substring(1, data.length() - 1).split(",");
// 生成根节点
TreeNode root = new TreeNode(Integer.parseInt(str[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 如果下个不为空,则表示左节点不为空
if (!str[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(str[i]));
queue.add(node.left);
}
i++;
if (!str[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(str[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
38. 字符串的排列
自己的想法
方法一:DFS
- 执行用时:6 ms, 在所有 Java 提交中击败了99.10%的用户
- 内存消耗:42.9 MB, 在所有 Java 提交中击败了70.57%的用户
class Solution {
// 原字符串
char[] array;
// 字符串的长度
int n;
// 组成的字符串
char[] c;
// 记录那些字符使用过
boolean[] is;
// 生成的字符串
List<String> list;
public String[] permutation(String s) {
array = s.toCharArray();
n = array.length;
// 排序
Arrays.sort(array);
// 组成的字符串
c = new char[n];
// 记录那些字符使用过
is = new boolean[n];
list = new ArrayList<>();
dfs(0);
// 生成结果集
return list.toArray(new String[0]);
}
public void dfs(int index) {
if (index == n) {
list.add(new String(c));
return;
}
for (int i = 0; i < n; i++) {
// 当前字符未使用过,或前一个字符和该字符相等,而前一个字符未使用过。
if (is[i] || (i > 0 && array[i] == array[i - 1] && !is[i - 1])) {
continue;
}
is[i] = true;
c[index] = array[i];
// 递归
dfs(index + 1);
is[i] = false;
}
}
}
39. 数组中出现次数超过一半的数字
其他方法:哈希表,排序(数组中点的元素一定为众数)
看题解后
方法一:摩尔投票法
- 执行用时:1 ms, 在所有 Java 提交中击败了99.97%的用户
- 内存消耗:41.8 MB, 在所有 Java 提交中击败了55.74%的用户
class Solution {
public int majorityElement(int[] nums) {
// 记录当前数出现的次数
int count = 1;
int index = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[index]) {
count++;
} else {
// 如果之前的数被清空,则重新初始化
if (--count == 0) {
index = i;
count = 1;
}
}
}
return nums[index];
}
}
代码简化:
class Solution {
public int majorityElement(int[] nums) {
// 众数为 value,票数为 count
int value = 0, count = 0;
for (int num : nums) {
if (count == 0) {
value = num;
}
count += num == value ? 1 : -1;
}
return value;
}
}
方法二:位运算
在 java 中 int 类型是 32 位的,我们只需要判断所有数字在某一位 1 的个数大于数组长度的一半,那么众数在这个位置肯定就是 1,我们需要遍历 32 次,确定这个众数每个位置是 0 还是 1。
- 执行用时:15 ms, 在所有 Java 提交中击败了22.74%的用户
- 内存消耗:41.5 MB, 在所有 Java 提交中击败了89.89%的用户
class Solution {
public int majorityElement(int[] nums) {
int result = 0;
int length = nums.length;
// 在 java 中 int 类型是 32 位,我们遍历每一位
for (int i = 0, bit = 1; i < 32; i++, bit <<= 1) {
// bitCounts 表示所有数字在 i 位置 1 的个数
int bitCounts = 0;
for (int num : nums) {
//判断数字 num 的第 i 位置是否为 1
if ((num & bit) == bit) {
// 如果是 1,bitCounts 就加1
bitCounts++;
}
// 如果 bitCounts 大于数组的一半,那么众数这个位置肯定是 1,然后通过 result |= bit 运算
if (bitCounts > length / 2) {
result |= bit;
break;
}
}
}
return result;
}
}
40. 最小的k个数
看题解后
方法一:快排
找前 K 大/前 K 小的问题不需要对整个数组进行 O(nlogn) 的排序,直接通过快排切分排好第 K 小的数(下标为 K-1)。
- 执行用时:2 ms, 在所有 Java 提交中击败了99.60%的用户
- 内存消耗:39.4 MB, 在所有 Java 提交中击败了94.82%的用户
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 最后一个参数表示我们要找的是下标为 k-1 的数
return quickSearch(arr, 0, arr.length - 1, k - 1);
}
private int[] quickSearch(int[] nums, int left, int right, int k) {
// 每快排切分 1 次,找到排序后下标为 j 的元素
int j = partition(nums, left, right);
// 如果 j 恰好等于 k 就返回 j 以及 j 左边所有的数;
if (j == k) {
return Arrays.copyOf(nums, j + 1);
}
// 否则根据下标 j 与 k 的大小关系来决定继续切分左段还是右段。
return j > k ? quickSearch(nums, left, j - 1, k) : quickSearch(nums, j + 1, right, k);
}
// 快排切分,返回下标 j,使得比 nums[j] 小的数都在 j 的左边,比 nums[j] 大的数都在 j 的右边。
private int partition(int[] nums, int left, int right) {
int value = nums[left];
int start = left + 1, end = right;
// 快排单向扫描
while (start <= end) {
if (nums[start] <= value) {
start++;
} else {
int t = nums[end];
nums[end] = nums[start];
nums[start] = t;
end--;
}
}
nums[left] = nums[end];
nums[end] = value;
return end;
}
}
方法二:大根堆(前 K 小) / 小根堆(前 K 大)
求前 K 小,用一个容量为 K 的大根堆,每次 poll 出最大的数,那堆中保留的就是前 K 小的了。(注意:不是小根堆!小根堆的话需要把全部的元素都入堆,那是 O(nlogn),就不是 O(nlogk)。
保持堆的大小为 K,然后遍历数组中的数字,遍历的时候做如下判断:
- 若目前堆的大小小于K,将当前数字放入堆中。
- 否则判断当前数字与大根堆堆顶元素的大小关系,如果当前数字比大根堆堆顶还大,这个数就直接跳过;反之如果当前数字比大根堆堆顶小,先 poll 掉堆顶,再将该数字放入堆中。
Java 中提供了现成的 PriorityQueue(默认小根堆)。
- 执行用时:14 ms, 在所有 Java 提交中击败了41.11%的用户
- 内存消耗:39.9 MB, 在所有 Java 提交中击败了24.19%的用户
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆,实现大根堆需要重写一下比较器。
Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num : arr) {
// 若目前堆的大小小于K,将当前数字放入堆中
if (queue.size() < k) {
queue.offer(num);
} else if (num < queue.peek()) {
// 反之如果当前数字比大根堆堆顶小,先poll掉堆顶,再将该数字放入堆中。
queue.poll();
queue.offer(num);
}
}
// 返回堆中的元素
int[] res = new int[queue.size()];
int index = 0;
for (int num : queue) {
res[index++] = num;
}
return res;
}
}
方法三:二叉搜索树(BST)
BST 相对于前两种方法没那么常见,但是也很简单,和大根堆的思路差不多。与前两种方法相比,BST 有一个好处是求得的前 K 大的数字是有序的。
因为有重复的数字,所以用的是 TreeMap 而不是 TreeSet。TreeMap 的 key 是数字,value 是该数字的个数。我们遍历数组中的数字,维护一个数字总个数为 K 的 TreeMap:
- 若目前 map 中数字个数小于 K,则将 map 中当前数字对应的个数 +1;
- 否则,判断当前数字与 map 中最大的数字的大小关系:若当前数字大于等于 map 中的最大数字,就直接跳过该数字;若当前数字小于 map 中的最大数字,则将 map 中当前数字对应的个数 +1,并将 map 中最大数字对应的个数减 1。
- 执行用时:33 ms, 在所有 Java 提交中击败了10.99%的用户
- 内存消耗:39.4 MB, 在所有 Java 提交中击败了94.54%的用户
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// TreeMap 的 key 是数字, value 是该数字的个数。
TreeMap<Integer, Integer> map = new TreeMap<>();
// count 表示当前 map 总共存了多少个数字。
int count = 0;
for (int num : arr) {
// 遍历数组,若当前 map 中的数字个数小于 k,则 map 中当前数字对应个数 +1
if (count < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
count++;
continue;
}
// 取出map中最大的Key(即最大的数字), 判断当前数字与map中最大数字的大小关系:
Map.Entry<Integer, Integer> entry = map.lastEntry();
// 若当前数字比 map 中最大的数字小,则将当前数字加入 map 中,并将 map 中的最大数字的个数-1。
if (num < entry.getKey()) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (entry.getValue() == 1) {
map.pollLastEntry();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
}
}
// 最后返回 map 中的元素
int[] res = new int[k];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// 个数
int c = entry.getValue();
while (c-- > 0) {
res[index++] = entry.getKey();
}
}
return res;
}
}
优先队列(Priority Queue)
队列中每个元素都有一个优先级,出队的时候,优先级最高的先出。
无序数组实现方式:
- 入队:放在数组末尾O(1)。
- 出队:找最大值并移除,然后移动数组后半部分的数O(n)。
有序数组实现方式:
- 入队:插入到合适的位置,然后移动数组后半部分的数O(n)。
- 出队:删除数组最末尾元素O(1)。
二叉堆实现方式:
二叉堆是完全二叉树,除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对。特性:
- 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
- 每个节点的左子树和右子树都是一个二叉堆。
- 任意节点的值都大于等于其子节点的值——大顶堆。
- 任意节点的值都小于等于其子节点的值——小顶堆(Priority Queue)。
由于二叉堆是二叉树的扩展,所以二叉堆是由数组表示:
- 根节点存储在 a[0],然后依次按层次顺序存储。
- 查找子节点:左子节点( 2 * i + 1),右子节点( 2 * i +2 )。
- 查找父节点 :( i - 1 ) / 2。
元素入队:
- 待插入元素放在最后。
- 上浮:不符合堆规则的点与父节点交换,直到符合规则为止。
- 复杂度O(log N)。
元素出队:
- 将根出队,最后一个点换到根。
- 下浮:不符合堆规则的点与子节点中较大的交换,直到符合规则为止。
- 复杂度O(log N)。
数组中的第K个最大元素
自己的想法
方法一:小根堆(前 K 大)
使用小根堆存储前 K 大的数。
- 执行用时:5 ms, 在所有 Java 提交中击败了54.34%的用户
- 内存消耗:38.8 MB, 在所有 Java 提交中击败了43.06%的用户
class Solution {
public int findKthLargest(int[] arr, int k) {
// 默认是小根堆
Queue<Integer> queue = new PriorityQueue<>();
for (int num : arr) {
// 若目前堆的大小小于K,将当前数字放入堆中
if (queue.size() < k) {
queue.offer(num);
} else if (num > queue.peek()) {
// 反之如果当前数字比大根堆堆顶大,先 poll 掉堆顶,再将该数字放入堆中。
queue.poll();
queue.offer(num);
}
}
return queue.peek();
}
}
方法二:快排
利用快排找到第 k 个最大元素,数组左边的数都大于 k,右边的数都小于 k。
- 执行用时:1 ms, 在所有 Java 提交中击败了99.21%的用户
- 内存消耗:38.7 MB, 在所有 Java 提交中击败了69.98%的用户
class Solution {
public int findKthLargest(int[] arr, int k) {
return sort(arr, 0, arr.length - 1, k - 1);
}
// 按降序排序
public int sort(int[] arr, int left, int right, int k) {
int mid = partition(arr, left, right);
if (mid == k) {
return arr[mid];
}
return mid > k ? sort(arr, left, mid - 1, k) : sort(arr, mid + 1, right, k);
}
public int partition(int[] arr, int left, int right) {
int value = arr[left];
int start = left + 1, end = right;
while (start <= end) {
if (arr[start] >= value) {
start++;
} else {
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
end--;
}
}
arr[left] = arr[end];
arr[end] = value;
return end;
}
}
41. 数据流中的中位数
看题解后
方法一:优先队列
维护两个堆,一个小顶堆,一个大顶堆。
- 小顶堆维护较大的数,这样 peek() 出来的都是最小值。
- 大顶堆维护较小的数,这样 peek() 出来的都是最大值。
注意:
int a = 5;
System.out.println(a / 3);// 1
System.out.println(a / 3.0);// 1.6666666666666667
- 执行用时:85 ms, 在所有 Java 提交中击败了55.33%的用户
- 内存消耗:49.8 MB, 在所有 Java 提交中击败了17.73%的用户
class MedianFinder {
// 定义两个优先队列,一个小顶堆,一个大顶堆
PriorityQueue<Integer> a;
PriorityQueue<Integer> b;
public MedianFinder() {
// 存储较大的数
a = new PriorityQueue<>();
// 存储较小的数
b = new PriorityQueue<>((a, b) -> b - a);
}
public void addNum(int num) {
if (a.size() != b.size()) {
// 对于一个新元素,将最小的给 b
a.offer(num);
// 最小的给 b
b.offer(a.poll());
} else {
// 对于一个新元素,将最大的给 a
b.offer(num);
// 将最大的给 a
a.offer(b.poll());
}
}
public double findMedian() {
return a.size() != b.size() ? a.peek() : (a.peek() + b.peek()) / 2.0;
}
}
42. 连续子数组的最大和
看题解后
方法一:动态规划
- 执行用时:1 ms, 在所有 Java 提交中击败了98.49%的用户
- 内存消耗:44.9 MB, 在所有 Java 提交中击败了58.34%的用户
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE, max = 0;
for (int num : nums) {
// 对于每个数都有选和不选两种
max = Math.max(max + num, num);
result = Math.max(result, max);
}
return result;
}
}
代码优化:减少一个变量。
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
// 如果之前的数和小于 0,则不选
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
43. 1~n 整数中 1 出现的次数
看题解后
方法一:
根据 cur 的值,分为三种情况
- 当 cur=0 时:此位 1 的出现次数只由高位 high 决定,计算公式为:high * digit。
如下图所示,以 n = 2304 为例,求 digit=10 (即十位)的 1 出现次数。
2 3 0 4
千位和百位可以选00 01 02....22 十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23,十位只能能取0,个位取0-4即 2300 2301 2302 2303 2304
但是2301不应该算进来,这个1是 单独 出现在个位的(而11,121,111这种可以被算多次)
即 23*10
- 当 cur=1 时:此位 1 的出现次数由高位 high 和低位 low 决定,计算公式为:high * digit + low + 1。
如下图所示,以 n = 2314 为例,求 digit=10 (即十位)的 1 出现次数。
2 3 1 4
千位和百位可以选00 01 02....22 十位可以取到1 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,十位取1,个位可以去0-4 即 2310-2314共5个
即 23 *10 + 4 +1
- 当 cur = 2, 3, ⋯,9 时: 此位 1 的出现次数只由高位 high 决定,计算公式为:(high + 1) * digit。
如下图所示,以 n = 2324 为例,求 digit=10 (即十位)的 1 出现次数。
2 3 2 4
千位和百位可以选00 01 02....22 十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,十位取1,个位可以去0-9 即 2310-2319共10个 (其中2311,被计算了两次,分别是从个位和十位分析得到的1次)
即 23 *10 + 10
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:35.2 MB, 在所有 Java 提交中击败了50.38%的用户
class Solution {
public int countDigitOne(int n) {
// 1 表示当前是个位
int digit = 1, res = 0;
// high 高位,cur 当前数,low 低位
int high = n / 10, cur = n % 10, low = 0;
while (high != 0 || cur != 0) {
// 如果个位是 0
if (cur == 0) {
res += high * digit;
} else if (cur == 1) {
res += high * digit + low + 1;
} else {
res += (high + 1) * digit;
}
// 将 cur 加入 low ,组成下轮 low
low += cur * digit;
// 下轮 cur 是本轮 high 的最低位
cur = high % 10;
// 将本轮 high 最低位删除,得到下轮 high
high /= 10;
// 位因子每轮 × 10
digit *= 10;
}
return res;
}
}
44. 数字序列中某一位的数字
看题解后
方法一:
所求数位 ① 在某个 digitdigit 位数中; ② 为从数字 startstart 开始的第 nn 个数位。
标题:剑指 offer——LeetCode
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2021/05/06/1620312198363.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!