LeetCode 338 Counting Bits

云惠网小编 2021年6月17日09:32:08
评论
570字阅读1分54秒
摘要

比特位计数

题意
给定一个非负整数 num. 对于 0 ≤ i ≤ num 范围中的每个数字 i, 计算其二进制数中的 1 的数目并将它们作为数组返回.
示例 1:

12
输入: 2输出: [0,1,1]
示例 2:

12
输入: 5输出: [0,1,1,2,1,2]

阅读全文 »

广告也精彩

比特位计数

题意

给定一个非负整数 num. 对于 0 ≤ i ≤ num 范围中的每个数字 i, 计算其二进制数中的 1 的数目并将它们作为数组返回.

示例 1:

1
2
输入: 2
输出: [0,1,1]

示例 2:

1
2
输入: 5
输出: [0,1,1,2,1,2]

解法

此题是 LeetCode 191 Number of 1 Bits 的拓展版, 可以利用那道题的两种算法, 只不过套个循环, 时间和空间复杂度都是 O(n).

那两种解法就不说了. 这里说下另一种解法.

这里分为 2 的倍数非 2 的倍数 两种数.

他们有一个区别就是二进制的最低位是否为 1.

2 的倍数其二进制最低位都是 0.
非 2 的倍数其二进制最低位都是 1.

除 2 或右移一位后, 等于是去掉最低位, 那么既然 2 的倍数最后一位都是 0, 所以对于 2 的倍数 除 2 或右移一位后, 数字 1 的个数并不会变.

那么对于非 2 的倍数 n, n 肯定比 n - 1 的二进制中 1 的个数多一位. 如 n = 1111, n - 1 = 1110.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] countBits(int num) {
int[] arr = new int[num + 1];
for (int i = 0; i <= num; i++) {
if (i % 2 == 0) {
arr[i] = arr[i >> 1];
} else {
arr[i] = arr[i - 1] + 1;
}
}
return arr;
}
}

时间复杂度 O(n), 空间复杂度 O(n).

腾讯云618
云惠网小编
LeetCode 938 Range Sum of BST java

LeetCode 938 Range Sum of BST

题意 给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值. 例 : 1234567891011 给予树, L = 3, R = 8: 5 / ...
腾讯云618

发表评论