class Solution {
public:
vector<int> countBits(int n) {
}
};
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 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 <= 105
进阶:
O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？O(n) 。__builtin_popcount ）来执行此操作。
注意：本题与主站 338 题相同：https://leetcode.cn/problems/counting-bits/
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2022-05-26 10:35:35
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n+1)
for i in range(1, n+1):
ans[i] = ans[i>>1] + (i&1)
return ans
golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2022-05-26 10:16:00
func countBits(n int) []int {
ans := make([]int, n+1)
for i := 1; i <= n; i++ {
ans[i] = ans[i>>1] + i&1
}
return ans
}