Skip to content

LeetCode: 383-Counting Bits 解題紀錄

Last Updated on 2022-03-01 by Clay

題目

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.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

  • 0 <= n <= 105

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
  • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

題目會輸入一個數字 n，而我們要計算從 0 開始到 n 之間，每個數字表示成二進制時，一共會存在多少個 1。最後回傳每個數字包含著 1 數量的陣列。

解題思路

Brute Force

直接計算從 0 開始到 n 之間的二進制轉換包含多少個 1。十進制轉換成二進制非常單純，就是在數字歸零之前，一直算出『餘數』，並把當前計算的數字除以二。


Brute Force 複雜度

由於每個數值我們都要除二直至歸零，故時間複雜度為 n*log(n)。

Time ComplexityO(n log n)
Space ComplexityO(n)


Brute Force C++ 範例程式碼

class Solution {
public:
    vector<int> countBits(int n) {
        // Init
        vector<int> results({0});
        
        // Count
        for (int i=1; i<=n; ++i) {
            int oneNum = 0;
            int num = i;
            
            while (num > 0) {
                oneNum += num % 2;
                num /= 2;
            }
            
            results.push_back(oneNum);
        }
        
        return results;
    }
};



Brute Force Python 範例程式碼

class Solution:
    def countBits(self, n: int) -> List[int]:
        # Init
        results = [0]
        
        # Count
        for n in range(1, n+1):
            oneNum = 0
            
            while n:
                oneNum += n % 2
                n = n // 2
        
            results.append(oneNum)
        
        return results



Dynamic Programming

由於題目最底下的 follow up 要求要在 O(n) 的時間複雜度內完成，所以我們應該很快地就能想像到要從前面的數值來推算後面的數值。

比方說，由於我們在計算 5 時已經計算過前面的 2，所以我們應該能夠藉由 2 的答案來推算出 5。

直接觀察範例給的解釋：

0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

假設我們要計算 2 的二進制，我們可以這樣計算：

2 / 2 = 1 ... 0
1 / 2 = 0 ... 1

所以 2 的二進制為 "10"。

那麼現在假設我們要計算 5 的二進制，我們原本要使用以下土法煉鋼的方法：

5 / 2 = 2 ... 1
2 / 2 = 1 ... 0
1 / 2 = 0 ... 1

但是我們會發現，其實從第二行開始就已經是過去計算過的 2 的二進制過程了！所以我們只需要判斷原始的數字是不是奇數，如果是奇數的情況我們就拿 dp[n/2]+1 來當作 n 這個數字二進制 1 的總數；如果是偶數的情況，由於 n 一開始除 2 就是 0，所以就直接計算為 dp[n/2]。

所以，總之我們需要建立一個 dp 表，逐步紀錄起每個數值的解答。剛好這題又要求我們回傳 0 到 n 所有數值的解答，所以就直接回傳 dp 表。


Dynamic Programming 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


Brute Force C++ 範例程式碼

class Solution {
public:
    vector<int> countBits(int n) {
        // Base case
        if (n == 0) return {0};
        
        // Init
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        
        // Count
        for (int i=2; i<=n; ++i) {
            if (i % 2 == 0) {
                dp[i] = dp[i/2];
            }
            else {
                dp[i] = dp[i/2] + 1;
            }
        }
        
        return dp;
    }
};



Brute Force Python 範例程式碼

class Solution:
    def countBits(self, n: int) -> List[int]:
        # Base case
        if n == 0: return [0]
        
        # Init
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        
        # Count
        for i in range(2, n+1):
            # Odd
            if i % 2 == 1:
                dp[i] = dp[i//2] + 1
            
            # Even
            else:
                dp[i] = dp[i//2]         
        
        return dp

References

Read More

Tags:

Leave a Reply