338. Подсчет битов

Дано неотрицательное целое число num. Для каждого числа i в диапазоне 0 ≤ i ≤ num вычислить количество единиц в их двоичном представлении и вернуть их в виде массива.

Пример:
Для num = 5 вы должны вернуть [0,1,1,2,1,2].

Последующие действия:

Очень легко найти решение со временем выполнения O(n*sizeof(integer)). Но можете ли вы сделать это за линейное время O(n) /возможно, за один проход?

Сложность пространства должна быть O(n).

Можете ли вы сделать это как босс? Сделайте это без использования какой-либо встроенной функции, такой как __builtin_popcount в C++ или любом другом языке.

Концепция

посмотрите построенную ранее таблицу

Код

class Solution {
public int[] countBits(int num) {
int[] result = new int[num+1];
int[] table = new int[]{0, 1, 1, 2};
if(num==0){
результат[0] = 0;
вернуть результат;
}
for(int i =1; i‹=число; i++){
int sum = 0;
int stay = i;
while(remain›0){
sum += table[remain %4];
осталось = осталось/4;
}
результат[i] = сумма;
}

вернуть результат;

}

Другое решение

class Solution { public int[] countBits(int num) { >int[] dp = new int[num+1]; for (int i = 1; i ‹= num; i++) { dp[i] = dp[i››1] + (i & 1); } возврат dp; } }