{%hackmd @lumynou5/dark-theme %}
# leetcode 338 Counting Bits
[原題](https://leetcode.com/problems/counting-bits/description/)
題目給一個n 要求一個數組a[n+1]
其中的每一項 代表該項的index(從0開始)在二進制下包含幾個1
### 直接算
對每一項算一遍 然後放進去 很直覺

int f(int i){
    int ans=0;
    while(i){
        if(i&1)++ans;
        i>>=1;
    }
    return ans;
}
vector<int> countBits(int n){
    vector<int> a(n+1);
    for(int i=0;i<=n;++i)a[i]=f(i);
    return a;
}
//9ms,7.8mb

時間複雜度平均$O(nlogn)$最差$O(nlogn)$ 空間$O(n)$(如果你不算返回的答案就算$O(1)$啦)
但是這畢竟是個應該有點規律的東西 相信它有個$O(n)$的解法
### 列舉觀察
把數列列出來
0 1 1 2 1 2 2 3 1 2 2 3
看不出明顯的規律
但是2的次冪肯定是1
並且到下一個1總是遞增(不嚴格)
根據位數分類的話

1bit    2bits    3bits    4bits
0 0     10 1     100 1    1000 1
1 1     11 2     101 2    1001 2
                 110 2    1010 2
                 111 3    1011 3
                          1100 2
                          1101 3
                          1110 3
                          1111 4

可以發現2bits的狀況 是1bit的狀態 加上最前面多1bit
3bits的前兩個 是最前面的1後面插一個0 所以前面完全一樣
後兩個是最前面的1 後面插一個1 所以多加1
同理 4bits前四項複製3bits 後四項是多一 依此類推
第i bits時複製1\<\<(i-2)項 後面1\<\<(i-2)項+1
這樣就能寫出一個$O(n)$的解法

vector<int> countBits(int n){
    vector<int> a(n+1);
    a[0]=0;
    if(!n)return a;
    a[1]=1;
    int i=2,j,k=1;
    for(;i<=n;k<<=1){
        for(j=k;j&&i<=n;--j,++i){
            a[i]=a[i-k];
        }
        for(j=k;j&&i<=n;--j,++i){
            a[i]=a[i-k]+1;
        }
    }
    return a;
}
//0ms,8mb

時間複雜度平均$O(n)$最差$O(n)$ 空間$O(n)$(如果你不算返回的答案就算$O(1)$啦)