leetcode

commit 55d62ce6e2cdf07e1fcb943120025a96e734d461
parent c15945ee7151880053e6b5921bc329d6025833b8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 20 Jun 2024 19:58:09 +0200

1 Random Problem

Diffstat:
A
Problems/1824.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/1824.cpp b/Problems/1824.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  public:
+    int minSideJumps(const vector<int> &obstacles) const {
+        static unsigned dp[500002][3];
+        const int n = size(obstacles);
+
+        memset(dp, 0xF0, sizeof(dp));
+        memset(dp[n - 1], 0x00, sizeof(dp[n]));
+        for (int i = n - 2; i >= 0; i--) {
+            for (int j = 0; j < 3; j++) {
+                if (obstacles[i + 1] == j + 1) continue;
+                if (obstacles[i] == j + 1) continue;
+                dp[i][j] = dp[i + 1][j];
+            }
+
+            dp[i][0] = min({dp[i][0], dp[i][1] + 1, dp[i][2] + 1});
+            dp[i][1] = min({dp[i][1], dp[i][0] + 1, dp[i][2] + 1});
+            dp[i][2] = min({dp[i][2], dp[i][0] + 1, dp[i][1] + 1});
+        }
+
+        return dp[0][1];
+    }
+};
diff --git a/README.md b/README.md
@@ -977,6 +977,7 @@ for solving problems.
 |  1817  |   Medium   | [Finding the Users Active Minutes](Problems/1817.cpp)                                              |
 |  1822  |    Easy    | [Sign of the Product of an Array](Problems/1822.cpp)                                               |
 |  1823  |   Medium   | [Find the Winner of the Circular Game](Problems/1823.cpp)                                          |
+|  1824  |   Medium   | [Minimum Sideway Jumps](Problems/1824.cpp)                                                         |
 |  1828  |   Medium   | [Queries on Number of Points Inside a Circle](Problems/1828.cpp)                                   |
 |  1829  |   Medium   | [Maximum XOR for Each Query](Problems/1829.cpp)                                                    |
 |  1833  |   Medium   | [Maximum Ice Cream Bars](Problems/1833.cpp)                                                        |