給定整數
n，回傳長度為n + 1的陣列ans，其中ans[i]是i的二進位表示中1的個數。要求 O(n) 時間複雜度。
Example:
Input: n = 5 Output: [0,1,1,2,1,2]
Intuition
TIP
核心思路：利用 DP 關係 dp[i] = dp[i >> 1] + (i & 1)，右移一位的結果已經算過。
- 暴力法對每個數字分別算 popcount，時間 O(n log n)
- 觀察規律：數字 i 的 1 的個數 = i 右移一位的 1 的個數 + i 的最低位
- 另一個 DP 關係：dp[i] = dp[i & (i - 1)] + 1（消除最低位的 1）
Approaches
1. Per-Number Popcount — O(n log n) / O(1)
- Idea: 對 0 到 n 的每個數字，分別用 Brian Kernighan 演算法計算 1 的個數
- Time:
O(n log n)- 每個數字最多 log n 個 bit - Space:
O(1)- 不含輸出陣列
class Solution {
fun countBits(n: Int): IntArray {
val ans = IntArray(n + 1)
for (i in 0..n) {
var count = 0
var num = i
while (num != 0) {
num = num and (num - 1)
count++
}
ans[i] = count
}
return ans
}
}⭐ 2. DP + Right Shift — O(n) / O(1)
- Idea: 數字 i 的 1 的個數等於 i >> 1 的 1 的個數加上 i 的最低位（i & 1）
- Time:
O(n)- 每個數字只需 O(1) - Space:
O(1)- 不含輸出陣列
class Solution {
fun countBits(n: Int): IntArray {
val ans = IntArray(n + 1)
for (i in 1..n) {
ans[i] = ans[i shr 1] + (i and 1)
}
return ans
}
}Note: DP + Clear Lowest Set Bit
利用 i & (i - 1) 消除最低位的 1，dp[i] = dp[i & (i - 1)] + 1。
class Solution {
fun countBits(n: Int): IntArray {
val ans = IntArray(n + 1)
for (i in 1..n) {
ans[i] = ans[i and (i - 1)] + 1
}
return ans
}
}這個方法本質上是利用已計算過的結果（消除一個 1 後的數字），加上被消除的那個 1。
🔑 Takeaways
- Pattern: 位元操作 + DP，利用位元結構找出子問題關係
- Key trick: i >> 1 和 i & (i - 1) 都可以將問題縮小到已計算過的子問題，是位元 DP 的常見模式