[leetcode]338.ビット数カウンタ

非負の整数numを指定します.0≦i≦numの範囲の各数値iについて、そのバイナリ数の1の数を計算し、それらを配列として返す.
例1:

  : 2
  : [0,1,1]

例2:

  : 5
  : [0,1,1,2,1,2]

ステップ:
時間的複雑度O(n*sizeof(integer))の解を与えるのは簡単である.しかし、線形時間O(n)内でスキャンしてもいいですか?アルゴリズムの空間的複雑さはO(n)であることが要求される.解法をさらに改善できますか.この操作は、C++または他の言語では、C++の__builtin_popcountなどの組み込み関数を使用しないで実行する必要があります.
考え方:任意の10進数について言えば、2つの状況があります.1)奇数であり、1つの数が奇数である場合、対応するバイナリに含まれる1の個数は、その前のビットの偶数に含まれる1の個数に必ず1を加算する.2)偶数、の1つの数が偶数の場合、その対応するバイナリに含まれる1の個数は、必ずそれを2で割った数に対応するバイナリに含まれる1の個数に等しい.すべての偶数のバイナリは最後の1桁が0であることを示し、2で割った方が右シフト1桁に相当し、1つの0を除いたので、個数は変わらない.
ACコード:(C++)

class Solution {
   public:
    vector<int> countBits(int num) {
        vector<int> ans(num + 1);
        ans[0] = 0;
        for (int i = 1; i <= num; i++) {
            if (i % 2 == 1)
                ans[i] = ans[i - 1] + 1;
            else
                ans[i] = ans[i / 2];
        }
        return ans;
    }
};