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

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
代码如下:

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;
    }
};

思路:通过找规律得出算法,如图:
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
注意在哪个位上有一中的数字代表的是位数(从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;
    }
};

思路:使用动态规划
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
根据第一种代码后面的图片可知,对于正整数x,当他为偶数的时候他的二进制数中1的个数和x/2的二进制中1的个数一样,就相当一右移一位,等价于将其二进制的最低为去掉。当为奇数的时候就是它上一个数(偶数)加上1。

上一篇:快速傅里叶变换的迭代法代码实现


下一篇:【信号处理】Python实现2PSK、QPSK、8PSK、N-QAM的调制和解调