题目
https://leetcode-cn.com/problems/chou-shu-lcof
解法
整体思路; 写好解题步骤，再详细内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public class SO49_nthUglyNumber {
public static void main(String[] args) {
SO49_nthUglyNumber so49_nthUglyNumber = new SO49_nthUglyNumber();
System.out.println(so49_nthUglyNumber.nthUglyNumber(11));
}
public int nthUglyNumber(int n){
if (n <= 0) return 0;
int[] uglyNumbers = new int[n];
uglyNumbers[0] = 1;
int a2 = 0, b3=0, c5=0;
for (int i=1; i<n; i++) {
uglyNumbers[i] = Math.min(Math.min(uglyNumbers[a2]*2, uglyNumbers[b3]*3), uglyNumbers[c5]*5);
while (uglyNumbers[a2]*2<=uglyNumbers[i]) {
a2++;
}
while (uglyNumbers[b3]*3<=uglyNumbers[i]) {
b3++;
}
while (uglyNumbers[c5]*5<=uglyNumbers[i]) {
c5++;
}
}
return uglyNumbers[n-1];
}
}
|
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int nthUglyNumber(int n){
if (n<=0) return 0;
int[] dp = new int[n];
dp[0] = 1;
int a = 0, b = 0, c=0;
for (int i=1; i<n; i++) {
int n2= dp[a] * 2;
int n3 = dp[b] * 3;
int n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if (n2 == dp[i]) a++;
if (n3 == dp[i]) b++;
if (n5 == dp[i]) c++;
}
return dp[n-1];
}
|
