題目:

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

給定一數n,回傳一長度為n+1的陣列紀錄0~n的二進位表示個別有幾個1
ex:input:2=>output:[0,1,1]
explanation:
0 --> 0
1 --> 1
2 --> 10

其實仔細觀察的話能發現其中是有規律的
1([1])等同於於0([0])的所有元素+1
2~3([1,2])等同於於0~1([0,1])的所有元素+1
4~7([1,2,2,3])等同於於0~3([0,1,1,2])的所有元素+1
8~15([1,2,2,3,2,3,3,4])等同於於0~7([0,1,1,2,1,2,2,3])的所有元素+1...
因為前者的二進位表示最高位比後者多了一個1
以4~7和0~3為例=>100,101,110,111和000,001,010,011
所以我們可以以最初陣列[0]為基礎去算出後續的可能

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans=[0]
        x=1
        while n>=x*2-1:
            plus=[i+1 for i in ans]
            ans=ans+plus
            x=x*2
            
        for i in range(n-x+1):
            ans.append(ans[i]+1)
        return ans

根據上面提到的規律進行操作,以2^m~2^(m+1)-1進行分組(m從0開始)
以[0]作為初始陣列(ans),只要n大於下一組的右邊界
我們就直接將陣列和另一個由陣列所有元素+1組成的陣列結合變為新的陣列
再前往下一組,直到n小於下一組的右邊界
就將下一組在n範圍內的數,慢慢一個一個放入ans(ans[0]+1,ans[1]+1......)
回傳最後的陣列即可
最後執行時間80ms(faster than 96.62%)

那我們下題見