LeetCode 338. Counting Bits：線性時間位計數動態規劃

問題描述

給定非負整數 num，返回長度 num+1 的數組，第 i 個元素為 i 的二進制中 1 的個數。要求 O(n) 時間、O(n) 空間、單次遍歷、不使用內建函數。

方法一：奇偶性規律 F[n] = F[n>>1] + (n&1)

觀察二進制：n 右移一位等於 n/2，1 的個數相同；若 n 為奇數則最低位多一個 1。

0: 0000  → 0
1: 0001  → F[0]+1 = 1
2: 0010  → F[1]   = 1
3: 0011  → F[1]+1 = 2
4: 0100  → F[2]   = 1
5: 0101  → F[2]+1 = 2

vector countBits(int num) {
    vector res(num+1, 0);
    for (int i = 1; i <= num; ++i)
        res[i] = res[i>>1] + (i&1);
    return res;
}

方法二：低位消除規律 F[n] = F[n&(n-1)] + 1

n&(n-1) 消除最低位的 1。n 的 1 個數比消除後多 1。
例：7 (111) & 6 (110) = 6 (110)，F[7]=F[6]+1。

vector countBits(int num) {
    vector res(num+1, 0);
    for (int i = 1; i <= num; ++i)
        res[i] = res[i & (i-1)] + 1;
    return res;
}

Python 實現

def countBits(self, num):
    res = [0]
    for i in range(1, num+1):
        res.append(res[i>>1] + (i&1))  # 或 res[i&(i-1)]+1
    return res

複雜度與優勢

• 時間：O(n)，單循環
• 空間：O(n)，輸出數組
• 無分支預測失敗，極高效
• 利用已計算結果，體現動態規劃思想