剑指 Offer II 003. 前n个数字二进制中1的个数 #
题目 #
- 给定一个非负整数
n，请计算0到n之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
思路 #
动态规划 #
- 令
z为与i最接近的2的幂, 则ans[i] = 1 + ans[i-z] - 问题转换为如何确定与某数最接近的
2的幂
代码 #
动态规划 #
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;
}
}