博文中会简要介绍Leetcode P0264题目分析及解题思路。
“Ugly Number II”是一道中等难度的题目。这道题的思路是用动态规划，
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
为什么想到动态规划？
由于我们需要知道第n个丑数，那么自然可以想到我们其实本质上再求解一个长度为n的丑数序列。那么序列上第n个丑数则一定等于2、3和5乘上前缀序列中对应的某个丑数所得到的结果中的最小者。
这种想法本质上是一个递归，但是我们并不明确知道2、3和5对应的丑数乘数，因此我们需要至少记录这三个对应的乘数，但又由于我们需要移动指针来更新乘数，所以我们其实在记忆化一个过程（序列）。往往在这种情况下，我们会使用到动态规划。
最优子结构是什么，怎么用？
最优子结构是“下一个丑数取决于2、3和5乘上前缀序列中对应的丑数所得到的结果中的最小值”。
根据上述的最优子结构，我们需要分别为2、3和5分配一个指针，用来指向对应的最小因子。所有丑数中的最小值是1，所以丑数序列初始化后的第一个丑数是1，且三个指针指向1。而后通过比较2、3和5与对应指针上的丑数的乘积可以得到序列上的下一个丑数，并且向后移动对应的指针，然后重复上述操作即可。
以下是Java的题解代码实现。
class Solution {
public int nthUglyNumber(int n) {
if (n == 1)
return 1;
List<Integer> ugly = new ArrayList<>();
ugly.add(1);
int p2 = 0, p3 = 0, p5 = 0;
while (n > 1) {
int next = Math.min(ugly.get(p2)*2,
Math.min(ugly.get(p3)*3, ugly.get(p5)*5)
);
ugly.add(next);
if (next == ugly.get(p2)*2)
p2++;
if (next == ugly.get(p3)*3)
p3++;
if (next == ugly.get(p5)*5)
p5++;
n--;
}
return ugly.get(ugly.size()-1);
}
}
以下是C++的题解代码实现。
class Solution {
public:
int nthUglyNumber(int n) {
if (n == 1)
return 1;
vector<int> ugly(1, 0);
ugly[0] = 1;
int pf2 = 0, pf3 = 0, pf5 = 0;
while (n > 1) {
int next = min(ugly[pf2]*2,
min(ugly[pf3]*3, ugly[pf5]*5)
);
ugly.push_back(next);
if (next == ugly[pf2]*2)
pf2++;
if (next == ugly[pf3]*3)
pf3++;
if (next == ugly[pf5]*5)
pf5++;
n--;
}
return ugly.back();
}
};