[LeetCode] 0338. ビットを数える

整数を与える n、 戻る 配列 答え 長さの n+1 それぞれについて 私 (0 <= i <= n), 答え[i] です の数 1さんの のバイナリ表現では 私.

例 1:

入力： n=2
出力： [0,1,1]
説明：
0 --> 0 1 --> 1 2 --> 10

例 2:

入力： n=5
出力： [0,1,1,2,1,2]
説明：
0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

制約:

• 0 <= n <= 10 5

フォローアップ：

• ランタイムを使用したソリューションを思いつくのは非常に簡単です。 O(n log n)線形時間でできるでしょうか？ の上） おそらくシングルパスで？
• 組み込み関数を使用せずにそれを行うことはできますか(つまり、 __builtin_popcount C++ で)?