#338. Counting Bits

題目描述

給你一個整數n，回傳一個長度為n+1的整數陣列，陣列中的元素i是i的值(0<=i<=n)的二進位表示中的1的數量。

限制條件

0 <= n <= 10^5

解題思路

Intuition

這一題，我們需要做的事就是計算從0到n的每一個數字在二進位表示法中的1的數量。

舉例來說：

n=5
0: 0 | [0]
1: 1 | [1]
2: 1 | [10]
3: 2 | [11]
4: 1 | [100]
5: 2 | [101]

計算二進位的方式有很多，像是>>右移運算子或者直接以四則運算除以2來計算。
這裡我們用最直覺的除以2的方法來處理。

public class Solution { 
	public int[] CountBits(int n) {
        if(n==0) return new int[]{0};        
        List<int> ans = new List<int>{0};
        for(int i=1;i<=n;i++){
            int a = i;
            int c = 0;            
            while(a!=0) {
                if(a%2==1) c++;
                a/=2;
            }
            ans.Add(c);
        }
        return ans.ToArray();
    }
}

複雜度分析：

時間複雜度：從0到n的數值都要計算，會花上n的時間，而計算二進位中的1的數量的while迴圈會花上log(n)的時間，因此時間複雜度為O(n*log(n))。
空間複雜度：要回傳一個n+1的陣列，也就是說會需要創造一個n+1的陣列，因此空間複雜度為O(n)。

Follow-up

非常容易使用時間複雜度為O(n*log(n))的解決方式來處理，但是能不能讓執行的時間複雜度為O(1)呢？
可以不使用內建的處裡函式(例如：C++的__builtin_popcount())來解決這個問題嗎？

Imporvement

如果我們要完成所有的0到n的bits的計算，勢必會花上n的時間，所以要讓執行時間變得更快必須要把上一個解法中會造成log(n)的演算法換掉。

0 : 0 | [0]
1 : 1 | [1]
2 : 1 | [10]
3 : 2 | [11]
4 : 1 | [100]
5 : 2 | [101]
6 : 2 | [110]
7 : 3 | [111]
8 : 1 | [1000]
9 : 2 | [1001]
10: 2 | [1010]

我們拿出0到10的二進位表示來觀察，可以發現到[1,2,4,8]、[3,6]、[5,10]之間的關係都是兩倍差，但每一組的組員彼此的bit 1的數量都是一樣的。而換個方式分組，[2,3]、[4,5]、[6,7]、[8,9]之間則是偶數和奇數的關係，每一個奇數都會比偶數多一個bit 1。

則可以整理出，每一個奇數的bit 1都會比它減去1的偶數的小組的bit 1數量多1，因此可以獲得n[i] = n[i>>1] + i%2這個算式。

public class Solution { 
	public int[] CountBits(int n) {
        var ans = new int[n+1];
        for(int i=0;i<ans.Length;i++){            
            ans[i] = ans[i>>1] + i%2;      
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：從0到n的數值都要計算，會花上n的時間，但是透過改進的演算法，可以用過去已經計算出來的結果推算現在的結果，不需要每一次都去重新計算結果，在花費的時間上為O(1)。
空間複雜度：要回傳一個n+1的陣列，也就是說會需要創造一個n+1的陣列，因此空間複雜度為O(n)。

學習重點

Bit操作。
動態規劃。