LeetCode 55. 跳跃游戏
题目描述
✅ 55. 跳跃游戏
思路分析
这道题目要求我们判断是否能从数组的第一个位置跳跃到最后一个位置。我们可以通过贪心算法来解决这个问题。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func canJump(nums []int) bool {
var farthest int // 表示当前能够跳跃到的最远位置
for i := 0; i < len(nums); i++ {
if i > farthest {
// 如果当前索引已经超过了最远可达位置，返回 false
return false
}
farthest = max(farthest, i+nums[i]) // 更新最远可达位置
if farthest >= len(nums)-1 {
// 如果最远可达位置已经到达或超过了最后一个位置，返回 true
return true
}
}
return false
}
- 时间复杂度：O(n)，我们只需要遍历一次数组。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
动态规划：
dp[i]表示从起点是否可以到达位置i。
1
2
3
4
5
6
7
8
9
10
11
12
13
func canJump(nums []int) bool {
n := len(nums)
dp := make([]bool, n)
dp[0] = true
for i := 0; i < n; i++ {
if dp[i] {
for j := i + 1; j <= i+nums[i] && j < n; j++ {
dp[j] = true
}
}
}
return dp[n-1]
}
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！