leetcode

commit 5f566a67e1294713dec897cecba63e54503c07e6
parent 2ce3e7ab03cc1275ed9be4055a894e25382a542a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  5 Feb 2023 12:55:36 +0100

Data Structure II: Day 2

Diffstat:
A
Problems/0075.cpp
 | 
10
++++++++++
A
Problems/0706.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/0075.cpp b/Problems/0075.cpp
@@ -0,0 +1,10 @@
+class Solution {
+public:
+  void sortColors(vector<int> &nums) {
+    array<int, 3> arr;
+    for (int n : nums) arr[n]++;
+    int count = 0;
+    for (int i = 0; i < 3; i++)
+      while (arr[i]--) nums[count++] = i;
+  }
+};
diff --git a/Problems/0706.cpp b/Problems/0706.cpp
@@ -0,0 +1,32 @@
+class MyHashMap {
+  const int mod = 9973;
+
+  vector<vector<pair<int, int>>> hm;
+  int hash(int key) { return key % mod; }
+
+  int &find(int key) {
+    static int err = -1;
+    for (auto &[k, v] : hm[hash(key)])
+      if (k == key) return v;
+    return err;
+  }
+
+public:
+  MyHashMap() : hm(mod) {}
+  void put(int key, int value) {
+    int &loc = find(key);
+    if (loc == -1)
+      hm[hash(key)].push_back({key, value});
+    else
+      loc = value;
+  }
+  int get(int key) { return find(key); }
+  void remove(int key) {
+    vector<pair<int, int>> &row = hm[hash(key)];
+    for (int i = 0; i < row.size(); i++)
+      if (row[i].first == key) {
+        row.erase(row.begin() + i);
+        break;
+      }
+  }
+};
diff --git a/README.md b/README.md
@@ -64,6 +64,7 @@ for solving problems.
 |  0067  |    Easy    | [Add Binary](Problems/0067.cpp)                                                                  |
 |  0070  |    Easy    | [Climbing Stairs](Problems/0070.cpp)                                                             |
 |  0074  |   Medium   | [Search a 2D Matrix](Problems/0074.cpp)                                                          |
+|  0075  |   Medium   | [Sort Colors](Problems/0075.cpp)                                                                 |
 |  0077  |   Medium   | [Combinations](Problems/0077.cpp)                                                                |
 |  0083  |    Easy    | [Remove Duplicates from Sorted List](Problems/0083.cpp)                                          |
 |  0084  |    Hard    | [Largest Rectangle in Histogram](Problems/0084.cpp)                                              |
@@ -238,6 +239,7 @@ for solving problems.
 |  0700  |    Easy    | [Search in a Binary Search Tree](Problems/0700.cpp)                                              |
 |  0701  |   Medium   | [Insert into a Binary Search Tree](Problems/0701.cpp)                                            |
 |  0704  |    Easy    | [Binary Search](Problems/0704.cpp)                                                               |
+|  0706  |    Easy    | [Design HashMap](Problems/0706.cpp)                                                              |
 |  0707  |   Medium   | [Design Linked List](Problems/0707.cpp)                                                          |
 |  0714  |   Medium   | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp)                        |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                            |