当前位置：首页 > article >正文

leetcode338. 比特位计数

article 2024/9/28 14:34:48

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

示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：

0 <= n <= 105

进阶：

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

/**
 * @param {number} n
 * @return {number[]}
 */ 
var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        bits[i] = countOnes(i);
    }
    return bits
};

const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

代码解读：
const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}
  
函数接受一个整数参数x，并返回该整数二进制表示中1的个数。

代码逻辑如下：

初始化一个变量ones为0，用于计数二进制中1的个数。
使用while循环，当x大于0时执行循环体。
在循环体中，首先对x进行按位与操作（&），将x与x - 1的结果赋值给x。这个操作的效果是将x的最低位的1变为0。例如，如果x是5（二进制表示为101），那么x - 1就是4（二进制表示为100），两者按位与的结果就是4（二进制表示为100）。
每执行一次按位与操作，就将ones加1，表示找到了一个1。
当x变为0时，说明所有的1都已经被找到并计数，此时跳出循环。
返回ones作为结果。

举个例子，如果输入的x是5（二进制表示为101），那么函数会返回2，因为有两个1。