leetcode338.比特位计数（简单）

leetcode338.比特位计数（简单）

方法一：一个数一个数枚举 ------->O(nlogn)

class Solution {
public:
    vector countBits(int n) {

        vector ans(n + 1);
        for (int i = 0; i < n + 1; ++i) {
            int tmp = i;
            while(tmp) {
                ans[i]++;
                tmp &= (tmp - 1);
            }
        }
        return ans;
    }
};

达不到O(n)…
方法二：dp ------->O(n)
具体思路：dp[i]表示i中二进制1的个数。
dp[i]=dp[i去掉最高位的1的数字]+1;

class Solution {
public:
    vector countBits(int n) {

        vector dp(n + 1);
        int high;
        for (int i = 1; i < n + 1; ++i) {
            if ((i & (i - 1)) == 0) {
                high = i;
            }
            dp[i] = dp[i - high] + 1;
        }
        return dp;
    }
};

方法三：dp------->O(n)
具体思路：dp[i]=dp[i去掉最低位的1的数字]+1;
i去掉最低位的1的数字为：i&(i - 1)

class Solution {
public:
    vector countBits(int n) {

        vector ans(n + 1);
        for (int i = 1; i < n + 1; ++i) {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }
};