设计 网站 现状,站长之家下载,企业网站优化外包,seo技术分类【力扣题】题目描述#xff1a; 题解#xff1a;从0到n的整数#xff0c;逐一统计二进制中1的个数#xff0c;记录在一个新列表中。 【Python3】代码#xff1a;
1、解题思路#xff1a;Python函数。
知识点#xff1a;bin(...)#xff1a;转为二进制字符串#xff…【力扣题】题目描述 题解从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(n1)]return res#相当于res []for i in range(n1):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。 例如num5(二进制101)num-14(二进制100)num(num-1)101100100(即将101的最低位的1消除为0)。 class Solution:def countBits(self, n: int) - List[int]:res []for i in range(n1):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(n1)]return res 3、解题思路动态规划。
将一个问题拆分成多个子问题解决子问题并记录子问题的结果减少重复计算最终整个问题解决。
3-1若num是2的整数幂num中只有最高位有1则记录num。
若num不是2的整数幂则num的二进制 比 去除最高位之后的二进制 多一个1。
例如5(二进制101)去除最高位之后的二进制01其个数已统计过为1则5的二进制中1的个数为112个。
class Solution:def countBits(self, n: int) - List[int]:# 动态规划--最高有效位res [0]high 0 # 记录最高有效位即二进制中只有最高位有一个1for i in range(1,n1):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的个数为112个。
知识点num 1将num二进制右移一位。 i 1将num与1进行二进制与运算。
class Solution:def countBits(self, n: int) - List[int]:# 动态规划-最低有效位res [0]for i in range(1,n1):res.append(res[i 1] (i 1))return res 3-3num(num-1)消除num最低位的1则num 比 消除最低位1之后 多一个1。
例如num5(二进制101)num-14(二进制100)num(num-1)101100100二进制100其个数已统计过为1则5的二进制中1的个数为112个。
class Solution:def countBits(self, n: int) - List[int]:# 动态规划--最低设置位res [0]for i in range(1,n1):res.append(res[i (i-1)] 1)return res
