313 字
2 分钟
Leetcode->比特位计数
题目
给你一个整数 n
,对于 0 <= i <= n
中的每个 i
,计算其二进制表示中 1
的个数 ,返回一个长度为 n + 1
的数组 ans
作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
提示:
0 <= n <= 105
解题:key:
① Brian Kernighan
算法
TIP
Brian Kernighan
算法:对于任意整数 x,令 x=x & (x-1),该运算将 x 的二进制表示的最后一个 1 变成 0。因此,对 x 重复该操作,直到 x 变成 0,则操作次数即为 x的「一比特数」。
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;
}
②动态规划-最高有效位
var countBits = function(n) {
const bits = new Array(n + 1).fill(0);
// 最高有效位(小于n并且是2的整数次幂)
let highBit = 0;
for (let i = 1; i <= n; i++) {
// 利用方法1中提到的 i & (i-1)判断是否
if ((i & (i - 1)) == 0) {
// 说明i 是 2的整数次幂
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
};
Leetcode->比特位计数
https://blog.oceanh.top/posts/algorithm/比特位计数/