使用dp思想,dp[n] = dp[n /2] (最后一位是0)或者 dp[n /2] + 1(最后一位是1)
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result;
if(num >= 0)
result.push_back(0);
if(num >= 1)
result.push_back(1);
if(num >= 2) {
for(int i = 2; i <= num; i++) {
int onetimes = i % 2 == 0 ? result[i / 2] : result[i / 2] + 1;
result.push_back(onetimes);
}
}
return result;
}
};
网友评论