【一天一道Leetcode】比特位计数
【一天一道Leetcode】比特位计数
潘永斌
发布于 2021-03-09 16:18:00
发布于 2021-03-09 16:18:00
代码可运行
运行总次数：0
代码可运行
01
题目描述
题目描述：
给定一个非负整数num。
对于0≤i≤num范围中的每个数字i，计算其二进制数中的1的数目并将它们作为数组返回。
示例：
输入: 2
输出: [0,1,1]
解释：
十进制0，1，2三个数的二进制数分别为
0：0000 含有0个1
1：0001 含有1个1
2：0010 含有1个1
因此输出为0，1，1输入: 7
输出: [0,1,1,2,1,2,2,3]
解释：
十进制0,1,2,3,4,5,6,7八个数的二进制数分别为
0：0000 含有0个1
1：0001 含有1个1
2：0010 含有1个1
3：0011 含有2个1
4：0100 含有1个1
5：0101 含有2个1
6：0110 含有2个1
7：0111 含有3个1
因此输出为0，1，1，2，1，2，2，302
代码分析
由题目描述可知
设f(x)为x二进制中1的个数
如f(3)=2
3的二进制表达式为0011，故二进制中1的个数为2。
1.如果输入i为偶数，那么f(i)=f(i//2),因为i//2本质上是i的二进制右移一位，高位补零，所以1的数量不变。
如4, 6, 8等
4的二进制为0100，2的二进制为0010
f(4)=1=f(2)
6的二进制为0110，3的二进制为0011
f(6)=2=f(3)
8的二进制为1000，4的二进制为0100
f(8)=1=f(4)2.如果输入i为奇数，那么f(i)=f(i-1)+1，i为奇数时，i-1必定为偶数，而偶数的二进制最低位一定是0，
那么该偶数二进制加1后的二进制最低位变为1且不会进位，所以奇数二进制中1的个数比它上一个偶数二进制中1的个数多一个1，
即f(i)=f(i-1)+1。
如3, 5, 7, 9等
3的二进制为0011，3-1=2的二进制为0010
f(3)=f(2)+1=1+1=2
5的二进制为0101，4的二进制为0100
f(5)=f(4)+1=1+1=2
7的二进制为0111，6的二进制为0110
f(7)=f(6)+1=2+1=3
9的二进制为0101，8的二进制为0100
f(9)=f(8)+1=1+1=2所以代码为：
class Solution:
def countBits(self, num: int) -> List[int]:
res=[0]
for i in range(1,num+1):
if i%2==0:
res.append(res[i//2])
else:
res.append(res[i-1]+1)
return res本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
