KK's blog

每天积累多一些

0%

LeetCode 1654 Minimum Jumps to Reach Home

Posted on Edited on Disqus:

LeetCode



A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right). It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row. It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.


Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1


Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.


Constraints:

1 <= forbidden.length <= 1000 1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000 All the elements in forbidden are distinct.
* Position x is not forbidden.

题目大意：

求从0到x的最小步数，可以往前跳a步，往后跳b步，不能跳到负数，不能连续两次往前跳，不能跳到被禁止的位置。

算法思路：

类似于Jump game，不过此题要用真的BFS，用三个元素push如queue: (point, distance, is_backward), is_backward记录是否回退两次而剪枝，distance是结果。

注意事项：

  1. 用BFS模板，但此题到了某个位置可以有两个状态：向前跳和向后跳。所以visited不能只含位置，必须包含方向，(position, is_backward). if (neighbor, neighbor_is_backward) in visited也记得包含方向，否则LTE，因为Python不会检查是否tuple
  2. upper limit为max(x, max(forbidden)) + a + b，否则LTE，这个比较推导，可以这么理解max(x, max(forbidden))之后可以自由不受限制地走，必定存在一个点之后会重复且无意义，如a和b的最小倍数。举个例子找规律，a=2, b=1, x=10, 要走到11的话就要先到x+a+b再往回走

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
	forbidden_set = set(forbidden)
	limit = max(x, max(forbidden)) + a + b
	queue = collections.deque([(0, 0, False)])
	visited = set([(0, False)])  # remember two states
	while queue:
		node = queue.popleft()
		if node[0] == x:
			return node[1]
		for neighbor in [node[0] + a, node[0] - b]:
			if neighbor in forbidden_set or neighbor < 0 or neighbor > limit: # remember limit
				continue
			if neighbor == node[0] - b and node[2]: # no backward twice
				continue
			neighbor_is_backward = True if neighbor == node[0] - b else False
			if (neighbor, neighbor_is_backward) in visited: # remember not neighbor in visited - LTE
				continue
			queue.append((neighbor, node[1] + 1, neighbor_is_backward))
			visited.add((neighbor, neighbor_is_backward))
	return -1

算法分析：

时间复杂度为O(max(x, max(forbidden)) + a + b)，空间复杂度O(max(x, max(forbidden)) + a + b)

Free mock interview