题目链接：https://leetcode-cn.com/problems/ugly-number/
分类：
数学（丑数的特点：只包含质因数2,3,5）递归实现、迭代实现（拿2，3，5循环除num）丑数的特点是只包含质因数2,3，5，且1是丑数。
对于给定的输入num，要判断num是不是丑数，就不断拿2，3 ，5去除num，如果能被其中某个质因数整除，就拿整除结果继续除以2，3，5：
如果num最终 == 1，说明num本身为1或能够被2，3，5整除，属于丑数，返回true；如果num最总 == 0，说明num不能被2,3，5整除，不属于丑数，返回false。根据上面的思路，可以得出递归实现和迭代实现：
//递归实现 class Solution { public boolean isUgly(int num) { if(num == 1) return true; if(num <= 0 ) return false; //递归判断一个数分别能否被2，3，5整除，且整除之后的结果仍能被2，3，5整除，，，直到商=1 if(num % 2 == 0){ return isUgly(num/2); } else if(num % 3 == 0){ return isUgly(num / 3); } else if(num % 5 == 0){ return isUgly(num / 5); } //2，3，5都不能整除它，所以返回false return false; } } /* 迭代实现： 按照2,3,5 的顺序依次循环除num，当除到不是当前因数的倍数时， 就进行下一个因数的整除，这样，最后剩下的数为1则为丑数 */ class Solution { public boolean isUgly(int num) { if(num == 0) return false; //将2,3,5存入数组便于循环使用 while(num % 2 == 0) num /= 2; while(num % 3 == 0) num /= 3; while(num % 5 == 0) num /= 5; return num == 1; } }题目链接：https://leetcode-cn.com/problems/ugly-number-ii/
分类：
数学（丑数：只包含质因子2，3，5的正整数；暴力解：每个数字都判断是否为丑数，直到找到第n个丑数）；堆（PriorityQueue作为小顶堆存放丑数；顶部 = 当前的最小丑数；HashSet去重）；动态规划（dp数组按升序存放丑数、三指针法构造dp数组）。这题和263相比，需要找出从小到大排序的第n个丑数，因此涉及到丑数的排序和存储：
元素的存储和排序可以使用堆这一数据结构同时解决（思路2）；也可以使用动态规划，但是动态规划的dp数组在构造时还需要考虑排序问题，本题使用三指针法解决dp元素的排序问题（思路3）。设置一个计数器，初始值 = 0，然后每个数字都判断是否只包含2，3，5质因数，如果当前数字是丑数，计数器 + 1，直到计数器 == n，当前数字就是第n个丑数。
这里不再赘述。
创建一个小根堆用于存放丑数，每次获取顶部就是获取当前最小的丑数。堆最先存放1，然后依次存放2，3，5以及这三个数的2，3，5倍。
算法流程：
初始时计数器count = 0，每次从小根堆中取出一个当前最小的元素时count + 1，直到count == n，即此时弹出的小根堆顶部就是第n个丑数。
同时每从堆中取一个数时，就把当前数的2，3，5倍都入堆，前提是要做去重，可以用set来实现。
为什么当count == n时，小顶堆顶部就是第n个丑数？ 当第 i 个数从堆中取出来时，又会同时向堆中加入当前弹出元素的2，3，5倍数字，当前弹出的元素是堆里最小的元素，它的2倍必然是set集合元素之外最小的丑数了；且每个数弹出时，又会加入3个丑数进去，所以当count == n时我们从一开始到现在找到的丑数总数（可能在堆内，也可能已出堆）一定是 > n的，所以当计数器count == n时必然能从中取到第n个丑数。
1、数值溢出问题 丑数的计算过程中可能出现数值 > int的上界，所以我们可以将小顶堆、HashSet的泛型设置为Long，计算每个丑数时也用 long型的变量来存放。
2、丑数去重问题 我们按算法流程生成丑数时，可能会得到重复的丑数，例如：丑数2的3倍=6也是丑数，加入堆中；丑数3的2倍=6，已经出现过，所以不能重复加入堆中。
我们可以使用一个Set来存放已经出现过的丑数来达到去重的目的。
也可以将PriorityQueue + Set替换成TreeSet，可以同时达到排序和去重的效果。
实现代码：
class Solution { int[] array = {2,3,5}; public int nthUglyNumber(int n) { //特殊用例 if(n <= 0) return -1; //小顶堆存放丑数，配合计数器找到第n个出堆的元素就是第n个丑数 Queue<Long> queue = new PriorityQueue<>();//优先级队列默认是小顶堆 //set用于去重，已经生成过的丑数就不再加入堆，以免影响n的判断 Set<Long> set = new HashSet<>(); //将1加入队列 queue.offer((long)1); set.add((long)1); int count = 1;//计数器 long num = 0;//用于存放堆弹出的顶部，便于最后返回 while(count <= n){ //将堆顶部弹出，此时顶部是当前最小丑数（除已出堆以外的所有丑数中最小） num = queue.poll(); //弹出顶部时，将它的2，3，5倍丑数都加入到堆和set中，加入前先去重 for(int i = 0; i < 3; i++){ long temp = num * array[i]; if(!set.contains(temp)){ queue.offer(temp); set.add(temp); } } //弹出一个元素，计数器才+1 count++; } return (int)num; } }丑数数量是有限的，且可以通过一定规则生成：前面的丑数就作为后面数生成时的因子，关键在于大小的排列。
使用三个指针 i_2, i_3和 i_5，标记所指向丑数要乘以的因子。
算法很简单：设置一个dp数组按升序存放丑数，在 2nums[i_2]，3nums[i_3]和2*nums[i_5]中选出最小的丑数并添加到数组中。并将该丑数对应的因子指针往前走一步。重复该步骤直到计算出第n个丑数。
参考：https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode/
class Solution { public int nthUglyNumber(int n) { //特殊用例 if(n <= 0) return -1; //数组存放计算过的丑数，以便后续直接使用 int[] ugly = new int[1690]; ugly[0] = 1; //三指针各自从0开始移动 int i_2 = 0, i_3 = 0, i_5 = 0; for(int i = 1; i < n; i++){ int factor2 = ugly[i_2] * 2; int factor3 = ugly[i_3] * 3; int factor5 = ugly[i_5] * 5; int min = Math.min(Math.min(factor2,factor3) , factor5); ugly[i] = min; if(min == factor2) i_2++; if(min == factor3) i_3++; if(min == factor5) i_5++; } return ugly[n - 1]; } }