Leetcode338 比特位计数[DP]

2019年11月27日 0 作者 折纸

题目描述

file

解法

# 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函数,时间复杂度比较高,思路简单不说了
    file