題目網址：https://leetcode.cn/problems/counting-bits/

題意：給一整數 n, 對於 0 ≤ i ≤ n 中的每個 i, 計算其在二進制中 1 的個數, 返回一個長度為 n + 1 的 array 作為答案。

Solution 1：

想法：判斷 i 最靠右的 bit 是否為 1。若是的話, 則 cnt++, 每次判斷完後就將 i 右移一位, 直到 i = 0（沒有 1-bit）為止

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);

        for (int i = 0; i <= n; ++i) {
            int cnt = 0;
            for (int val = i; val > 0; val >>= 1) {
                const int rightmost = val & 1;
                if (rightmost == 1) {
                    cnt++;
                }
            }
            res[i] = cnt;
        }

        return res;
    }
};
  • time：$O(n \cdot log(n))$ ➔ $n * O(log(n))$
    • $O(log(n))$ : n 右移 1 位等價 n 除以 2, 令 k 為右移次數, $\dfrac{n}{2^k} = 1$ ➔ $k = log(n)$
  • space：$O(1)$ ➔ 若不考慮要返回的 array, 只需常數空間

Solution 2：

想法：利用 DP, 因為透過觀察發現：

1. 前一數（偶數）的 1 之個數 + 1, 因為偶數最右邊的 bit 必為 0, 奇數多的就是最右邊的 bit

  • e.g. 3 = 011, 2 = 010 ➔ 故 3 的 1 之個數 = 2 的 1 之個數 + 1

2. 偶數的 1 之個數 = （該數 / 2） 的 1 之個數, 因為偶數最右邊的 bit 必為 0, 所以偶數往右移一位, 該數的 1 之個數並不會減少

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            dp[i] = (i & 1) ? dp[i - 1] + 1 : dp[i >> 1];
        }
        return dp;
    }
};
  • time：$O(n)$ ➔ $n * O(1)$
    • dp[i] 都是去存取先前已計算過的 dp[i-1] 或 dp[i >> 1], 故每一次計算 dp[i] 故只需花 $O(1)$
  • space：$O(1)$ ➔ 若不考慮要返回的 array, 只需常數空間