LeetCode 338. 比特位計(jì)數(shù)
給定一個非負(fù)整數(shù) num。 對于范圍 0 ≤ i ≤ num 中的每個數(shù)字 i 冬筒，計(jì)算其二進(jìn)制數(shù)中的1的數(shù)目并將它們作為數(shù)組返回恐锣。
示例：
比如給定 num = 5 ，應(yīng)該返回 [0,1,1,2,1,2].
進(jìn)階：
- 給出時間復(fù)雜度為O(n * sizeof(integer)) 的解答非常容易舞痰。 但是你可以在線性時間O(n)內(nèi)用一次遍歷做到嗎土榴？
- 要求算法的空間復(fù)雜度為O(n)。
- 你能進(jìn)一步完善解法嗎响牛？ 在c ++或任何其他語言中不使用任何內(nèi)置函數(shù)（如c++里的 __builtin_popcount）來執(zhí)行此操作鞭衩。
我的答案：
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans;
ans.push_back(0);
for(int i=1; i<=num; i++){
ans.push_back(ans[i/2] + i%2);
}
return ans;
}
};
解題用時：23'
