剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/w3tCBm
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我最开始想到的方法，时间复杂度是 nk 级别的，比较直观，每次用那个数和 1 做与 运算，然后求出 1 的个数，但是题目中要求使用 n 级别的算法，于是，见下一代码：

class Solution {
public int[] countBits(int n) {
int[] result = new int[n + 1];
result[0] = 0;
for (int i = 1; i <= n; i++) {
int sum = 0;
int t = i;
while (t != 0) {
sum += t & 1;
t >>= 1;
}
result[i] = sum;
}
return result;
}
}

第二种思路：使用 i & (i - 1) 来进行求解，举个例子，比如 i 等于 8:1000，i - 1 就是 0111，二者相与的结构就是 0000，再加上 1 就是 8 的 1 个数，整数 i 的个数比 i & (i - 1) 的个数的 1 要多 1.

本题只适用于相连，有点动态规划的意思

class Solution {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 1; i <= n; i++) {
result[i] = result[i & (i - 1)] + 1;
}
return result;
}
}

最后

以上就是光亮鸵鸟为你收集整理的剑指 Offer II 003. 前 n 个数字二进制中 1 的个数的全部内容，希望文章能够帮你解决剑指 Offer II 003. 前 n 个数字二进制中 1 的个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。