每日一道leetcode

338. 比特位计数 - 力扣（LeetCode）

题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 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 log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

思路（人麻了，O(n)的思路比O(nlogn)跑的还久，leetcode这个效率评估机制有点搞心态啊）

1. 最简单的实现方案是O(nlogn)的每个数去不断地右移再和1比较统计个数。（这个方法是有局限的，后面再讲）
2. 若要实现O(n)复杂度的方案，显然必须要利用之前的计算结果，根据提示，我们可以发现几个可利用的地方：
   1. 每达到2的n次方，最高的1位才会更新上去。
   2. 到达2的n次方之后，在到达2的n+1次方之前，过程中的1的变化趋势就是之前的每个变化趋势+1。
   3. 因为数字是从0开始，而0不属于2的任何次方，所以0必须单独考虑提前插入。

代码实现

O(nlogn)——有局限

class Solution {
public:vector<int> countBits(int n) {vector<int> ans;for(int i = 0; i <= n; i++) {int cnt = 0, tmp = i;while(tmp > 0) {cnt += 1 & tmp;tmp = tmp >> 1; }ans.push_back(cnt);}return ans;}
};

O(n)

class Solution {
public:vector<int> countBits(int n) {vector<int> ans;int i = 1, power = 0, iter;ans.push_back(0);while(i <= n) {if(i == pow(2, power)) {iter = 0;++power;}ans.push_back(ans[iter]+1);++iter;++i;}return ans;}
};

复杂度分析

1. 位运算版——有局限

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(n)，忽略结果数组为O(1)。

1. 秋千版（因为有点类似荡秋千，每次摆动一个相同的幅度，当重新回到推秋千的人的手中的时候再次施力，那么秋千将会走完原来摆过的路程后再更上一层，这其中秋千到达每个节点的速度都比原来到达这个节点有增加）

• 时间复杂度：O(n)。
• 空间复杂度：O(n)，忽略结果数组为O(1)。

知识积累

• 按位与运算：按每个二进制位做与操作，相同为1，不同为0.
• 按位右移运算：将整个二进制数右移，最后一项舍去，最高位直接复制原来最高位的二进制数，以达到右移能够表现出除以2的效果。

官方题解

• 对于暴力位运算法，官解提出了一个Brian Kernighan 算法——对于任何一个数n，n&(n-1)就是会将最低的1变成0，那么不断令n = n & (n-1);，直到n=0时，其操作次数就是1的个数，这个想法其实还挺巧妙的，如果没有位运算的话。