Posted on 2023-09-03 15:51
Uriel 閱讀(37)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
位運算
輸入n，輸出從0~n每個數二進制表示的1的數量
O(n)復雜度的方法比較巧妙：1000..0這樣的數1的數量一定是1，所以某個數i的1的含1數量等于1（首位）+(i-p)的含1數量，p為與i位數相等的1000...0的十進制表示
1 #338
2 #Runtime: 52 ms (Beats 71.57%)
3 #Memory: 17.3 MB (Beats 36.53%)
4
5 class Solution(object):
6 def countBits(self, n):
7 """
8 :type n: int
9 :rtype: List[int]
10 """
11 ans = [1] * (n + 1)
12 ans[0] = 0
13 for i in range(1, n + 1):
14 if (i & (i-1)) == 0:
15 p = i
16 else:
17 ans[i] = 1 + ans[i - p]
18 return ans