【面试题】丑数(动态规划)

标签: 剑指offer  java  动态规划  数据结构  算法  leetcode

题目描述

在这里插入图片描述

解题思路

根据丑数的定义, 丑数应该是另⼀个丑数乘以 2、 3或者 5的结果(1除外),满足递推性质 。 因此我们可以创建⼀个数组, ⾥⾯的数字是排好序的丑数, 每⼀个丑数都是前⾯的丑数乘以 2、 3或者 5得到的。
在这里插入图片描述

Java

动态规划法

class Solution {
    public int nthUglyNumber(int n) {
        if(n <= 0) return 0;
        int[] dp = new int[n]; // 定义状态表,dp[i]代表第 i + 1 个丑数。
        int a = 0, b = 0, c = 0;
        dp[0] = 1; // 第一个丑数为 1
        for(int i=1; i<dp.length; i++) {
            dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);
            // 分别判断dp[i]与dp[a]*2,dp[b]*3,dp[c]*5的大小关系,若相等则将对应索引 a,b,c 加1
            // 这里不采用if-else的原因是,存在2*某个丑数 ,3*某个丑数,5*某个丑数相同的情况。当有多个索引满足条件时,均要+1
            if(dp[a]*2 == dp[i]) a++;
            if(dp[b]*3 == dp[i]) b++;
            if(dp[c]*5 == dp[i]) c++;
        }
        return dp[n-1]; // 返回第 n 个丑数
    }
}

参考

https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/

版权声明:本文为Mr_SCX原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Mr_SCX/article/details/107299209

智能推荐

LeetCode刷题(十四)-----字符串-------medium部分(Java、C++)

22. 括号生成 [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] 思路一:c++版本,暴力构造法+剪枝 构造法生成括号 首先分析:需要构造有效的括号,数量上,左右括号分别都为n个。 其次:左括号的数量需要大于等于右括号的数...

双路快速排序法

快速排序法的优化——双路快速排序 上一节我们自己动手写的一个快速排序的算法,在随机数测试中表现得非常好,然而,我们在用高度有序的数组进行测试的时候,发现快速排序的效率变得异常的低下,比归并排序的效率低得多了,近似退回了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,修改配置文...