【Python3】【力扣题】338. 比特位计数

【力扣题】题目描述：

题解：从0到n的整数，逐一统计二进制中1的个数，记录在一个新列表中。

【Python3】代码：

1、解题思路：Python函数。

知识点：bin(...)：转为二进制字符串，即"0bxxx"。

              字符串.count(...)：统计字符串中某字符出现的次数。

              列表.append(...)：往列表尾部添加元素。

              列表推导式：用简洁的方式创建列表。即 [ 对元素的简单操作 for 变量 in 可迭代对象 ]

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [bin(i)[2:].count("1") for i in range(n+1)]
        return res
        #相当于
        res = []
        for i in range(n+1):
            res.append(bin(i)[2:].count("1"))
        return res

2、解题思路：Brian Kernighan算法。

每次将整数的二进制最低位的1消除为0，直到整数变为0。消除多少次则二进制中有多少个1。

num &= (num-1) 即 num = num & (num-1) 。

相当于将二进制最低位的1消除为0。若num为2的整数幂，则num&(num-1)=0。

例如：num=5(二进制101)，num-1=4(二进制100)，num&(num-1)=101&100=100(即将101的最低位的1消除为0)。

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        for i in range(n+1):
            cou = 0
            while i > 0:
                i &= (i-1)
                cou += 1
            res.append(cou)
        return res
        # 或者
        def count_one(num):
            cou = 0
            while num > 0:
                num &= (num-1)
                cou += 1
            return cou  
        res = [count_one(i) for i in range(n+1)]
        return res

3、解题思路：动态规划。

将一个问题拆分成多个子问题，解决子问题并记录子问题的结果减少重复计算，最终整个问题解决。

（3-1）若num是2的整数幂，num中只有最高位有1，则记录num。

若num不是2的整数幂，则num的二进制 比 去除最高位之后的二进制 多一个1。

例如：5(二进制101)，去除最高位之后的二进制01（其个数已统计过为1），则5的二进制中1的个数为1+1=2个。

class Solution:
    def countBits(self, n: int) -> List[int]:
        # 动态规划--最高有效位
        res = [0]
        high = 0                    # 记录最高有效位即二进制中只有最高位有一个1
        for i in range(1,n+1):
            if i & (i-1) == 0:
                high = i
            res.append(res[i-high] + 1)
        return res

（3-2）将二进制右移一位，去除最低位之后的二进制中1的个数已统计过；被去除的最低位若为1则结果中再加1。

例如：5(二进制101)，右移一位之后的二进制10（其个数已统计过为1），被去除的最低位为1则5的二进制中1的个数为1+1=2个。

知识点：num >> 1：将num二进制右移一位。

              i & 1：将num与1进行二进制与运算。

class Solution:
    def countBits(self, n: int) -> List[int]:
        # 动态规划-最低有效位
        res = [0]
        for i in range(1,n+1):
            res.append(res[i >> 1] + (i & 1))
        return res

（3-3）num&(num-1)消除num最低位的1，则num 比 消除最低位1之后 多一个1。

例如：num=5(二进制101)，num-1=4(二进制100)，num&(num-1)=101&100=100，二进制100其个数已统计过为1，则5的二进制中1的个数为1+1=2个。

class Solution:
    def countBits(self, n: int) -> List[int]:
        # 动态规划--最低设置位
        res = [0]
        for i in range(1,n+1):
            res.append(res[i & (i-1)] + 1)
        return res