力扣/leetcode383.比特位记数

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例

代码思路

第一种方法

最简单的方法就是，遍历然后使用python自带的bin()方法直接转换为2进制然后用count去数数。

第二种方法

考虑到数的特点，如果该数i为偶数，那么他二进制中1的个数和他i/2的数的1的个数是一样的。

那是因为偶数的末尾是0，向右边移动一位，然后就变成i/2，这导致1的数量不变。

如果i为奇数,那么它的二进制1的位数=i-1的二进制位数+1

1：奇数二进制末尾为1如果把末尾的1去掉就相当于在原有基础上减1。

2：减掉1后，奇数就变成偶数了，而偶数的二进制数又是总和它i/2是相等的，这就进入了递归的环节了。

class Solution(object):
    def countBits(self, num):
        res = []
        for i in range(num + 1):
            res.append(self.count(i))
        return res
    
    def count(self, num):
        if num == 0:
            return 0
        if num % 2 == 1:
            return self.count(num - 1) + 1
        return self.count(num // 2)

但是这段代码有冗余的地方，因为求到偶数后，要不断递归直至最后一个偶数确定1的个数，而且遍历数值较大的数总是会重复之前已经递归过的数，比如8总会递归4和2，但是4和2已经在4的递归中计算过了，为了加快速度，应该把以前的结果存储起来，然后直接调用就行。

第二种方法的改进

class Solution(object):
    def countBits(self, num):
        self.memo = [0] * (num + 1)
        res = []
        for i in range(num + 1):
            res.append(self.count(i))
        return res
    
    def count(self, num):
        if num == 0:
            return 0
        if self.memo[num] != 0:
            return self.memo[num]
        if num % 2 == 1:
            res = self.count(num - 1) + 1
        else:
            res = self.count(num // 2)
        self.memo[num] = res
        return res

进入count后 判断非0后直接判断是否存在列表里，有的话直接调值。