扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
https://leetcode.com/problems/counting-bits/
创新互联专注于企业全网营销推广、网站重做改版、天峻网站定制设计、自适应品牌网站建设、H5开发、商城开发、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为天峻等各大城市提供网站开发制作服务。给定一个非负数n，输出[0,n]区间内所有数的二进制形式中含1的个数
Example:
For num = 5 you should return [0,1,1,2,1,2].
注意fellow up部分，题目说了你要是一个个无脑去遍历输出是不ok的，直接用某些内置函数也是不行的
解题思路
实在没思路就看看hint部分
找张纸，多写几个数，包括：
1、数（十进制）
2、数（二进制）
3、二进制中1的个数
图片来自http://blog.csdn.net/qiexingqieying/article/details/51719997
感谢作者keke he，侵删
横线分组，会发现第1组的count是第0组的count+1，第n组是1+2+。。。+(n-1)组的count+1
所以某个数的count就是这个数减所在组2开方数的count+1
res[x]=res[x-pow(2,len(bin(x))-3)]+1注意python的bin（）结果强制带前缀0b
然后类似斐波拉切数列，第一个和第二个强制制定
class Solution(object):
def countBits(self, num):
res=[1] * (num+1)
if num==0:
res[0]=0
elif num==1:
res[0]=0
res[1]=1
elif num>1:
res[0]= 0
res[1] = 1
for x in xrange(2,num+1):
res[x]=res[x-pow(2,len(bin(x))-3)]+1
return res
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网