263. Ugly Number的子母题
题目要求输出从1开始数，第n个ugly number是什么并且输出。
一开始想着1遍历到n直接判断，超时了。
class Solution { public: bool isUgly(int num) { while (num % 5 == 0 && num > 4) num /= 5; while (num % 3 == 0 && num > 2) num /= 3; while (num % 2 == 0 && num > 1) num /= 2; return num == 1; } int nthUglyNumber(int n) { int res = 1; vector<int> sta; sta.push_back(res); while (sta.size() <= n) { ++res; if (isUgly(res)) sta.push_back(res); else { while (!isUgly(res)) { ++res; } sta.push_back(res); } } for (auto a : sta) { cout << a; } return sta[n]; } };
超时以后想通过数组保存ugly数字，然后对其排序，直接输出第n个ugly数字。
这里有点投机取巧的意思。利用static去保存，这样在不同数据测试中，只需要第一次计算保存数据，后面只需要执行返回static里面的值就好了，所以评测结果非常快。
Runtime: 4 ms, faster than 97.70% of C++ online submissions for Ugly Number II.
class Solution { public: int nthUglyNumber(int n) { static vector<int> uglyNums; long long a, b, c, maxN = INT_MAX; if (uglyNums.empty()) { for (a = 1; a < maxN; a *= 2) for (b = a; b < maxN; b *= 3) for (c = b; c < maxN; c *= 5) uglyNums.push_back(c); sort(begin(uglyNums), end(uglyNums)); } return uglyNums[n - 1]; } };
最优解里看到的，也是讨论区里面用的最多的一种方法，0ms。
class Solution { public: int nthUglyNumber(int n) { static vector<int> ugly {1}; static int last(1); static int c2=2, c3=3, c5=5; static int i2=0, i3=0, i5=0; while (ugly.size() < n) { while (c2 <= last) c2 = 2 * ugly[++i2]; while (c3 <= last) c3 = 3 * ugly[++i3]; while (c5 <= last) c5 = 5 * ugly[++i5]; ugly.push_back(last = min(c2, min(c3, c5))); } return ugly[n-1]; } };
转载于:https://www.cnblogs.com/ruoh3kou/p/10007880.html
相关资源：数据结构—成绩单生成器