题目描述
leetcode 第338题:比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例:
输入: 5
输出: [0,1,1,2,1,2]
解题方法
动态规划
参照题解
- 解题思路
定义数组dp记录每个数字转二进制数后1的个数
因为0的二进制中,1个数为0,所以dp初始插入0
在[1,num]区间内遍历数字i
每次迭代,dp记录i中二进制数中1的个数
如果i是奇数,那它的二进制数一定比前面那个偶数多一个1
如果i是偶数,那它的二进制数中1的个数一定等于除以2之后的那个数中1的个数
遍历完成后返回dp即可
- 复杂度
时间复杂度:O(num)
空间复杂度:O(1)
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |
- 文字草稿
num=5
偶数0,1出现的次数=0
奇数1,1出现的次数=偶数0中1出现的次数0+1=1
偶数2,1出现的次数=奇数1中1出现的次数1
奇数3,1出现的次数=偶数2中1出现的次数1+1=2
偶数4,1出现的次数=奇数3中1出现的次数1
奇数5,1出现的次数=偶数4中1出现的次数1+1=2
最终返回[0,1,1,2,1,2]