题目描述
题目链接:338. Counting Bits
Given an integer
n
, return an arrayans
of lengthn + 1
such that for eachi
(0 <= i <= n
),ans[i]
is the number of1
’s in the binary representation ofi
.
例子
例子 1
Input:
n = 2
Output:[0,1,1]
Explanation:0 --> 0
1 --> 1
2 --> 10
例子 2
Input:
n = 5
Output:[0,1,1,2,1,2]
Explanation:0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Follow Up
- It is very easy to come up with a solution with a runtime of
O(n log n)
. Can you do it in linear timeO(n)
and possibly in a single pass?- Can you do it without using any built-in function (i.e., like
__builtin_popcount
in C++)?
Constraints
0 <= n <= 10^5
解题思路
这道题看似比较比较抽象需要逐个数每个数字中二进制表示下 1
的位数,实际上用位操作的思路来看就很直观,如果是奇数则是在上一个数的结果上加 1 (最后一位从 0
变 1
,其他位不变),而偶数则相当于他的一半的二进制表示左移一位,因此它的结果和它的一半的结果一致。代码如下:
#include <vector>
class Solution {
public:
std::vector<int> countBits(int n) {
std::vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; ++i) {
if (i % 2 == 1) {
ans[i] = ans[i - 1] + 1;
}
else {
ans[i] = ans[i / 2];
}
}
return ans;
}
};
- 时间复杂度:
O(1)
- 空间复杂度:
O(n)
(输出结果所需空间,没有利用额外空间)
GitHub 代码同步地址: 338.CountingBits.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions