leetcode 338. 比特位计数

传送门

题解

方法一，暴力枚举

时间复杂度O(n*sizeof(integer))有个常数k的时间复杂度O(K*n);
如果用运算的lowbit函数优化，会降低一点时间复杂度降低一点k值。
lowbit 优化版，效果还行，不过不是最优解

class Solution {
public:
    vector<int> countBits(int num) {
        if (!num) return {0};
        vector<int> ans(num + 1, 0);

        for (int i = 1; i <= num; i ++ ){
            int t = i;
            int count = 0;
            while (t){
                count ++ ;
                t = t - (t & -t); // 位运算lowbit，主要就这一行代码
            }
            ans[i] = count;
        }
        return ans;
    }
};

方法二，动态规划

偶数末尾二进制表示肯定是0结尾，所以去掉这个0和原本的数中1的个数一样。
例如：
二进制数1000B和100B一样。
奇数末尾二进制表示肯定是1结尾，所以去掉这个1和原本的数中1的个数少1。
例如：
二进制数10001B和1000B个数少1。
状态转移方程为：移位运算>>快速做除法。

dp(i) = dp(i/2) 若i为偶数；

dp(i) = dp(i/2) + 1 若i为奇数；
最近比较忙，快考试了，就水一题$~$

class Solution {
public:
  vector<int> countBits(int num) {

      if (!num) return {0};
      vector<int> dp(num + 1, 0);
      dp[1] = 1;
      for (int i = 2; i <= num; i ++ ) {
          if (i & 1) dp[i] = dp[i >> 1] + 1;
          else dp[i] = dp[i >> 1];
      }
      return dp;
  }
};