leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0264.cpp (1001B)

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