丑數

Solution

核心思路：

注意的幾個點：
1.優先隊列改變排序：

priority_queue<int,vector<int>,greater<int>> q;

2.用來判斷是否訪問過，可以用unordered_set
注意set的插入用的是insert而不是push

unordered_set<long long> vis;

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>//使用優先隊列priority_queue導入queue就行了
#include<unordered_map>
#include<unordered_set>
using namespace std;//優先隊列寫法
int nthUglyNumber1(int n) {priority_queue<long long,vector<long long>,greater<long long>> q;//unordered_map<long long, long long> vis;unordered_set<long long> vis;q.push(1);long long x;for (int i = 1; i <= n; ++i) {x = q.top();q.pop();long long x2 = x * 2;long long x3 = x * 3;long long x5 = x * 5;if (!vis.count(x2)) { q.push(x2); vis.insert(x2); }if (!vis.count(x3)) { q.push(x3); vis.insert(x3); }if (!vis.count(x5)) { q.push(x5); vis.insert(x5); }}return x;
}//動態規劃+三指針寫法
//題目的本質目的，是從前面得到的數中，每個數乘2，3，5，然后求從小到大的第n個數
//由于需要從小到大，可以使用三個指針依次指向當前乘以2，3，5的數，選取其中最小的為丑數，并將指針向后移動一個
int nthUglyNumber2(int n) {int p2 = 1, p3 = 1, p5 = 1;vector<long long> dp(n + 1, 1);for (int i = 2; i <= n; ++i) {long long x2 = dp[p2] * 2;long long x3 = dp[p3] * 3;long long x5 = dp[p5] * 5;long long ugly = min(min(x2, x3), x5);if (ugly == x2) p2++;if (ugly == x3) p3++;if (ugly == x5) p5++;dp[i] = ugly;}return dp[n];
}
int main() {return 0;
}