代码如下:
class Solution {
public:
vector<int> countBits(int n) {
vector<int> a(n + 1);
for(int i=0;i<=n;i++){//外循环是控制0到n的每个计算
int k=0;
int count=i;
for(int j=16;j>=0;j--){//内循环是每个具体的数字的计算
int num = 1<<j;//num=1*2的j次方
if(count>=num){
count-=num;
k++;
}
}
a[i]=k;
}
return a;
}
};
思路:通过找规律得出算法,如图:
注意在哪个位上有一中的数字代表的是位数(从1开始是最低位,2是倒数第二位)而不是1的个数,即一共有几个不同的数字就有几个1。因为每次加一的时候是加在最低位上面的,当末尾加上两个1的时候就进位到倒数第二位上所以1+1=2(表示有1加入的时候末位+末尾=倒数第二位(进一)),那如何进一到倒数第三位呢,就是倒数第二位有两个1的时候即2+2=3,以此类推可以得出规律(如上图下面一列)。(其实就像十进制的数字一样,如1000有一个10的3次方,100有一个10的2次方,110有一个10的2次方和一个10的1次方。)
所以可得算法:因为n大于等于0,小于等于10的5次方,经计算可知2的16次方小于10的5次方,10的17次方大于10的5次方。所以从2的16次方开始计算,计算n里面有几个不同的2的次方(即有几个不同的2的次方就有几个1)(因为是找不同2的次方,所以要从最大的开始到最小的)。最后将所得的每个数放入数组当中,然后返回。
官方更简洁的代码:
class Solution {
public:
vector<int> countBits(int n) {
vector<int> bits(n + 1);
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
//i>>1等价于i/2
//i&1用来判断是奇数还是偶数,如果i是奇数结果等于1,偶数等于0
}
return bits;
}
};
思路:使用动态规划
根据第一种代码后面的图片可知,对于正整数x,当他为偶数的时候他的二进制数中1的个数和x/2的二进制中1的个数一样,就相当一右移一位,等价于将其二进制的最低为去掉。当为奇数的时候就是它上一个数(偶数)加上1。