LeetCode338 Counting Bits

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

样例

1
For num = 5 you should return [0,1,1,2,1,2].

思路

~个数,每个数的二进制表示中1的个数是多少。

首先我们来考虑,一个数的二进制表示中1的个数要怎么求

  • 直接遍历每个二进制位:
1
for (int i = 0; i < 32; ++i) ans += (n >> i) & 1;
  • 有多少个1就遍历多少次(通过lowbit跳转):
1
2
int lowbit(int n) { return n&-n; }
for (; n > 0; n -= lowbit(n)) ans++;

首先来说下的作用,这个是用来求一个数的二进制表示中最右边的那个“1”。
举个例子比较直观,比如

1
2
3
n           ->    0000 0000 1010 1100

lowbit(n) -> 0000 0000 0000 0100

那么 为什么 能求出呢?(注意到计算机内部以补码表示数)

假设的第~位全为0,那么最右边的“1”即为第位,形如

1
2
3
xxxx xxxx xxx1 0000  (x可为0或1)

第i+1位

取反后则形如 (假设x取反后变为y)

1
2
3
yyyy yyyy yyy0 1111  

第i+1位

再加1后则形如

1
2
3
yyyy yyyy yyy1 0000  

第i+1位

两个相与(&)后则求出最右边的“1”

1
2
3
4
  xxxx xxxx xxx1 0000 (前面提到x取反后为y,即 x & y = 0)
& yyyy yyyy yyy1 0000
---------------------
0000 0000 0001 0000

举个例子,比如

1
2
3
n     ->    0000 0000 1010 1100
-n -> 1111 1111 0101 0100 (各二进制位取反再加1)
n&-n -> 0000 0000 0000 0100

了解了之后,再来看下for (; n > 0; n -= lowbit(n)) ans++;这句为什么能求出中所有的1。不难发现,每次减掉等价于把最右边的那个“1”去掉。因此,循环执行这个操作的次数即为中1的个数。

最后,推荐大家参阅 算法-求二进制数中1的个数,这篇博客囊括了几乎所有这方面的算法~


上面提到的两个做法,复杂度近似,那么如何优化到呢?
不妨考虑那个做法的思路,中1的个数等价于这个数中1的个数再加1。
至此,我们可以用动态规划的方法来递推出答案!

代码

做法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int cal(int n) {
int ans = 0;
for (; n; n -= n&-n, ans++);
return ans;
}
vector<int> countBits(int num) {
vector<int> vec;
for (int i = 0; i <= num; ++i) vec.push_back(cal(i));
return vec;
}
};

做法二:

1
2
3
4
5
6
7
8
class Solution {
public:
vector<int> countBits(int num) {
vector<int> dp(num + 1, 0);
for (int i = 1; i <= num; ++i) dp[i] = dp[i-(i&-i)] + 1;
return dp;
}
};

分享到 评论