1.丑数（263 - 易）
题目描述：给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 :
输入：n = 6
输出：true
解释：6 = 2 × 3
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
思路：数学问题：依次使用所给质因数缩小给定值，最后给定值为1，即为丑数。注：0和负数不是丑数。
代码实现：
public boolean isUgly(int n) {
if (n <= 0) return false;
int[] nums = {5, 3, 2};
for (int num : nums) {
while (n % num == 0) {
n /= num;
}
}
return n == 1;
}
2.丑数II（264 - 中）
题目描述：给你一个整数 n ，请你找出并返回第 n 个 丑数 。
示例 :
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
思路：动态规划思想（空间换时间）
和1不同的是，本题是寻找第n个丑数，是自下向上。我们发现已有丑数都是基于之前的丑数乘上质因数。
这里使用三指针（代表第几个数的几倍，2,3,5倍），定义dp动态数组，其中，dp[i]：第i+1个丑数。状态转移方程：每次循环确定当前最小的一个丑数。
代码实现：
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; ++i) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(n2, Math.min(n3, n5));
if (dp[i] == n2) a++;
if (dp[i] == n3) b++;
if (dp[i] == n5) c++;
}
return dp[n - 1];
}
