首页 > 代码库 > 338. Counting Bits

338. Counting Bits

https://leetcode.com/problems/counting-bits/

给定一个非负数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

 

338. Counting Bits