比特位计数
题意
给定一个非负整数 num. 对于 0 ≤ i ≤ num 范围中的每个数字 i, 计算其二进制数中的 1 的数目并将它们作为数组返回.
示例 1:
代码语言：javascript复制输入: 2
输出: [0,1,1]示例 2:
代码语言：javascript复制输入: 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.
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).
