0%

[Leetcode]338. Counting Bits(C++)

题目描述

题目链接:338. Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

例子

例子 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 time O(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 (最后一位从 01,其他位不变),而偶数则相当于他的一半的二进制表示左移一位,因此它的结果和它的一半的结果一致。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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