23.02.28 学习

$O(nlogn)$算法1，暴力统计

class Solution {
public:
    vector<int> res;

    vector<int> countBits(int n) {
        for (int i = 0; i <= n; i ++ ) {
            string num = to2jinzhi(i);
            int cnt = 0;
            for (int j = 0; j < num.size(); j ++ ) {
                if (num[j] == '1') cnt ++ ;
            }
            res.push_back(cnt);
        }

        return res;
    }

    string to2jinzhi(int x) {
        string ans = "";
        int tmp;

        while (x > 0) {
            tmp = x % 2;
            x /= 2;
            ans += to_string(tmp);
        }
        return ans;
    }
};

$O(n)$动态规划

i二进制中1的个数= (右移i-1位)的1个数 + (最后一位 & 1)

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

        return f;
    }
};