Leetcode題解 Python & C#：五月挑戰DAY28 Counting Bits

給一個非負整數 num，要找出 [0, num] 之間(包含兩端)的所有整數在二進位下有的 1 個數。

因為很簡單，所以有限制條件，在 O(n) 時空內解決。

如果是 0，那其二進位不含 1 ，是 0 個。

如果是 1，那其二進位只有 1 個 1 。

如果是 2，那進位，二進位變成 10，只有 1 個 1。

如果是 3，那二進位是 11，有 2 個 1。

如果是 4，那進位，二進位是 100，只有 1 個 1。 

一旦進位，接下來的 1 個數，會是將前面的所有的 1 個數再加 1。可把前面視作最高位為 0 的版本，而進位是變成最高位為 1 的版本，

000

001 ( _ + 1)

010 (0的答案 + 1))

011 (1的答案 + 1))

100 (00的答案 + 1)

101 (01的答案 + 1)

110 (10的答案 + 1)

111 (11的答案 + 1)

接下來換奇偶方法。

若用長除法，數字不斷除以 2 ，最後可以用長除法的結果把該數字(10進位)轉換成 2 進位的型式。

若過程有餘數出現，相當於有二進位的某位有 1 的出現。

0 (長除法) 出現餘數 1 次數： 0

1 (長除法) 出現餘數 1 次數： 1

2 (長除法) 出現餘數 1 次數： 1

3 (長除法) 出現餘數 1 次數： 2

4 (長除法) 出現餘數 1 次數： 1

5 (長除法) 出現餘數 1 次數： 2

6 (長除法) 出現餘數 1 次數： 2

7 (長除法) 出現餘數 1 次數： 3

因為數字被除2之後是計算是之前有過的，也就是重複計算。

舉個例好懂：

像 7 / 2 = 3 ... 1 ， 後面還要拿 3 繼續長除法，但 3 的計算是出現過的，可以直接取 3 的答案，所以奇數就是整除2的答案+1，而偶數是整除2的答案。

Python(計數)

class Solution:
    def countBits(self, num):
        result = [0]
        i = 0
        while True:
            for number in range(len(result)):
                if i == num: return result
                result.append(result[number] + 1)
                i += 1

Python(奇偶)

class Solution:
    def countBits(self, num: int) -> List[int]:
        result = [0]
        memo = {0:0}
        
        def ones(number):
            if number in memo: return memo[number]
            ans = number % 2 + ones(number//2)
            result.append(ans)
            memo[number] = ans
        
        for number in range(num+1):
            ones(number)
            
        return result

C#(奇偶)

public class Solution {
    public int[] CountBits(int num) {
        var result = new List();
        result.Add(0);
        for(int i = 1; i <= num; i++)
        {
            result.Add(result[i/2] + i % 2);
        }
        return result.ToArray();
    }
}