本文主要是介绍264.丑数Ⅱ。简单易懂，代码简单0ms，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// 后面的丑数一定由前面的丑数乘以2，或者乘以3，或者乘以5得来。
// 例如，8,9,10,12一定是1, 2, 3, 4, 5, 6乘以2,3,5三个质数中的某一个得到。
// 从第一个丑数开始，一个个数丑数，并确保数出来的丑数是递增的，直到数到第n个丑数，得到答案
// 1, 2, 3, 4, 5, 6中的每一个丑数都有一次机会与2相乘，一次机会与3相乘，一次机会与5相乘（一共有18次机会形成18个新丑数），来得到更大的一个丑数。
// 可以用三指针,p1,p2,p3分别指向123456，下次寻找丑数时，对这三个"123456"分别乘2，乘3，乘6判断哪个最小
// 那么就是下个丑数，然后对应的指针+1
class Solution {public int nthUglyNumber(int n) {int[] dp = new int[n + 1];dp[1] = 1;int p2 = 1, p3 = 1, p5 = 1;for (int i = 2; i <= n; ++i) {int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;dp[i] = Math.min(Math.min(num2, num3), num5);if(dp[i] == num2) ++p2;if(dp[i] == num3) ++p3;if(dp[i] == num5) ++p5;}return dp[n];}
}
这篇关于264.丑数Ⅱ。简单易懂，代码简单0ms的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
