【一天一道Leetcode】丑数Ⅱ
看那个码农
共 2348字,需浏览 5分钟
· 2021-04-11
本篇推文共计2000个字,阅读时间约3分钟。
01
题目描述
题目描述:
给你一个整数n,请你找出并返回第n个丑数。
丑数就是只包含质因数 2、3、5的正整数。
示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。
提示:
1 <= n <= 1690
02
思路和方法
根据题目中丑数的定义,0和负整数一定不是整数。
1是第一个丑数。
我们通过题目中丑数的定义,丑数就是只包含质因数 2、3、5的正整数。
我们可以依次算出所有丑数,直到算到所需的第n个丑数,进行输出为止。
如何计算?
我们可以根据丑数的性质,只包含2,3,5三个质因数。我们可以分别设置三个指针用来计算丑数。
再设置一个数组用于存储从小到大遍历到的丑数。
最后返回数组中的第n个元素即可。
我们的代码输出为:
class Solution:
def nthUglyNumber(self, n: int) -> int:
if n<=0:
return false
# 放进第一个丑数:1
nums = [1]
# 三个指针初始化
i2 = 0
i3 = 0
i5 = 0
# 算出所有丑数,直到所需的第n个为止
for i in range(1,n):
# 从小到大,按照丑数定义收集丑数
ugly = min(nums[i2] * 2,nums[i3] * 3,nums[i5] * 5)
# 将丑数放进结果数组中
nums.append(ugly)
# 指针移动,从小到大地寻找丑数
if(nums[i] == nums[i2] * 2): i2 += 1
if(nums[i] == nums[i3] * 3): i3 += 1
if(nums[i] == nums[i5] * 5): i5 += 1
# 返回第n个丑数
return nums[n-1]
【年终总结】你好2021,再见2020。
【秋招纪实录】一篇特别正经的【腾讯】求职经验分享
【一天一道Leetcode】笨阶乘
你与世界
只差一个
公众号
评论
分享一份抓取某东商品名称、价格和评论数的代码
点击上方“Python共享之家”,进行关注回复“资源”即可获赠Python学习资料今日鸡汤芳草已云暮,故人殊未来。大家好,我是皮皮。一、前言前几天在Python白银交流群【邮递员】问了一个Python网络爬虫的问题,提问截图如下:代码如下:import requestsfrom
IT共享之家
0
一天肝600多篇文章,用数量对抗算法的不确定性
我写公众号七八年,总原创文章数量也只不过是650多篇。写爆文的一天就干出600多篇,多少有点震惊。背后是公众号平台进行功能调整后,从一天只能发一次文章,变改成了一天可以无限制发任意数量的文章。做公众号爆文写作变现的底层逻辑是基于公众号算法调整,从订阅规则改成了推荐机制,人人都有机会获得系统的推荐流量
python之禅
0
又踩坑了,java日期闰年处理,算少一天!
前言 今年是2024年,刚好是闰年。大家都知道,闰年是有366天的,其中二月份有29天。最近作者有个项目组出了一个生产问题,跟闰年相关的。所以写篇文章跟大家讲讲这个bug,顺便讲讲Java日期处理的一些坑,让大家避坑~...
程序员鱼皮
0
在华为,请假一天的代价是3700…
最近, 一篇 「在华为, 请假一天的代价是3700」 的帖子 引发网友热议 原 来,在华为请假会影 响每个月的奖金和年终, 所以很多人都会选择拿周末的加班来调。 在华为周末加班是双倍工资, 请假一天相当于扣除双倍的...
码农突围
0
长时舞蹈生成:数秒钟可生成极长的3D舞蹈
大数据文摘受权转载自将门创投 针对目前音乐生成3D舞蹈动作中存在的长序列生成动作质量差,生成效率低的问题,本文提出了Lodge,可以高效地根据输入音乐生成极长的3D人体舞蹈动作。本文将Lodge设计为两阶段的由粗到...
大数据文摘
0
一天涨 23k Star 的开源项目「GitHub 热点速览」
在 GitHub 上做过开源项目的小伙伴,可能都经历过截图自己项目 100 Star、1000 Star 的时刻,但有些时候事情发生的太快来不及截图,因为可能一觉醒来就破万了。这件事看似有些天方夜谭,但放在马斯克的身上就不足为...
HelloGitHub
0
今天BOSS约了个面试,HR直接发我一道面试题
javapub.net.cn 作者:JavaPub 编程学习一条龙:http://luxian.javapub.net.cn 前言 在电商、外卖、预约服务等场景中,订单超时自动取消是一个常见的业务需求。这一功能不仅提高了系统的自动化程度,还为用户提供了...
JavaPub
0
【业界动态】国家数据局等三部门共同研究提升“东数西算”网络传输...
近日,为深入贯彻党中央、国务院决策部署,加快落实《深入实施“东数西算”工程 加快构建全国一体化算力网的实施意见》,国家数据局会同国家发展改革委、工业和信息化部围绕充分发挥“东数西算”网络传输效能,进一步提...
MoMaek
0