mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 08:27:30 +08:00
67 lines
2.0 KiB
Markdown
67 lines
2.0 KiB
Markdown
# [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)
|
||
|
||
|
||
## 题目
|
||
|
||
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 <= 1000`
|
||
- `0 <= nums[i] <= 10^5`
|
||
|
||
## 题目大意
|
||
|
||
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
|
||
|
||
## 解题思路
|
||
|
||
- 要求找到最少跳跃次数，顺理成章的会想到用贪心算法解题。扫描步数数组，维护当前能够到达最大下标的位置，记为能到达的最远边界，如果扫描过程中到达了最远边界，更新边界并将跳跃次数 + 1。
|
||
- 扫描数组的时候，其实不需要扫描最后一个元素，因为在跳到最后一个元素之前，能到达的最远边界一定大于等于最后一个元素的位置，不然就跳不到最后一个元素，到达不了终点了；如果遍历到最后一个元素，说明边界正好为最后一个位置，最终跳跃次数直接 + 1 即可，也不需要访问最后一个元素。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
func jump(nums []int) int {
|
||
if len(nums) == 1 {
|
||
return 0
|
||
}
|
||
needChoose, canReach, step := 0, 0, 0
|
||
for i, x := range nums {
|
||
if i+x > canReach {
|
||
canReach = i + x
|
||
if canReach >= len(nums)-1 {
|
||
return step + 1
|
||
}
|
||
}
|
||
if i == needChoose {
|
||
needChoose = canReach
|
||
step++
|
||
}
|
||
}
|
||
return step
|
||
}
|
||
``` |