我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
看到这个题直接想递归
后来试图加剪枝处理，嘿更慢了
果然 timeout
存一下我的坑的，正确的摆在下面↓：
class Solution { public: bool uglyNumber(int n){ if(n == 1 || n == 2 || n == 3 || n == 5) return true; if(n % 2 == 0) { return uglyNumber(n/2); } if(n % 3 == 0) { return uglyNumber(n/3); } if(n % 5 == 0) { return uglyNumber(n/5); } return false; } int nthUglyNumber(int n) { int i = 0; while(n--) { i = i+1; for(;uglyNumber(i) != true;) { // printf("%d",i); i++; } } return i; } };
如果一个数是“丑数”，则它乘以2、3、5中的任意数都是"丑数"。换句话说，“丑数”从小到大来看，较大的“丑数”来自于较小的“丑数”乘以2、3、5。
把乘以2、乘以3、乘以5看作三种转移方式，则从1开始，“丑数”能够向后转移。
class Solution { public: int nthUglyNumber(int n) { vector<int> dp(n, 0); dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; i++) { dp[i] = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5); if (dp[i] == dp[p2] * 2) p2++; if (dp[i] == dp[p3] * 3) p3++; if (dp[i] == dp[p5] * 5) p5++; } return dp[n - 1]; } };
绝！
class Solution { public: int nthUglyNumber(int n) { long long two_qua[100]; long long three_qua[100]; long long five_qua[100]; two_qua[0] = three_qua[0] = five_qua[0] = 1; for (int i = 1; i <= log(INT_MAX) / log(2); ++i) two_qua[i] = two_qua[i - 1] * 2; for (int i = 1; i <= log(INT_MAX) / log(3); ++i) three_qua[i] = three_qua[i - 1] * 3; for (int i = 1; i <= log(INT_MAX) / log(5); ++i) five_qua[i] = five_qua[i - 1] * 5; vector<int> ans; for (int i = 0; i <= log(INT_MAX) / log(2); ++i) { for (int j = 0; j <= log(INT_MAX) / log(3); ++j) { for (int k = 0; k <= log(INT_MAX) / log(5); ++k) { if (log10(two_qua[i]) + log10(three_qua[j]) + log10(five_qua[k]) < log10(INT_MAX)) ans.push_back(two_qua[i] * three_qua[j] * five_qua[k]); } } } sort(ans.begin(), ans.end()); return ans[n - 1]; } };
