0311-0320

311. Sparse Matrix Multiplication $\star\star$

312. Burst Balloons $\star\star\star$

313. Super Ugly Number $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int nthSuperUglyNumber(int n, vector<int>& primes) {
    const int k = primes.size();

    vector<int> nums{1};
    vector<int> indices(k);

    while (nums.size() < n) {
      vector<int> nexts(k);
      for (int i = 0; i < k; ++i) nexts[i] = nums[indices[i]] * primes[i];
      int next = accumulate(nexts.begin(), nexts.end(), INT_MAX,
                            [](int a, int b) { return min(a, b); });

      for (int i = 0; i < k; ++i)
        if (next == nexts[i]) ++indices[i];

      nums.push_back(next);
    }

    return nums.back();
  }
};

314. Binary Tree Vertical Order Traversal $\star\star$

315. Count of Smaller Numbers After Self $\star\star\star$

316. Remove Duplicate Letters $\star\star\star$

317. Shortest Distance from All Buildings $\star\star\star$

318. Maximum Product of Word Lengths $\star\star$

319. Bulb Switcher $\star\star$

1
2
3
4
class Solution {
 public:
  int bulbSwitch(int n) { return sqrt(n); }
};

320. Generalized Abbreviation $\star\star$