LeetCode 045 Jump Game II

LeetCode

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 10<sup>4</sup> 0 <= nums[i] <= 1000

题目大意：

N/A

解题思路：

BFS，但不需要用queue

解题步骤：

N/A

注意事项：

1. end, next_end分别表示该层和下一层的边界，end从0开始，表示第0个数是第一层，遍历每个数，从0开始。
2. 这个边界是inclusive的，所以当i==end时候，不应该res加1，是下一轮循环才是下一层的开始。有两种实现，我的实现是第一种，标准答案是遍历到最后一个数的前一个，因为最后一个数已经是目标，所以不需要计算next_end，更不需要层数+1。

Python代码：

def jump2(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	update_end = False
	for i in range(len(nums)):
		if update_end:
			res += 1
			update_end = False
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			update_end = True
	return res

Python代码：

def jump(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	for i in range(len(nums) - 1):
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			res += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)