Leetcode338 比特位计数[DP]

题目描述

解法

# class Solution:
#     def countBits(self, num: int) -> List[int]:
#         res = []
#         for i in range(num+1):
#             temp = bin(i)[2:]
#             res.append(temp.count('1'))
#         return res
class Solution:
    def countBits(self, num: int) -> List[int]:
        if not num:
            return [0]
        res = [0,1]
        for i in range(2,num+1):
            if(i%2==0):
                res.append(res[i//2])
            else:
                res.append(res[i//2]+1)
        return res

 

Note

• 注释部分思路是用了内置count函数，时间复杂度比较高，思路简单不说了