leetcode

commit efd0bf974830c5fa091956c3ba96ff9e4d4b65db
parent 110291debf45769a678f8d97592b0ea0ce1f7264
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 24 Feb 2023 13:25:03 +0100

Data Structure II: Day 21

Diffstat:
A
Problems/0451.cpp
 | 
11
+++++++++++
A
Problems/0973.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/0451.cpp b/Problems/0451.cpp
@@ -0,0 +1,11 @@
+class Solution {
+public:
+  string frequencySort(string s) {
+    array<int, 128> um = {0};
+    for (char c : s) um[c]++;
+    sort(s.begin(), s.end(), [&um](char a, char b) {
+      return um[a] > um[b] || (um[a] == um[b] && a < b);
+    });
+    return s;
+  }
+};
diff --git a/Problems/0973.cpp b/Problems/0973.cpp
@@ -0,0 +1,17 @@
+class Solution {
+  typedef pair<double, int> pdi;
+
+public:
+  vector<vector<int>> kClosest(vector<vector<int>> &points, int k) {
+    auto cmp = [](const pdi &a, const pdi &b) { return a.first < b.first; };
+    priority_queue<pdi, vector<pdi>, decltype(cmp)> pq(cmp);
+    for (int i = 0; i < points.size(); i++) {
+      pq.push({sqrt(pow(points[i][0], 2) + pow(points[i][1], 2)), i});
+      if (pq.size() > k) pq.pop();
+    }
+
+    vector<vector<int>> res(k);
+    while (k--) res[k] = points[pq.top().second], pq.pop();
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -238,6 +238,7 @@ for solving problems.
 |  0445  |   Medium   | [Add Two Numbers II](Problems/0445.cpp)                                                          |
 |  0448  |    Easy    | [Find All Numbers Disappeared in an Array](Problems/0448.cpp)                                    |
 |  0450  |   Medium   | [Delete Node in a BST](Problems/0450.cpp)                                                        |
+|  0451  |   Medium   | [Sort Characters By Frequency](Problems/0451.cpp)                                                |
 |  0452  |   Medium   | [Minimum Number of Arrows to Burst Balloons](Problems/0452.cpp)                                  |
 |  0460  |    Hard    | [LFU Cache](Problems/0460.cpp)                                                                   |
 |  0472  |    Hard    | [Concatenated Words](Problems/0472.cpp)                                                          |
@@ -336,6 +337,7 @@ for solving problems.
 |  0953  |    Easy    | [Verifying an Alien Dictionary](Problems/0953.cpp)                                               |
 |  0959  |   Medium   | [Regions Cut By Slashes](Problems/0959.cpp)                                                      |
 |  0965  |    Easy    | [Univalued Binary Tree](Problems/0965.cpp)                                                       |
+|  0973  |   Medium   | [K Closest Points to Origin](Problems/0973.cpp)                                                  |
 |  0974  |   Medium   | [Subarray Sums Divisible by K](Problems/0974.cpp)                                                |
 |  0977  |    Easy    | [Squares of a Sorted Array](Problems/0977.cpp)                                                   |
 |  0980  |    Hard    | [Unique Paths III](Problems/0980.cpp)                                                            |