题目
给定一个非负整数
num
。对于0 ≤ i ≤ num
范围中的每个数字i
,计算其二进制数中的1
的数目并将它们作为数组返回。示例 1:
1
2 输入: 2
输出: [0,1,1]示例 2:
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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
暴力解法
对输入$num$,范围内有$num+1$个数字,每个数字为$sizeof(int)$位,遍历每个数字的所有位并计数,保存在返回数组中即可。时间复杂度$O(N*sizeof(int))==O(N)$。
动态规划
事实上,对于一个数的二进制表示中1的个数,不同的树之间是有推导关系的,因此暴力法中我们实际上做了重复计算,可以用动态规划解决。
对于2的所有幂次方
,其在一个数的二进制表示中都用一个1
表示。一个整数一定可以拆分成2的幂次的和
,而其拆分结果的最小数量即为1
的数量。
注意,在这个拆分的过程中不可能出现拆分出两个相同元素的情况,因为两个相同的元素总可以合成一个大的元素。
因此,我们计算一个数n
的1的位数
时,其状态转移方程:
1 | countBits(n)=countBits(n - pow(2, (int)log2(n))) + 1; |
其次,注意在初始化状态的时候考虑特殊输入,比如初始化dp[1]
,要考虑输入为0
。
1 | class Solution { |
动态规划的位运算优化
对于一个数,右移1位的结果相当于对其本身除以二的结果向下取整,也相当于舍弃掉最低位,那么新的数字的二进制表示中,1的个数根据原数的最低位是否为1进行相应计算。
1 | dp[i] = dp[i>>1] + (i&1); |
代码如下:
1 | class Solution { |
- 时间复杂度$O(N)$
- 空间复杂度$O(N)$