剑指Offer 49 丑数

超、凢脫俗 2021-12-19 04:21 265阅读 0赞

[丑数][Link 1]

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

1 # -*- coding:utf-8 -*-
     2 class Solution:
     3     def GetUglyNumber_Solution(self, index):
     4         if index <= 6:
     5             return index
     6         i2,i3,i5= 0,0,0
     7         dp = [0] * index
     8         dp[0] = 1
     9         for i in range(1,index):
    10             next2 = dp[i2] * 2
    11             next3 = dp[i3] * 3
    12             next5 = dp[i5] * 5
    13             dp[i] = min(next2,min(next3,next5))
    14             if dp[i] == next2:
    15                 i2 += 1
    16             if dp[i] == next3:
    17                 i3 += 1
    18             if dp[i] == next5:
    19                 i5 += 1
    20         return dp[index-1]
    21         # write code here

转载于:https://www.cnblogs.com/asenyang/p/11022941.html

[Link 1]: https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 49. 丑数【2】

> 难度等级：中等 > 上一篇算法： > > [ 剑指 Offer 61. 扑克牌中的顺子【数学】][_ Offer 61.] > 力扣此题地址： > > [剑指 Of

痛定思痛。/ 2023年09月27日 12:17/ 0 赞/ 97 阅读

相关 LeetCode:剑指 Offer 49. 丑数(C语言)

题目描述：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例: 输入: n = 10 输出:

今天药忘吃喽~/ 2022年12月17日 01:19/ 0 赞/ 125 阅读

相关【剑指Offer】49. 丑数

[NowCoder][] 题目描述把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习

以你之姓@/ 2022年12月01日 14:06/ 0 赞/ 100 阅读

相关剑指 Offer 49. 丑数

题目我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例: > 输入: n = 10 > 输出

小咪咪/ 2022年11月21日 14:57/ 0 赞/ 47 阅读

相关【剑指offer】面试题49：丑数

题目我们把只包含因子2、3 和 5 的数称作丑数(Ugly Number) 求按照从小到大的顺序的第1500个丑数。例如，6、8都是丑数，但是14不是，因为它

川长思鸟来/ 2022年06月11日 05:36/ 0 赞/ 165 阅读

相关剑指Offer-丑数

转载地址：[https://www.jianshu.com/p/9598e96ea6b6][https_www.jianshu.com_p_9598e96ea6b6] 题目：

痛定思痛。/ 2022年05月23日 07:21/ 0 赞/ 206 阅读

相关剑指Offer | 丑数

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

超、凢脫俗/ 2022年05月23日 05:26/ 0 赞/ 175 阅读

相关剑指Offer-丑数

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

朱雀/ 2022年02月19日 01:56/ 0 赞/ 204 阅读

相关剑指Offer 49 丑数

[丑数][Link 1] 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数

超、凢脫俗/ 2021年12月19日 04:21/ 0 赞/ 266 阅读

相关剑指offer：丑数

题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大

亦凉/ 2021年12月09日 01:09/ 0 赞/ 285 阅读