【一天一道Leetcode】比特位计数
本篇推文共计2000个字,阅读时间约3分钟。
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,3
02
代码分析
由题目描述可知
设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,再见2020。
【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台
【秋招纪实录】一篇特别正经的【腾讯】求职经验分享
【一天一道Leetcode】矩阵不可变
【一天一道Leetcode】单调数列
【一天一道Leetcode】数组不可变
你与世界
只差一个
公众号
评论