【LeetCode】338. 比特位计数

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