比特位计数

By crabboss 2024 年 7 月 16 日

leetcode link : https://leetcode.cn/problems/counting-bits/description/?envType=problem-list-v2&envId=2cktkvj&

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

O(nlogn)解法：

1 for循环从0到n遍历数字
- 2.1 先记录余（余为1的数量就是二进制中1的个数）
- 2.2 再记录商2 对数字i进行循环除以2，记录其余和商。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> result;
        for(int i=0; i<=n; i++){
            int sum = 0;
            int j = i, k;
            while(j){
                k = j % 2;
                j = j / 2;
                sum += k;
            }
            result.push_back(sum);
        }
        return result;
    }
};

O(n)解法：

1 考虑奇偶性。
- 1.1 奇数中1的个数 = 前面偶数1的个数 + 1
- 1.2 偶数中1的个数 = 偶数/2的个数

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