🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌

一、題目

1、題目描述

??給定一個非負整數 n n n，對于 0 ≤ i ≤ n 0 \le i \le n 0≤i≤n 范圍中的每個數字 i i i，計算其二進制數中的 1 的數目并將它們作為陣列回傳，
??樣例輸入：7
??樣例輸出： [ 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 ] [0,1,1,2,1,2,2,3] [0,1,1,2,1,2,2,3]

2、基礎框架

• c++ 版本給出的基礎框架代碼如下：

class Solution {
public:
    vector<int> countBits(int n) {
    }
};

3、原題鏈接

LeetCode 338. 位元位計數

二、解題報告

1、思路分析

• 這個題是數學上非常有名的一種概念 —— 分型，
• 就是由小資料推出大資料，也算是遞推吧，話不多說，看下下面這個圖基本就明白了，
  
• 所以我們可以得出如下的遞推公式：
• f ( n ) = { 0 n = 0 1 n = 1 f ( n ? 2 i ? 1 ) 2 i ≤ n < 2 i + 2 i ? 1 f ( n ? 2 i ? 1 ) + 1 2 i + 2 i ? 1 ≤ n < 2 i + 1 f(n) = \begin{cases} 0 & n=0\\ 1 & n=1 \\ f(n - 2^{i-1})& 2^i \le n \lt 2^i + 2^{i-1} \\ f(n - 2^{i-1}) + 1& 2^i + 2^{i-1} \le n \lt 2^{i+1}\\ \end{cases} f(n)=??????????01f(n?2i?1)f(n?2i?1)+1?n=0n=12i≤n<2i+2i?12i+2i?1≤n<2i+1?

2、時間復雜度

• 時間復雜度為一個for回圈的次數，即 O ( n ) O(n) O(n)，

3、代碼詳解

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bitCount;
        bitCount.reserve(n + 1);
        for(int i = 0; i < n+1; ++i) {
            bitCount.push_back(-1);
        }
        bitCount[0] = 0;
        if(n == 0) {
            return bitCount;
        }
        bitCount[1] = 1;
        if(n == 1) {
            return bitCount;
        }
        
        for(int i = 1; ; ++i) {
            int flag = 0;
            for(int j = 1<<i; j < (1<<i+1); ++j) {
                if(j < (1<<i) + (1<<i-1)) {
                    bitCount[j] = bitCount[j - (1<<i-1)];
                }else {
                    bitCount[j] = bitCount[j - (1<<i-1)] + 1;
                }
                if(j >= n) {
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        return bitCount;
    }
};

• 這段代碼就是上文提到的遞推公式，只有一個點需要注意就是：
• 1<<n代表的是 2 n 2^n 2n，剩下的就是回圈進行遞推，

三、本題小知識

??可以利用 1<<i來快速計算 2 i 2^i 2i，并且用1<<i-1計算 2 i ? 1 2^{i-1} 2i?1，因為算術運算子的優先級高于位移運算子，所以減法先運算，就不需要加括號了，等價于1<<(i-1)，