思路
找规律，当一个从0到num的序列中每到2的倍数的下标i时，i2i-1对应的数字带1的数量为0i-1已知序列对应下标+1，因此可以递推出来该序列。代码
#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;
}
