目录
题目:剑指 Offer 49. 丑数 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过啦!!!
写在最后:
题目:剑指 Offer 49. 丑数 - 力扣(Leetcode)
题目的接口:
class Solution {
public:
int nthUglyNumber(int n) {
}
};
解题思路:
丑数这道题用到一点动态规划的思想,
具体思路如下:
根据题意:
如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数,
那么我们发现,之后的丑数:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12
是前 10 个丑数。
都是前面的丑数乘2、乘3或者乘5 得来的,
那我们的思路就能变成:
从第一个数1开始,让他乘2、乘3、乘5,
第二个数也这样操作,
然后取他们的最小值作为下一个丑数,
以此类推,
三个指针,分别用来乘2、乘3、乘5,
取得最小值的那个指针指向下一个数,
如果出现两个数相等的情况,
例:
2 * 5 == 5 * 2
那就两个指针都指向下一个数,
防止重复,
最后返回第n个丑数即可。
例:
根据规则:从第一个数1开始,让他乘2、乘3、乘5
一乘二,指针往后走一个:
一乘三,指针往后走一个:
这个时候,二乘二比一乘五更小,
所以这里走的是二乘二:
然后是一乘五:
以此类推,就能计算出之后的丑数了。
下面是代码:
代码:
class Solution {
public:
int nthUglyNumber(int n) {
//创建n + 1大小的数组
vector<int> dp(n + 1);
//初始化三指针
int a = 0, b = 0, c = 0;
//数组从1开始
dp[0] = 1;
//循环
for(int i = 1; i < n; i++)
{
//让三指针*2 *3 *5 并选出最小值,就是下一个丑数
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
//取最小值
dp[i] = min(min(n2, n3), n5);
//如果该下标对应的数是下一个丑数,就让指针指向下一个
//如果有两个数结果相同,就让那两个指针都指向下一个
//防止重复
if(n2 == dp[i])
{
a++;
}
if(n3 == dp[i])
{
b++;
}
if(n5 == dp[i])
{
c++;
}
}
//最后返回第n个丑数
return dp[n - 1];
}
};
过啦!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。文章来源:https://www.toymoban.com/news/detail-405752.html
之后我还会输出更多高质量内容,欢迎收看。文章来源地址https://www.toymoban.com/news/detail-405752.html
到了这里,关于【LeetCode】剑指 Offer(25)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!