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 laneand 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 obstacle in the 3 lanes at each point.
- For example, if
obstacles[2] == 1
, then there is an obstacle on lane 1 at point 2.
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
. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.
- For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.
Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2
at point 0.
Note: There will be no obstacles on points 0
and n
.
Example 1:
Input: obstacles = [0,1,2,3,0] Output: 2 Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows). Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).
Example 2:
Input: obstacles = [0,1,1,3,3,0] Output: 0 Explanation: There are no obstacles on lane 2. No side jumps are required.
Example 3:
Input: obstacles = [0,2,1,0,3,0] Output: 2 Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.
Constraints:
obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0
Solution: DP
Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: int minSideJumps(vector<int>& obstacles) { const int n = obstacles.size(); vector<vector<int>> dp(3, vector<int>(n, INT_MAX / 2)); dp[1][0] = 0; dp[0][0] = dp[2][0] = 1; for (int i = 1; i < n; ++i) { for (int k = 0; k < 3; ++k) if (obstacles[i] != k + 1) dp[k][i] = dp[k][i - 1]; for (int k = 0; k < 3; ++k) if (obstacles[i] != k + 1) dp[k][i] = min({dp[k][i], dp[(k + 1) % 3][i] + 1, dp[(k + 2) % 3][i] + 1}); } return min({dp[0].back(), dp[1].back(), dp[2].back()}); } }; |
C++/O(1) Space
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int minSideJumps(vector<int>& obstacles) { const int n = obstacles.size(); vector<int> dp{1, 0, 1}; for (int o : obstacles) { if (o) dp[o - 1] = 1e9; for (int k = 0; k < 3; ++k) { if (k == o - 1) continue; dp[k] = min({dp[k], dp[(k + 1) % 3] + 1, dp[(k + 2) % 3] + 1}); } } return *min_element(begin(dp), end(dp)); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment