leetcode

commit c800b121c4af0d519385d2ed538e63787469448b
parent 5684438eea23a066e6c3d856cfa1725a3c1588df
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  4 Feb 2023 13:17:07 +0100

LeetCode 75 I: Day 15 FINISH

Diffstat:
A
Problems/0692.cpp
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
A
Problems/1046.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 67 insertions(+), 0 deletions(-)
diff --git a/Problems/0692.cpp b/Problems/0692.cpp
@@ -0,0 +1,46 @@
+// sort: O(nlogn)
+class Solution {
+public:
+  vector<string> topKFrequent(const vector<string> &words, int k) {
+    unordered_map<string, int> um;
+    for (const auto &w : words) um[w]++;
+
+    vector<pair<int, string>> vec(um.size());
+    vector<string> res(k);
+
+    int count = 0;
+    for (const auto &[k, v] : um) vec[count++] = {-v, k};
+    sort(vec.begin(), vec.end());
+    for (int i = 0; i < k; i++) res[i] = vec[i].second;
+
+    return res;
+  }
+};
+
+// heap: O(nlogk)
+class Solution {
+  typedef pair<string, int> psi;
+  static constexpr const auto cmp = [](const psi &p1, const psi &p2) {
+    if (p1.second == p2.second) return p1.first < p2.first;
+    return p1.second > p2.second;
+  };
+
+public:
+  vector<string> topKFrequent(const vector<string> &words, int k) {
+    unordered_map<string, int> um;
+    for (const auto &w : words) um[w]++;
+
+    priority_queue<psi, vector<psi>, decltype(cmp)> pq(cmp);
+    vector<string> res(k);
+
+    for (auto it : um) {
+      pq.push(it);
+      if (pq.size() > k) pq.pop();
+    }
+
+    int count = k - 1;
+    while (!pq.empty()) res[count--] = pq.top().first, pq.pop();
+
+    return res;
+  }
+};
diff --git a/Problems/1046.cpp b/Problems/1046.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+  int lastStoneWeight(vector<int> &stones) {
+    int n = stones.size();
+    make_heap(stones.begin(), stones.end());
+    while (stones.size() > 1) {
+      int x, y;
+      pop_heap(stones.begin(), stones.end());
+      y = stones.back(), stones.pop_back();
+      pop_heap(stones.begin(), stones.end());
+      x = stones.back(), stones.pop_back();
+      if (x != y) {
+        stones.push_back(y - x);
+        push_heap(stones.begin(), stones.end());
+      }
+    }
+    return !stones.empty() ? stones.back() : 0;
+  }
+};
diff --git a/README.md b/README.md
@@ -229,6 +229,7 @@ for solving problems.
 |  0669  |   Medium   | [Trim a Binary Search Tree](Problems/0669.cpp)                                                   |
 |  0671  |    Easy    | [Second Minimum Node In a Binary Tree](Problems/0671.cpp)                                        |
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                        |
+|  0692  |   Medium   | [Top K Frequent Words](Problems/0692.cpp)                                                        |
 |  0695  |   Medium   | [Max Area of Island](Problems/0695.cpp)                                                          |
 |  0700  |    Easy    | [Search in a Binary Search Tree](Problems/0700.cpp)                                              |
 |  0701  |   Medium   | [Insert into a Binary Search Tree](Problems/0701.cpp)                                            |
@@ -290,6 +291,7 @@ for solving problems.
 |  1026  |   Medium   | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp)                                |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                      |
 |  1042  |   Medium   | [Flower Planting With No Adjacent](Problems/1042.cpp)                                            |
+|  1046  |    Easy    | [Last Stone Weight](Problems/1046.cpp)                                                           |
 |  1047  |    Easy    | [Remove All Adjacent Duplicates In String](Problems/1047.cpp)                                    |
 |  1051  |    Easy    | [Height Checker](Problems/1051.cpp)                                                              |
 |  1061  |   Medium   | [Lexicographically Smallest Equivalent String](Problems/1061.cpp)                                |