[C++] LeetCode 338. Bit位計數

題目

給定一個非負整數 num。 對于範圍 0 ≤ i ≤ num 中的每個數字 i ，計算其二進制數中的1的數目并将它們作為數組傳回。

示例：

比如給定

num = 5

，應該傳回

[0,1,1,2,1,2]

.

進階：

給出時間複雜度為

O(n * sizeof(integer))

的解答非常容易。 但是你可以線上性時間O(n)内用一次周遊做到嗎？

要求算法的空間複雜度為

O(n)

。

你能進一步完善解法嗎？ 在c ++或任何其他語言中不使用任何内置函數（如c++裡的

__builtin_popcount

）來執行此操作。

題解

這道題可以考慮

n=n-1+1

，那麼對于

n-1

最低位為

的時候，

n

的

1

的個數就等于

n-1

的

1

的個數加

1

。

但是如果

n-1

最低位不為

1

，那麼加

1

之後，原先低位為

1

的由于進位都變成

，從最右側往左第一個

的位置變為

1

；是以

n

中

1

得個數就等于

n-1

中

1

的個數減去

n-1

最低位連續

1

的個數加上

1

。

例如：

1=1(2) 1 = 1 ( 2 ) 　　 2=10(2) 2 = 10 ( 2 ) 　　 3=11(2) 3 = 11 ( 2 ) 　　 4=100(2) 4 = 100 ( 2 )

代碼

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res;
        res.push_back(0);
        for(int i=1;i<=num;i++){
            if(((i-1)&1)==0){
                res.push_back(res[i-1]+1);
                continue;
            }
            for(int j=0;j<32;j++){
                if(((i-1)&(1<<j))==0){
                    res.push_back(res[i-1]-j+1);
                    break;
                }
            }
        }
        return res;
    }
};