Сложность: 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.
😎 Решение:
class Solution {
fun countBits(num: Int): IntArray {
val ans = IntArray(num + 1)
for (x in 1..num) {
ans[x] = ans[x and (x - 1)] + 1
}
return ans
}
}Ставь 👍 и забирай 📚 Базу знаний