【3.3】LeetCode每日一题· 比特位计数

2021年03月03日 10时15分

标签： LeetCode 递推

## 题目描述
给定一个非负整数**num**。对于**0 ≤ i ≤ num**范围中的每个数字**i**，计算其二进制数中的**1**的数目并将它们作为数组返回。

#### 示例1
	输入: 2
	输出: [0,1,1]

#### 示例2
	输入: 5
	输出: [0,1,1,2,1,2]

#### 进阶
* 给出时间复杂度为**O(n\*sizeof(integer))**的解答非常容易。但你可以在线性时间**O(n)**内用一趟扫描做到吗？
* 要求算法的空间复杂度为**O(n)**。
* 你能进一步完善解法吗？要求在C\++或任何其他语言中不使用任何内置函数（如 C\++ 中的**\_\_builtin\_popcount**）来执行此操作。

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/counting-bits/ "题目链接")

## 解题思路和代码
### 暴力+内置函数`__builtin_popcount`
C\++内置函数`__builtin_popcount`能够计算某一无符号32位整数中二进制位为1的个数，因此可以直接暴力便利`0 <= i <= num`中的每个`i`，然后调用`__builtin_popcount`函数即可。

class Solution {
	public:
		vector<int> countBits(int num) {
			vector<int> res;
			for(int i = 0; i <= num; i++){
				res.push_back(__builtin_popcount(i));
			}
			return res;
		}
	};

#### 用时和内存
> 执行用时：4 ms，在所有 C\++提交中击败了96.36%的用户
> 内存消耗：8.2 MB，在所有 C\++提交中击败了26.70%的用户

### 暴力+自己实现函数`popcount`
我们也可以手动实现内置函数，思路是每次统计**i**的最低位是否是**1**，然后删除最后一位继续统计下一位（右移操作实现）。
	
	class Solution {
	public:
		inline int popcount(int i){
			int res = 0;
			while(i){
				if(i&1) res++;
				i >>= 1;
			}
			return res;
		}
		vector<int> countBits(int num) {
			vector<int> res;
			for(int i = 0; i <= num; i++){
				res.push_back(popcount(i));
			}
			return res;
		}
	};

#### 用时和内存
> 执行用时：12 ms，在所有 C\++提交中击败了20.35%的用户
> 内存消耗：8.4 MB，在所有 C\++提交中击败了17.23%的用户

### 动态规划
以上两种方法都需要遍历一边数字，然后用$$O(\log N)$$的时间复杂度求出数字中二进制位为1的个数。然而，在求某一数字的二进制位为1的个数时，可以用之前已经计算过的答案以$$O(1)$$的时间推出。记$$f(i)$$为数字$$i$$中二进制位为1的个数，则有
```math
\displaystyle
f(i) = (i \% 2) + f(\frac{i}{2}),
```

即数字**i**中二进制位为**1**的个数，可以分成两部分统计：
1. 第一部分统计**i**的最后一位是否为**1** ($$ i\%2 $$)，代码中可以使用`i&1`取得

2. 然后统计去掉最后一位（右移，相当于除以2）后，剩下的数字中二进制位为1的个数，即$$f(\frac{i}{2}) $$。

因此可以得到代码

class Solution {
		public:
			vector<int> countBits(int num) {
				vector<int> res(num+1);
				for(int i = 0; i <= num; i++){
					res[i] = (i&1) + res[i>>1];
				}
				return res;
			}
		};

#### 用时和内存
> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：7.7 MB，在所有 C\++提交中击败了71.84%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.3】LeetCode每日一题· 比特位计数

所有评论

暂无评论

新增评论