🙉饭不食，水不饮，题必须刷🙉
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)。

---