1.丑数1
public 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[] dp=new int[n]; dp[0]=1; int p2=0,p3=0,p5=0; for (int i = 1; i < n; i++) { int num2=dp[p2]*2; int num3=dp[p3]*3; int num5=dp[p5]*5; //这里开始书写 //首先，我们选择的一个丑数，加入到自己的队列中 dp[i]=Math.min(Math.min(num2,num3),num5); //加入到我们的队伍中，就是为了把这个丑数的因子进行一个进化 if (num2==dp[i]) p2++; if (num3==dp[i]) p3++; if (num5==dp[i]) p5++; } return dp[n-1]; }
