Posted on 2023-09-03 15:51
Uriel 阅读(9)
评论(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