动态规划

学习官方解答

动态规划是 末尾 1 的数量 + 前面 1 的数量

res[i] = res[i >> 1] + (i & 1);

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

April 19, 2024 3:19 AM (GMT+8) Link

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i ++) {
            if (i % 2) {
                f[i] = f[i - 1] + 1;
            } else {
                f[i] = f[i / 2];
            }
        }
        return f;
    }
};

Brian Kernighan 算法

Dynamic Programming 最高有效位

Dynamic Programming 最低有效位

暴力

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res;
        for (int i = 0; i <= n; i ++) {
            res.push_back(count_number_one(i));
        }
        return res;
    }
    int count_number_one(int x) {
        int cnt = 0;
        while(x > 0) {
            if (x % 2 == 1) cnt ++;
            x /= 2;
        }
        return cnt;
    }
};