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

創(chuàng)新互聯(lián)專(zhuān)注于企業(yè)全網(wǎng)營(yíng)銷(xiāo)推廣、網(wǎng)站重做改版、天峻網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5開(kāi)發(fā)、商城開(kāi)發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性?xún)r(jià)比高，為天峻等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

給定一個(gè)非負(fù)數(shù)n，輸出[0,n]區(qū)間內(nèi)所有數(shù)的二進(jìn)制形式中含1的個(gè)數(shù)

Example:
For num = 5 you should return [0,1,1,2,1,2].

注意fellow up部分，題目說(shuō)了你要是一個(gè)個(gè)無(wú)腦去遍歷輸出是不ok的，直接用某些內(nèi)置函數(shù)也是不行的

解題思路

實(shí)在沒(méi)思路就看看hint部分

找張紙，多寫(xiě)幾個(gè)數(shù)，包括：

1、數(shù)（十進(jìn)制）

2、數(shù)（二進(jìn)制）

3、二進(jìn)制中1的個(gè)數(shù)

圖片來(lái)自http://blog.csdn.net/qiexingqieying/article/details/51719997

感謝作者keke he，侵刪

橫線分組，會(huì)發(fā)現(xiàn)第1組的count是第0組的count+1，第n組是1+2+。。。+(n-1)組的count+1

所以某個(gè)數(shù)的count就是這個(gè)數(shù)減所在組2開(kāi)方數(shù)的count+1

res[x]=res[x-pow(2,len(bin(x))-3)]+1

注意python的bin（）結(jié)果強(qiáng)制帶前綴0b

然后類(lèi)似斐波拉切數(shù)列，第一個(gè)和第二個(gè)強(qiáng)制制定

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

標(biāo)題名稱(chēng)：338.CountingBits-創(chuàng)新互聯(lián)
本文鏈接：http://aaarwkj.com/article30/ccdcpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)