LeetcodeMedium-【面试题49. 丑数】*

标签: Leetcode  # 剑指offer

我们把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。

注意:本题与主站 264 题相同:https://leetcode-cn.com/problems/ugly-number-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路1:动态规划

题解
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums = [1] * n
        index1 = 0
        index2 = 0
        index3 = 0
        for i in range(1, n):
            nums[i] = min(nums[index1]*2, min(nums[index2]*3, nums[index3]*5))
            # 必须分开判断,不能用分支,因为上面的可能有相等的情况,相等的都要加+1,例如:2*3和3*2
            if nums[i] == nums[index1] * 2:
                index1 += 1
            if nums[i] == nums[index2] * 3:
                index2 += 1
            if nums[i] == nums[index3] * 5:
                index3 += 1
        # print(nums)
        return nums[n-1]
版权声明:本文为qq_39451578原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39451578/article/details/106052410

智能推荐

双路快速排序法

快速排序法的优化——双路快速排序 上一节我们自己动手写的一个快速排序的算法,在随机数测试中表现得非常好,然而,我们在用高度有序的数组进行测试的时候,发现快速排序的效率变得异常的低下,比归并排序的效率低得多了,近似退回了O(n^2)的复杂度,这是为什么呢?首先让我们来分析一下归并排序的算法思想,归并排序之所以能够达到O(logn)的复杂度,多亏了递归,递归使得把数组不断的二分...

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

猜你喜欢

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...

rabbitmq五种模式详解(含实现代码)

1.简单模式 当生产端发送消息到交换机,交换机根据消息属性发送到队列,消费者监听绑定队列实现消息的接收和消费逻辑编写.简单模式下,强调的一个队列queue只被一个消费者监听消费. 1.1 结构   生产者:生成消息,发送到交换机 交换机:根据消息属性,将消息发送给队列 消费者:监听这个队列,发现消息后,获取消息执行消费逻辑 1.2应用场景 常见的应用场景就是一发,一接的结构 例如: 手机...