diff options
author | Jack Sangdahl <[email protected]> | 2024-11-07 18:58:21 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-07 18:58:21 -0700 |
commit | 6779cbd9ed0c98f31af5939304b5611a9efe5026 (patch) | |
tree | 0fdabb022eb85ea33f963f25d14e6f7077737601 | |
parent | 44d57e16ee87f213c1b65bfe9a72185056ab3e16 (diff) | |
download | leetcode-6779cbd9ed0c98f31af5939304b5611a9efe5026.tar.gz leetcode-6779cbd9ed0c98f31af5939304b5611a9efe5026.zip |
1824. minimum sideway jumps
-rw-r--r-- | minimum_sideways_jumps.c | 55 | ||||
-rw-r--r-- | minimum_sideways_jumps.py | 37 |
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])) |