题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
- 输入：nums = [2,3,1,1,4]
- 输出：true
- 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
- 输入：nums = [3,2,1,0,4]
- 输出：false
- 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
- 1 <= nums.length <= 3 * 104
- 0 <= nums[i] <= 105
解法一：动态规划
规定：dp[i] 为使用完 nums 中区间为 [0...i] 的数字后能够跳跃到的下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func max(nums ...int) int {
ans := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > ans {
ans = nums[i]
}
}
return ans
}
func canJump(nums []int) bool {
n := len(nums)
dp := make([]int, n)
dp[0] = nums[0]
for i := 1; i < n; i++ {
if i <= dp[i-1] {
dp[i] = max(dp[i-1], i+nums[i])
} else {
return false
}
}
return true
}
|
优化上面代码，优化后的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func max(nums ...int) int {
ans := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > ans {
ans = nums[i]
}
}
return ans
}
func canJump(nums []int) bool {
n := len(nums)
maxDist := nums[0]
for i := 1; i < n; i++ {
if i <= maxDist {
maxDist = max(maxDist, i + nums[i])
} else {
return false
}
}
return true
}
|
