LeetCode 338. Counting Bits 解題報告：動態規劃 O(n) 位運算優化與 Java 實現

LeetCode 338. Counting Bits — 比特位計數的 DP 最優解

題目：給定非負整數 `num`，對於範圍 `0 ≤ i ≤ num` 中的每個數字，計算其二進制表示中 `1` 的個數，返回數組。

示例：`num = 5` → `[0,1,1,2,1,2]` (0=0, 1=1, 2=10, 3=11, 4=100, 5=101)。

方法一：暴力逐位統計 (原始碼思路) — O(n log n)

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0;
        int x = i;
        while (x > 0) {          // 逐位檢查
            count += (x & 1);    // 累加最低位
            x >>= 1;             // 右移
        }
        ans[i] = count;
    }
    return ans;
}

缺點：每個數獨立計算，重複工作多，時間複雜度 O(n * log n) (log n 為位數)。

方法二：動態規劃 — 最高有效位 (MSB) — O(n)

規律：對於數字 `i`，找到小於等於 `i` 的最大 2 的冪次 `highBit` (即最高位 1 的位置)。則 `i = highBit + (i - highBit)`，其中 `i - highBit` < `highBit`，已計算過。

遞推公式：`bits[i] = bits[i - highBit] + 1`

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    int highBit = 0; // 當前最高有效位對應的 2 的冪次
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0) { // i 是 2 的冪次 (二進制只有一個1)
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
    }
    return bits;
}

方法三：動態規劃 — 最低有效位 (LSB) / 奇偶性 — O(n) 更簡潔

規律：

• 偶數 `i`：二進制最低位為 0，`i` 的 1 的個數 = `i/2` (即 `i >> 1`) 的 1 的個數。
• 奇數 `i`：二進制最低位為 1，`i` 的 1 的個數 = `i/2` 的 1 的個數 + 1。

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
}

優勢：無需維護 `highBit`，代碼極簡，位運算極快，標準最優解。

方法四：動態規劃 — 最後設置位 (Brian Kernighan 算法變體) — O(n)

規律：`i & (i - 1)` 將 `i` 的最低位 1 置為 0。設 `lastSet = i & (i - 1)`，則 `bits[i] = bits[lastSet] + 1`。

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}

複雜度總結

擴展：Java 內置方法 `Integer.bitCount()`

JDK 內部使用高度優化的本地方法 (CPU 指令 `POPCNT` 或查表法)，單次調用極快。若無 O(n) 批量要求，直接循環調用 `Integer.bitCount(i)` 即可。

for (int i = 0; i <= n; i++) ans[i] = Integer.bitCount(i);