【一天一道Leetcode】比特位计数
看那个码农
共 1831字,需浏览 4分钟
· 2021-03-04
本篇推文共计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】数组不可变
你与世界
只差一个
公众号
评论
机械臂抓取/6D位姿估计/三维点云/缺陷检测方向交流群成立啦
点击下方卡片,关注「3D视觉工坊」公众号选择星标,干货第一时间送达添加小助理: dddvision,备注:研究方向+学校/公司+昵称(如机械臂抓取+清华+小草莓)▲长按扫码添加助理大家好,我是小草莓!我们3D视觉工坊成立了计算机视觉各个方向的交流群,详细如下所示,欢迎添加小助理,邀请你加群!3D视觉
3D视觉工坊
0
【比特币减半后价格表现大揭秘】历史数据告诉你什么?
加密货币现状的十张图表Glassnode 和 Coinbase 发布了《加密货币市场指南》,这是一个季度系列,旨在提供对加密货币市场主要发展的详细分析。以下是报告中引起我们注意的10张图表:1.比特币主导地位从50%上升至52%通常由减半引发的山寨季会降低比特币的主导地位,使其更倾向于新的山寨币。这
区块链头条
0
2028年的下一次减半,比特币的价格会在哪里?
第四次比特币减半正式表明支付给矿工的奖励从每个区块 6.25 比特币减少到 3.125 比特币。比特币支付的平均费用在 4 月 20 日(比特币第四次减半当天)达到创纪录的 128 美元后仅一天就急剧下降。根据mempool.space 的数据 ,中等优先级交易的平均费用已降至 8 至 1
区块链头条
1
一天肝600多篇文章,用数量对抗算法的不确定性
我写公众号七八年,总原创文章数量也只不过是650多篇。写爆文的一天就干出600多篇,多少有点震惊。背后是公众号平台进行功能调整后,从一天只能发一次文章,变改成了一天可以无限制发任意数量的文章。做公众号爆文写作变现的底层逻辑是基于公众号算法调整,从订阅规则改成了推荐机制,人人都有机会获得系统的推荐流量
python之禅
0
如何调整策略以应对即将到来的比特币减半?
摘要 随着比特币减半的临近,ETF 的巨大购买力将掩盖减半带来的传统供应挤压效应。这种动态要求交易者需要平衡减半的历史影响与 ETF 对比特币可用性和价格的当代影响。 我们正接近市场周期的阶段,比特币的供应动态...
区块链头条
0
又踩坑了,java日期闰年处理,算少一天!
前言 今年是2024年,刚好是闰年。大家都知道,闰年是有366天的,其中二月份有29天。最近作者有个项目组出了一个生产问题,跟闰年相关的。所以写篇文章跟大家讲讲这个bug,顺便讲讲Java日期处理的一些坑,让大家避坑~...
程序员鱼皮
0
在华为,请假一天的代价是3700…
最近, 一篇 「在华为, 请假一天的代价是3700」 的帖子 引发网友热议 原 来,在华为请假会影 响每个月的奖金和年终, 所以很多人都会选择拿周末的加班来调。 在华为周末加班是双倍工资, 请假一天相当于扣除双倍的...
码农突围
0
一天涨 23k Star 的开源项目「GitHub 热点速览」
在 GitHub 上做过开源项目的小伙伴,可能都经历过截图自己项目 100 Star、1000 Star 的时刻,但有些时候事情发生的太快来不及截图,因为可能一觉醒来就破万了。这件事看似有些天方夜谭,但放在马斯克的身上就不足为...
HelloGitHub
0