域名申请到网站建设教程,哪个网站专题做的好,广告设计与制作专业课程,郑州seo优化外包热狗网题目描述
给你一个整数 n #xff0c;对于 0 i n 中的每个 i #xff0c;计算其二进制表示中 1 的个数 #xff0c;返回一个长度为 n 1 的数组 ans 作为答案。
示例 代码思路
第一种方法
最简单的方法就是#xff0c;遍历然后使用python自带的bin()方法直接…题目描述
给你一个整数 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 resdef count(self, num):if num 0:return 0if num % 2 1:return self.count(num - 1) 1return 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 resdef count(self, num):if num 0:return 0if self.memo[num] ! 0:return self.memo[num]if num % 2 1:res self.count(num - 1) 1else:res self.count(num // 2)self.memo[num] resreturn res
进入count后 判断非0后直接判断是否存在列表里有的话直接调值。
