338. Counting Bits

1. 思路
   找规律，当一个从0到num的序列中每到2的倍数的下标i时，i_{2i-1对应的数字带1的数量为0}i-1已知序列对应下标+1，因此可以递推出来该序列。

2. 代码

#include <iostream>
#include <map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> output;
        output.push_back(0);
        int cur = 1;
        for(int i = 1 ; i <= num ; i++) {
            if(i == 2 * cur)
                cur *= 2;
            output.push_back(output[i - cur] + 1);
        }
        return output;
    }
};

int main(int argc, const char * argv[]) {
    Solution s ;
    int num;
    
    cin>>num;
    vector<int> output = s.countBits(num);
    for(int i = 0 ; i < output.size() ; i++)
        cout<<output[i]<<endl;
    return 0;
}