一、题目描述

二、解题思路

• 暴力法：逐个对数字模2，得到1的个数，装入vector，时间复杂度为$O(n\times sizeof(int))$
• 位运算法
  • >>法
    • 对一个数字，用二进制表达，比如9可以表达为1001
    • 左移1位，得到100，而100这个的结果我们在之前一定计算过，因为(n >> 1) < n恒成立
    • 但是最后还要看最低位是不是1，那就采用n & 1的方法，最低位如果是0，此式为0，否则为1
    • 得到状态转移方程：dp[i] = dp[i >> 1] + (i & 1)

    class Solution {
           
    public:
        vector<int> countBits(int num) {
           
            
            vector<int> res(num + 1, 0);
            for(int i = 1; i <= num; i++)
                res[i] = res[i >> 1] + (i & 1);
            return res;
        }
    };
    

  • &法
    • n & (n - 1)可以去掉n最低位的1（如果最低位是1）
    • n - 1的结果我们在之前计算过，所以dp[i] = dp[i & (i - 1)] + 1

    class Solution {
           
    public:
        vector<int> countBits(int num) {
           
    	vector<int> res(num + 1, 0);
        for(int i = 1; i <= num; i++)
            res[i] = res[i & (i - 1)] + 1;
        return res;
     }
    };
    

• 数字轮转法
  • 0：0
  • 1：1
  • 2~3：1,2
  • 4~7：1,2,2,3
  • 8~15：1,2,2,3,2,3,3,4
  • 16~31：1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5
  • 发现什么规律了吗？
    • 每行比上一行多出来的数据，都是上一行数据的后一半接到后面，再加上上一行数据的后一半的后一半接到后面，后一半的后一半的后一半。。。。。。。。。，直到结束，最后加上一个比上一行数据的最后一位（也就是最大位）还大1的数字
    • 发现了这个规律后，我们就可以从1开始推倒出全部的情况

class Solution {
   
public:
    vector<int> countBits(int num) {
   
        vector<int> sln;
        sln.push_back(0);
        if(!num)    return sln;
        int start = 0;
        int end = 0;
        int biggest = 0;
        int counter = 0;
        while(1){
   
            auto len = sln.size();
            start = len / 2;
            end = len - 1;
            bool flag = 0;
            while(start <= end){
   
                for(int i = start; i <= end; i++){
   
                    if(sln[start]){
   
                        sln.push_back(sln[i]);
                        counter++;
                        if(counter == num){
   
                            return sln;
                        }
                    }
                }
                if(start == end)    break;
                start = (start + end + 1) >> 1;
                
            }
            sln.push_back(++biggest);
            counter++;
            if(counter == num)
                return sln;
        }
        return sln;
};

三、运行结果

内存占用都差不多，速度上位运算能快点，但是最早通过的那次提交却是数据轮转法，最慢的那次也是，很迷。。。。。