leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0264.cpp (1001B)

0 // Brute force solution 1 class Solution { 2 public: 3 int nthUglyNumber(int n) { 4 priority_queue<long long, vector<long long>, greater<long long>> pq; 5 unordered_set<long long> us; 6 int count; 7 8 pq.push(1); 9 count = 1; 10 while (!pq.empty() && count < n) { 11 long long n = pq.top(); 12 pq.pop(); 13 for (int i : {2, 3, 5}) { 14 if (us.count(n * i)) continue; 15 pq.push(n * i); 16 us.insert(n * i); 17 } 18 count++; 19 } 20 21 return (int)pq.top(); 22 } 23 }; 24 25 // DP solution 26 class Solution { 27 public: 28 int nthUglyNumber(int n) { 29 vector<int> k(n); 30 k[0] = 1; 31 int t2 = 0, t3 = 0, t5 = 0; 32 for (int i = 1; i < n; i++) { 33 k[i] = min(k[t2] * 2, min(k[t3] * 3, k[t5] * 5)); 34 t2 += k[i] == k[t2] * 2; 35 t3 += k[i] == k[t3] * 3; 36 t5 += k[i] == k[t5] * 5; 37 } 38 return k.back(); 39 } 40 };