Vue.js

Appearance

On this page

实战：比特位计数 ​

计算 0 到 n 每个数的二进制中 1 的个数。

问题描述 ​

LeetCode 338. Counting Bits

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

示例：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 → 0
1 → 1
2 → 10
3 → 11
4 → 100
5 → 101

解法一：逐个计算 ​

javascript
function countBits(n) {
  const result = [];
  for (let i = 0; i <= n; i++) {
    result.push(hammingWeight(i));
  }
  return result;
}

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

时间：O(n log n)

解法二：动态规划 ​

利用 n & (n-1) 清除最低位 1：

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

时间：O(n)

原理 ​

i & (i-1) 去掉最低位的 1，得到的数比 i 小，其 1 的个数已经算过了。

i = 5 = 101
i & (i-1) = 100 = 4
dp[5] = dp[4] + 1

另一种 DP 思路 ​

javascript
function countBits(n) {
  const dp = new Array(n + 1).fill(0);
  
  for (let i = 1; i <= n; i++) {
    // 右移一位 + 最低位
    dp[i] = dp[i >> 1] + (i & 1);
  }
  
  return dp;
}

i >> 1 是 i 除以 2，i & 1 是 i 的奇偶性。

两种 DP 方法对比 ​

方法递推式原理
n & (n-1)dp[i] = dp[i & (i-1)] + 1去掉最低位 1
右移dp[i] = dp[i >> 1] + (i & 1)去掉最低位（可能是 0 或 1）

两种方法时间复杂度相同，都是 O(n)。

详细执行过程 ​

以 n = 5 为例：

dp[0] = 0  (基础情况)

dp[1] = dp[1 & 0] + 1 = dp[0] + 1 = 1    或  dp[1 >> 1] + (1 & 1) = 0 + 1 = 1
dp[2] = dp[2 & 1] + 1 = dp[0] + 1 = 1    或  dp[2 >> 1] + (2 & 1) = 1 + 0 = 1
dp[3] = dp[3 & 2] + 1 = dp[2] + 1 = 2    或  dp[3 >> 1] + (3 & 1) = 1 + 1 = 2
dp[4] = dp[4 & 3] + 1 = dp[0] + 1 = 1    或  dp[4 >> 1] + (4 & 1) = 1 + 0 = 1
dp[5] = dp[5 & 4] + 1 = dp[4] + 1 = 2    或  dp[5 >> 1] + (5 & 1) = 1 + 1 = 2

结果：[0, 1, 1, 2, 1, 2]

边界情况 ​

javascript
// n = 0
countBits(0);  // [0]

// n = 1
countBits(1);  // [0, 1]

// 2 的幂
countBits(8);  // [0, 1, 1, 2, 1, 2, 2, 3, 1]
// 注意：2 的幂只有 1 个 1

常见错误 ​

错误一：DP 数组大小错误 ​

javascript
// 错误：数组大小应该是 n + 1
const dp = new Array(n).fill(0);

// 正确：包含 0 到 n
const dp = new Array(n + 1).fill(0);

错误二：使用 n & (n-1) 时忘记边界 ​

javascript
// 当 i = 0 时，i & (i-1) = 0 & (-1)
// JavaScript 中 -1 的二进制是全 1，但 0 & 任何数 = 0
// 所以 dp[0] 不会有问题，但最好从 i = 1 开始

规律观察 ​

0: 0000  →  0
1: 0001  →  1
2: 0010  →  1
3: 0011  →  2
4: 0100  →  1
5: 0101  →  2
6: 0110  →  2
7: 0111  →  3
8: 1000  →  1

规律：每到 2 的幂次方，1 的个数重置为 1。

相关题目 ​

题目难度关键点
338. 比特位计数简单本题
191. 位1的个数简单单个数的 1 计数
231. 2的幂简单n & (n-1) 技巧
461. 汉明距离简单XOR + 计数

总结 ​

  1. 暴力法：O(n log n)，每个数单独计算
  2. DP 法：O(n)，利用已计算结果
  3. 核心技巧：n & (n-1) 去掉最低位 1，或右移继承
  4. 空间优化：本题需要返回数组，无法进一步优化空间

复杂度 ​

  • 时间：O(n)
  • 空间：O(n)（存储结果）

执行过程 ​

dp[0] = 0
dp[1] = dp[0] + 1 = 1
dp[2] = dp[1] + 0 = 1
dp[3] = dp[1] + 1 = 2
dp[4] = dp[2] + 0 = 1
dp[5] = dp[2] + 1 = 2

结果：[0,1,1,2,1,2]

复杂度 ​

  • 时间：O(n)
  • 空间：O(n)

在 GitHub 上编辑此页