【LeetCode】338. 比特位计数
LeetCode 计数 比特
2023-09-14 09:13:24 时间
0.总结
- 难点是如何实现时间复杂度为
O(n)
的算法
1.题目
2.思想
2.1 暴力求解
- 遍历待求数组,得到每个数字
num
- 计算每个数num 中1的含量
2.2
?
3.代码
class Solution:
def countBits(self, n: int) -> List[int]:
res = []
# standard = 1
# while(standard <= n):
# standard = standard << 1 # 左移一位
# standard = standard-1 #
# print(standard)
# 统计一的个数
def _get_cnt(num):
cnt = 0
while(num):
a,b = divmod(num,2)
num = a
if b:
cnt += 1
return cnt
for i in range(n+1):
res.append(_get_cnt(i))
return res