aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-07 18:58:21 -0700
committerJack Sangdahl <[email protected]>2024-11-07 18:58:21 -0700
commit6779cbd9ed0c98f31af5939304b5611a9efe5026 (patch)
tree0fdabb022eb85ea33f963f25d14e6f7077737601
parent44d57e16ee87f213c1b65bfe9a72185056ab3e16 (diff)
downloadleetcode-6779cbd9ed0c98f31af5939304b5611a9efe5026.tar.gz
leetcode-6779cbd9ed0c98f31af5939304b5611a9efe5026.zip
1824. minimum sideway jumps
-rw-r--r--minimum_sideways_jumps.c55
-rw-r--r--minimum_sideways_jumps.py37
2 files changed, 92 insertions, 0 deletions
diff --git a/minimum_sideways_jumps.c b/minimum_sideways_jumps.c
new file mode 100644
index 0000000..6d7ebc7
--- /dev/null
+++ b/minimum_sideways_jumps.c
@@ -0,0 +1,55 @@
+// 1824. Minimum Sideway Jumps
+#include "leetcode.h"
+
+/*
+ * there is a 3 lane road of length 'n' that consists of 'n + 1' points labeled
+ * from 0 to 'n'. a frog starts at point 0 in the second lane and wants to jump
+ * to point 'n'. however there could be obstacles along the way. you are given
+ * an array 'obstacles' of length 'n + 1' where each 'obstacles[i]' (ranging
+ * from 0 to 3) describes an obstacle on the lane 'obstacles[i]' at point 'i'.
+ * if 'obstacles[i] == 0' there are no obstacles at point 'i'. there will be at
+ * most one obstacles in the 3 lanes at each point. the frog can only travel
+ * from point 'i' to point 'i + 1' on the same lane if there is not an obstacle
+ * on the lane at point 'i + 1'. return the minimum number of side jumps the
+ * frog needs to reach any lane at point 'n' starting from lane 2 at point 0.
+ */
+
+int minSideJumps(int *obstacles, int obstaclesSize) {
+ int cnt = 0, status = 2;
+ for (int i = 0; i < obstaclesSize - 1; i++) {
+ if (obstacles[i + 1] == 2 && (status & (1 << 1))) {
+ status -= 2;
+ if (!status) {
+ cnt++;
+ status = 5;
+ if (obstacles[i])
+ status -= (1 << (obstacles[i] - 1));
+ }
+ } else if (obstacles[i + 1] == 3 && (status & (1 << 2))) {
+ status -= 4;
+ if (!status) {
+ cnt++;
+ status = 3;
+ if (obstacles[i])
+ status -= (1 << (obstacles[i] - 1));
+ }
+ } else if (obstacles[i + 1] == 1 && (status & 1)) {
+ status--;
+ if (!status) {
+ cnt++;
+ status = 6;
+ if (obstacles[i])
+ status -= (1 << (obstacles[i] - 1));
+ }
+ }
+ }
+ return cnt;
+}
+
+int main() {
+ int o1[] = {0, 1, 2, 3, 0}, o2[] = {0, 1, 1, 3, 3, 0},
+ o3[] = {0, 2, 1, 0, 3, 0};
+ printf("%d\n", minSideJumps(o1, ARRAY_SIZE(o1))); // expect: 2
+ printf("%d\n", minSideJumps(o2, ARRAY_SIZE(o2))); // expect: 0
+ printf("%d\n", minSideJumps(o3, ARRAY_SIZE(o3))); // expect: 2
+}
diff --git a/minimum_sideways_jumps.py b/minimum_sideways_jumps.py
new file mode 100644
index 0000000..01e1cd6
--- /dev/null
+++ b/minimum_sideways_jumps.py
@@ -0,0 +1,37 @@
+# 1824. Minimum Sideway Jumps
+
+"""
+there is a 3 lane road of length 'n' that consists of 'n + 1' points labeled
+from 0 to 'n'. a frog starts at point 0 in the second lane and wants to jump
+to point 'n'. however there could be obstacles along the way. you are given
+an array 'obstacles' of length 'n + 1' where each 'obstacles[i]' (ranging
+from 0 to 3) describes an obstacle on the lane 'obstacles[i]' at point 'i'.
+if 'obstacles[i] == 0' there are no obstacles at point 'i'. there will be at
+most one obstacles in the 3 lanes at each point. the frog can only travel
+from point 'i' to point 'i + 1' on the same lane if there is not an obstacle
+on the lane at point 'i + 1'. return the minimum number of side jumps the
+frog needs to reach any lane at point 'n' starting from lane 2 at point 0.
+"""
+
+
+class Solution(object):
+ def minSideJumps(self, obstacles):
+ """
+ :type obstacles: List[int]
+ :rtype: int
+ """
+ dp = [1, 0, 1]
+ for i in obstacles:
+ if i:
+ dp[i - 1] = float("inf")
+ for j in range(3):
+ if i != j + 1:
+ dp[j] = min(dp[j], dp[(j + 1) % 3] + 1, dp[(j + 2) % 3] + 1)
+ return min(dp)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minSideJumps(obstacles=[0, 1, 2, 3, 0]))
+ print(obj.minSideJumps(obstacles=[0, 1, 1, 3, 3, 0]))
+ print(obj.minSideJumps(obstacles=[0, 2, 1, 0, 3, 0]))