題目出處

338. Counting Bits

難度

easy

個人範例程式碼

class Solution:
    def countBits(self, n: int) -> List[int]:

        dp = [0 for _ in range(n+1)]

        for i in range(1, n+1):
            if i % 2 == 0: # ood case
                dp[i] = dp[i>>1]
            else: # even case
                dp[i] = dp[i>>1] + 1

        return dp

算法說明

個人覺得算法比較偏 tricky 的題目，看看即可，
要注意的點是在題目不希望我們用 O(nlogn) 去實現，也就是不希望我們「一個一個算」，

題目希望我們用 O(n) 時間完成，也就是我們必須想辦法「找到數字之間的相關性」，
就可以猜測這個做法應該跟 dp 有關

推理 dp 相關性

推理過程我們拆成奇數跟偶數分析，我們發現
* 偶 -> 奇：最好討論的情況，因為末位一定是 0，dp[i] = dp[i>>1] + 1，(dp[i>>1] 代表左側所有位數)
* 奇 -> 偶：我們觀察後，比較難發現他會找到最低位的 0 第一次出現的位置 (不懂可以看圖)，我們要做有點連環式的 dp 分析

• 例如: ‘101’ -> ‘110’ ，我們可以不管他前一個數字 ‘101’ 是啥，
  我們找到 ‘110’ 的 ‘0’ 會知道它的結果等於 dp[’11’]

• 例如: ‘1111’ -> ‘10000’ ，我們可以不管他前一個數字 ‘11111’ 是啥，
  我們找到 ‘10000’ 的 ‘0’ 會知道它的結果等於 dp[‘1000’]，
  而 dp[‘1000’] = dp[‘100′] = dp[’10’] = dp[‘1’] = dp[‘0’] + 1，
  類似這樣的連鎖效應。

input handling

一同在 dp 內處理

Boundary conditions

用 for 迴圈控制範圍

Reference

• 数 1 · Counting Bits