leetcode

commit 90db16afd264cf02d841d815f66aceaf85062b22
parent 0024d5569ebe626647ca76e2abcfbca6518e3284
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 20 Oct 2023 17:33:08 +0000

2 Random Problems

Diffstat:
A
Problems/0820.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
Problems/1333.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/Problems/0820.cpp b/Problems/0820.cpp
@@ -0,0 +1,43 @@
+class Trie {
+    struct Node {
+        Node(){};
+        Node *children[27] = {nullptr};
+        bool &terminate = reinterpret_cast<bool &>(children[0]);
+    };
+
+    Node *trie = new Node();
+
+    int length_rec(const Node *node, int len = 0) const {
+        int res = 1, had = 0;
+        for (int i = 1; i <= 26; i++) {
+            if (!node->children[i]) continue;
+            if (had) res += len + 1;
+            res += length_rec(node->children[i], len + 1);
+            had = true;
+        }
+        return res;
+    }
+
+  public:
+    void insert(const string &s) {
+        Node *crnt = trie;
+        for (int i = s.size() - 1; i >= 0; i--) {
+            const int idx = s[i] & 0x1F;
+            if (!crnt->children[idx]) crnt->children[idx] = new Node();
+            crnt = crnt->children[idx];
+        }
+        crnt->terminate = true;
+    }
+
+    int length(void) const { return length_rec(trie); }
+};
+
+class Solution {
+  public:
+    int minimumLengthEncoding(const vector<string> &words) {
+        Trie trie;
+        for (const string &word : words)
+            trie.insert(word);
+        return trie.length();
+    }
+};
diff --git a/Problems/1333.cpp b/Problems/1333.cpp
@@ -0,0 +1,19 @@
+class Solution {
+  public:
+    vector<int> filterRestaurants(const vector<vector<int>> &restaurants, int veganFriendly, int maxPrice,
+                                  int maxDistance) const {
+        vector<int> res;
+        for (int i = 0; i < restaurants.size(); i++) {
+            if (restaurants[i][3] > maxPrice || restaurants[i][4] > maxDistance) continue;
+            if (veganFriendly && !restaurants[i][2]) continue;
+            res.push_back(i);
+        }
+        sort(begin(res), end(res), [&](int a, int b) {
+            return restaurants[a][1] != restaurants[b][1] ? restaurants[a][1] > restaurants[b][1]
+                                                          : restaurants[a][0] > restaurants[b][0];
+        });
+        for (int i = 0; i < res.size(); i++)
+            res[i] = restaurants[res[i]][0];
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -409,6 +409,7 @@ for solving problems.
 |  0811  |   Medium   | [Subdomain Visit Count](Problems/0811.cpp)                                                         |
 |  0814  |   Medium   | [Binary Tree Pruning](Problems/0814.cpp)                                                           |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                    |
+|  0820  |   Medium   | [Short Encoding of Words](Problems/0820.cpp)                                                       |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                                 |
 |  0835  |   Medium   | [Image Overlap](Problems/0835.cpp)                                                                 |
 |  0837  |   Medium   | [New 21 Game](Problems/0837.cpp)                                                                   |
@@ -573,6 +574,7 @@ for solving problems.
 |  1325  |   Medium   | [Delete Leaves With a Given Value](Problems/1325.cpp)                                              |
 |  1326  |    Hard    | [Minimum Number of Taps to Open to Water a Garden](Problems/1326.cpp)                              |
 |  1329  |   Medium   | [Sort the Matrix Diagonally](Problems/1329.cpp)                                                    |
+|  1333  |   Medium   | [Filter Restaurants by Vegan-Friendly, Price and Distance](Problems/1333.cpp)                      |
 |  1334  |   Medium   | [Find the City With the Smallest Number of Neighbors at a Threshold Distance](Problems/1334.cpp)   |
 |  1337  |    Easy    | [The K Weakest Rows in a Matrix](Problems/1337.cpp)                                                |
 |  1338  |   Medium   | [Reduce Array Size to The Half](Problems/1338.cpp)                                                 |