丑数1和2--动态规划法的一道不错的题

1.丑数1public static boolean isUglyNumber(int n){ if (n 0) return false; // 负数、0 都不是 // 把 2 除干净 while (n % 2 0) n / 2; // 把 3 除干净 while (n % 3 0) n / 3; // 把 5 除干净 while (n % 5 0) n / 5; // 最后只剩 1就是丑数 return n 1; }丑数2--寻找第N个丑数暴力法public static int nthUglyNumber(int n) { //计数器 int count 0; int num 1; while (true) { //如果是丑数就加一 if (isUglyNumber(num)) { count; if (count n) return num; } num; } }三指针动态规划最优解public static int nthUglyNumber(int n){ int[] dpnew int[n]; dp[0]1; int p20,p30,p50; for (int i 1; i n; i) { int num2dp[p2]*2; int num3dp[p3]*3; int num5dp[p5]*5; //这里开始书写 //首先我们选择的一个丑数加入到自己的队列中 dp[i]Math.min(Math.min(num2,num3),num5); //加入到我们的队伍中就是为了把这个丑数的因子进行一个进化 if (num2dp[i]) p2; if (num3dp[i]) p3; if (num5dp[i]) p5; } return dp[n-1]; }