leetcode

commit 41106b7d05838a8589efe24fed2e5447b5ca6b64
parent e117352fca8c59577017bf8b4a9a1baf0e8386f7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 23 Dec 2023 13:00:42 +0000

Daily Problem

Diffstat:
A
Problems/1496.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/1496.cpp b/Problems/1496.cpp
@@ -0,0 +1,21 @@
+struct Hash {
+    size_t operator()(const tuple<int, int> &t) const { return (get<0>(t) << 16) + get<1>(t); }
+};
+
+class Solution {
+  public:
+    bool isPathCrossing(const string &path) const {
+        static const pair<int, int> moves[128] = {
+            ['N'] = {-1, 0}, ['S'] = {1, 0}, ['E'] = {0, 1}, ['W'] = {0, -1}};
+        unordered_set<tuple<int, int>, Hash> us;
+        int x = 0, y = 0;
+        us.insert({0, 0});
+        for (const char c : path) {
+            x += moves[c].first;
+            y += moves[c].second;
+            if (us.count({x, y})) return true;
+            us.insert({x, y});
+        }
+        return false;
+    }
+};
diff --git a/README.md b/README.md
@@ -729,6 +729,7 @@ for solving problems.
 |  1491  |    Easy    | [Average Salary Excluding the Minimum and Maximum Salary](Problems/1491.cpp)                       |
 |  1492  |   Medium   | [The kth Factor of n](Problems/1492.cpp)                                                           |
 |  1493  |   Medium   | [Longest Subarray of 1's After Deleting One Element](Problems/1493.cpp)                            |
+|  1496  |    Easy    | [Path Crossing](Problems/1496.cpp)                                                                 |
 |  1498  |   Medium   | [Number of Subsequences That Satisfy the Given Sum Condition](Problems/1498.cpp)                   |
 |  1502  |    Easy    | [Can Make Arithmetic Progression From Sequence](Problems/1502.cpp)                                 |
 |  1503  |   Medium   | [Last Moment Before All Ants Fall Out of a Plank](Problems/1503.cpp)                               |