Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
👨💻 Алгоритм:
1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.
2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.
3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.
😎 Решение:
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int x = 1; x <= num; ++x) {
ans[x] = ans[x & (x - 1)] + 1;
}
return ans;
}
}Ставь 👍 и забирай 📚 Базу знаний