[数据结构与算法]LeetCode338 比特位计数

题目

解题

解题一：Brian Kernighan 算法

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

const countOnes = (n) => {
    let countOne = 0;
    for (let i = n; i > 0; i &= (i - 1)) {
        countOne++;
    }
    return countOne;
}；

解题二：动态规划——最高有效位

// javascript
var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
};

解题三：动态规划——最低有效位

// javascript
var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
};