目錄
題目：劍指 Offer 49. 丑數(shù) - 力扣（Leetcode）
題目的接口：
解題思路：
代碼：
過啦?。?！
寫在最后：
題目：劍指 Offer 49. 丑數(shù) - 力扣（Leetcode）
題目的接口：
class Solution {
public:
int nthUglyNumber(int n) {
}
};
解題思路：
丑數(shù)這道題用到一點動態(tài)規(guī)劃的思想，
具體思路如下：
根據(jù)題意：
如果說第一個丑數(shù)是一，包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)，
那么我們發(fā)現(xiàn)，之后的丑數(shù)：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數(shù)。都是前面的丑數(shù)乘2、乘3或者乘5 得來的，
那我們的思路就能變成：
從第一個數(shù)1開始，讓他乘2、乘3、乘5，
第二個數(shù)也這樣操作，
然后取他們的最小值作為下一個丑數(shù)，
以此類推，?
三個指針，分別用來乘2、乘3、乘5，
取得最小值的那個指針指向下一個數(shù)，
如果出現(xiàn)兩個數(shù)相等的情況，
例：
2 * 5 == 5 * 2
那就兩個指針都指向下一個數(shù)，
防止重復(fù)，
最后返回第n個丑數(shù)即可。
例：
根據(jù)規(guī)則：從第一個數(shù)1開始，讓他乘2、乘3、乘5
一乘二，指針往后走一個：
一乘三，指針往后走一個：
這個時候，二乘二比一乘五更小，
所以這里走的是二乘二：
??
然后是一乘五：
?
?以此類推，就能計算出之后的丑數(shù)了。
?下面是代碼：
代碼：
class Solution {
public:
int nthUglyNumber(int n) {
//創(chuàng)建n + 1大小的數(shù)組
vector<int> dp(n + 1);
//初始化三指針
int a = 0, b = 0, c = 0;
//數(shù)組從1開始
dp[0] = 1;
//循環(huán)
for(int i = 1; i < n; i++)
{
//讓三指針*2 *3 *5 并選出最小值，就是下一個丑數(shù)
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
//取最小值
dp[i] = min(min(n2, n3), n5);
//如果該下標(biāo)對應(yīng)的數(shù)是下一個丑數(shù)，就讓指針指向下一個
//如果有兩個數(shù)結(jié)果相同，就讓那兩個指針都指向下一個
//防止重復(fù)
if(n2 == dp[i])
{
a++;
}
if(n3 == dp[i])
{
b++;
}
if(n5 == dp[i])
{
c++;
}
}
//最后返回第n個丑數(shù)
return dp[n - 1];
}
};過啦?。?！
寫在最后：
以上就是本篇文章的內(nèi)容了，感謝你的閱讀。
如果喜歡本文的話，歡迎點贊和評論，寫下你的見解。
如果想和我一起學(xué)習(xí)編程，不妨點個關(guān)注，我們一起學(xué)習(xí)，一同成長。文章來源：http://www.zghlxwxcb.cn/news/detail-405752.html
之后我還會輸出更多高質(zhì)量內(nèi)容，歡迎收看。文章來源地址http://www.zghlxwxcb.cn/news/detail-405752.html
到了這里，關(guān)于【LeetCode】劍指 Offer（25）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
