題目： LeetCode - 338. Counting Bits

題目說明

給一個 num，回傳一個代表 0 ~ num 的二進制中 1 的數量的陣列。

解題思路

觀察答案的陣列可以知道，對於 i 來說，如果 i 是奇數則 res[i] = res[i / 2] + 1，如果 i 是偶數則 res[i] = res[i / 2]。

參考解法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num + 1);
        for(int i = 1; i <= num; ++i)
            res[i] = res[i / 2] + i % 2;
        return res;
    }
};