Description
給定整數
n，回傳長度為n + 1的陣列ans，其中ans[i]是i的二進位表示中1的個數。要求 O(n) 時間複雜度。
Example:
Input: n = 5 Output: [0,1,1,2,1,2]
Intuition#
核心思路：利用 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: 逐一計算 Popcount#
- 概念: 對 0 到 n 的每個數字，分別用 Brian Kernighan 演算法計算 1 的個數
- 時間複雜度:
O(n log n)- 每個數字最多 log n 個 bit - 空間複雜度:
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 + 右移#
- 概念: 數字 i 的 1 的個數等於 i » 1 的 1 的個數加上 i 的最低位（i & 1）
- 時間複雜度:
O(n)- 每個數字只需 O(1) - 空間複雜度:
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
}
}補充：DP + 消除最低位的 1
利用 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，利用位元結構找出子問題關係
- 關鍵技巧: i » 1 和 i & (i - 1) 都可以將問題縮小到已計算過的子問題，是位元 DP 的常見模式