Problem#
給你一個整數 n 問你從 $[0, n]$ binary 中一的個數，輸出在 list 中。限制: $0 \leq n \leq 10^5$
follow-up:
- 在時間複雜度 $\mathcal{O}(N)$ 下做到且掃一次就完成
- 避免使用 builtin function e.g.
__builtin_popcount()
想法#
-
直覺做法就直接照做，直接去數每個數字有幾個 bit 是 1，更好一點則用
__builtin_popcount()來數 bit -
觀察發現如果一個數字是偶數，則該數字除2，1 bit 的個數會一樣；如果一個數字是奇數，則該數字除2的 1bit 的個數會減去一(因為 LSB 的 bit 被移掉了)
if odd then dp[i] = dp[i/2]+1 else dp[i] = dp[i/2]
-
Best 時間複雜度: $\mathcal{O}(N)$
-
Best 空間複雜度: $\mathcal{O}(N)$
AC Code#
賞析#
https://leetcode.com/problems/counting-bits/discuss/1808016/C%2B%2B-oror-Vectors-Only-oror-Easy-To-Understand-oror-Full-Explanation
https://leetcode.com/problems/counting-bits/discuss/800456/C%2B%2B-or-Counting-Bits-or-O(N)-Explanation
https://leetcode.com/problems/counting-bits/discuss/1808002/A-very-very-EASY-to-go-EXPLANATION
心得#
乍看之下很簡單，但其實有 DP 的作法
還有查到 popcount 的實作，挺有趣的