题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 字节跳动
- 微软（Microsoft）
- 谷歌（Google）
- 华为
AC 代码
- Java
// 枚举暴力（超时） class Solution { public int nthUglyNumber(int n) { int num = 1, res = -1; for (int i = 0; i < n;) { if (isUglyNum(num)) { res = num; i++; } num++; } return res; } private boolean isUglyNum(int num) { while (num % 2 == 0) { num /= 2; } while (num % 3 == 0) { num /= 3; } while (num % 5 == 0) { num /= 5; } return num == 1; } } // AC class Solution { public int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int[] dp = new int[n]; dp[0] = 1; for(int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = Math.min(Math.min(n2, n3), n5); if(dp[i] == n2) a++; if(dp[i] == n3) b++; if(dp[i] == n5) c++; } return dp[n - 1]; } }
- C++
class Solution { public: int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int dp[n]; dp[0] = 1; for(int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = min(min(n2, n3), n5); if(dp[i] == n2) a++; if(dp[i] == n3) b++; if(dp[i] == n5) c++; } return dp[n - 1]; } };
