【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 = 0while i > 0:i &= (i-1)cou += 1res.append(cou)return res# 或者def count_one(num):cou = 0while num > 0:num &= (num-1)cou += 1return 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                    # 记录最高有效位即二进制中只有最高位有一个1for i in range(1,n+1):if i & (i-1) == 0:high = ires.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