题目
#
- 给定一个整数
n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n+1 的数组 ans 作为答案。
思路
#
右移计数
#
Brian Kernighan
#
动态规划
#
代码
#
右移计数
#
class Solution {
public int count(int num) {
int result = 0;
for (int i = 30; i >= 0; i--) {
if (((num >> i) & 1) == 1) result += 1;
}
return result;
}
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = count(i);
}
return ans;
}
}
Brian Kernighan
#
class Solution {
public int count(int num) {
int ans = 0;
while (num > 0) {
num &= num - 1;
ans += 1;
}
return ans;
}
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for(int i = 0; i <= n; i++) ans[i] = count(i);
return ans;
}
}
动态规划
#
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
int pow = 1;
for (int i = 1; i <= n; i++) {
if (i == pow) {
ans[i] = 1;
pow *= 2;
}
else {
ans[i] = 1 + ans[i - pow/2];
}
}
return ans;
}
}