LC 338. 比特位计数
题目描述
这是 LeetCode 上的 338. 比特位计数 ,难度为 简单。
给定一个非负整数 num
。对于 0 ≤ i ≤ num
范围中的每个数字 i
,计算其二进制数中的 $1$ 的数目并将它们作为数组返回。
示例 1:1
2
3输入: 2
输出: [0,1,1]
示例 2:1
2
3输入: 5
输出: [0,1,1,2,1,2]
进阶:
- 给出时间复杂度为 $O(n \times sizeof(integer))$ 的解答非常容易。但你可以在线性时间 $O(n)$ 内用一趟扫描做到吗?
- 要求算法的空间复杂度为 $O(n)$ 。
- 你能进一步完善解法吗?要求在
C++
或任何其他语言中不使用任何内置函数(如C++
中的__builtin_popcount
)来执行此操作。
模拟
这道题要对每个数进行统计,因此不会有比 $O(n)$ 更低的做法。
而很容易想到的朴素做法是对每个数进行「位运算」计数,每个数都是 $32$ 位的,因此是一个 $O(32n)$ 的做法。
代码:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) ans[i] = getCnt(i);
return ans;
}
int getCnt(int u) {
int ans = 0;
for (int i = 0; i < 32; i++) ans += (u >> i) & 1;
return ans;
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:使用与输入同等规模的空间存储答案。复杂度为 $O(n)$
动态规划
事实上,这道题是有严格 $O(n)$ 的解法的,要求 $O(n)$ 复杂度又是输出方案的题,通常就是递推的 DP 题。
用已算出的值去凑出要算的值。
那么对于这类问题我们该如何考虑呢?一般是靠经验,如果实在没见过这类题型的话,我们就需要在纸上画一下,分析一下我们朴素做法的最后一步是怎么进行的。
不失一般性的,假设当前我要统计的数的 i
,i
对应的二进制表示是 00000...0010100101
(共 32 位)
如果我们是使用「朴素解法」求解的话,无论是从高位进行统计,还是从低位进行统计,最后一位扫描的都是边缘的数(如果是 1 就计数,不是 1 就不计数)。
- 从低位到高位,最后一步在扫描最高位之前,统计出 1 的个数应该等同于将
i
左移一位,并在最低位补 0,也就是等于ans[i << 1]
,这时候就要求我们在计算i
的时候i << 1
已经被算出来(从大到小遍历) - 从高位到低位,最后一步在扫描最低位之前,统计出 1 的个数应该等同于将
i
右移一位,并在最高位补 0,也就是等于ans[i >> 1]
,这时候就要求我们在计算i
的时候i >> 1
已经被算出来(从小到大遍历)
通过对「朴素做法」的最后一步分析,转移方程就出来了:
- 当从大到小遍历 :$f(i) = f(i << 1) + ((i >>31 ) \& 1)$
- 当从小到大遍历 :$f(i) = f(i >> 1) + ( i \& 1 )$
代码:1
2
3
4
5
6
7
8
9class Solution {
// 从小到大遍历
public int[] countBits(int n) {
int[] ans = new int[n + 1];
// ans[i] = 「i >> 1 所包含的 1 的个数」+「i 的最低位是否为 1」
for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
}
-1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
// 从大到小遍历
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = n; i >= 0; i--) {
// 如果计算 i 所需要的 i << 1 超过 n,则不存储在 ans 内,需要额外计算
int u = i << 1 <= n ? ans[i << 1] : getCnt(i << 1);
// ans[i] =「i << 1 所包含的 1 的个数」 + 「i 的最高位是否为 1」
ans[i] = u + ((i >> 31) & 1);
}
return ans;
}
int getCnt(int u) {
int ans = 0;
for (int i = 0; i < 32; i++) ans += (u >> i) & 1;
return ans;
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:使用与输入同等规模的空间存储答案。复杂度为 $O(n)$
位运算说明
a >> b & 1
代表检查a
的第b
位是否为 $1$,有两种可能性 $0$ 或者 $1$a += 1 << b
代表将a
的第b
位设置为 $1$ (当第b
位为 $0$ 的时候适用)
如不想写对第 b
位为 $0$ 的前置判断,a += 1 << b
也可以改成 a |= 1 << b
在之前的题解我就强调过,以上两个操作在位运算中使用频率超高,建议每位同学都加深理解。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.338
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!