338. Counting Bits

发布时间：2020-12-14 03:48:34 所属栏目：大数据来源：网络整理

导读：方法一：pop count 利用?191. The number of 1 bits 中的方法，算是bit manipulation 中的巧妙操作，每次 n = n(n-1) 把最低位的 1 置为 0 。时间复杂度 O(nk)，k表示数字中1的位数。 class Solution { public : vector int countBits( int num) { vector i

方法一：pop count

利用?191. The number of 1 bits 中的方法，算是bit manipulation 中的巧妙操作，每次 n = n&(n-1) 把最低位的 1 置为 0 。

时间复杂度 O(nk)，k表示数字中1的位数。

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res;
        for (int i=0;i<=num;++i){
            res.push_back(popcount(i));
        }
        return res;
    }
    
    int popcount(int n){
        int cnt=0;
        while (n!=0){
            ++cnt;
            n = n&(n-1);
        }
        return cnt;
    }
};

方法二：DP

DP方法有很多，如 dp[i] = dp[i/2] + i%2， dp[i] = dp[i & (i-1)] +1 ...

时间复杂度 O(n)

注意的是，所有位操作的优先级都比普通运算符低，因此别忘了加括号！

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!