leetcode

题意：

丑数是素因子只包含2 3 5的数。1     2     3   4    5   6     8

返回第n个丑数

分析：

第一想法动态规划，找dp[ i ]之前的值乘2  3   5，找这些值里面大于dp[i-1]但是由最小的。

测试用例前面的全能过，但是到6000的时候出错。

public class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n+1]; for(int i=1; i<=n; i++){ dp[i] = Integer.MAX_VALUE; } for(int i=1; i<=n; i++){ if(i<=5) dp[i] = i; else{ for(int j=1; j<i; j++){ if(dp[j] * 5 > dp[i-1]) dp[i] = Math.min(dp[i], dp[j] * 5); if(dp[j] * 3 > dp[i-1]) dp[i] = Math.min(dp[i], dp[j] * 3); if(dp[j] * 2 > dp[i-1]) dp[i] = Math.min(dp[i], dp[j] * 2); } } } return dp[n]; } } 多路归并的方法：

ugly =  2 *dp[i ]  或  3*dp[ j ] 或  5*dp[ k ]

谁小取谁，然后，角标加1

其实就是说，每一个dp * 2 3 5我们都是要取的，先取小的。

                   2           3               5

dp[ 0 ]      

dp[ 1 ]

dp[ 2 ]

dp[ 3 ]

dp[ 4 ]

dp[ 5 ]

dp[ 6 ]

......

代码：

public class Solution { public int nthUglyNumber(int n) { if(n<=0) return 0; int a=0,b=0,c=0; int[] dp = new int[n]; dp[0] = 1; for(int i=1; i<n; i++) { int dp[i] = Math.min(dp[a]*2,Math.min(dp[b]*3,dp[c]*5)); if(dp[a]*2 == dp[i]) a++; if(dp[b]*3 == dp[i]) b++; if(dp[c]*5 == dp[i]) c++; } return dp[n-1]; } }