LeetCode 55: 跳跃游戏

  • A+
所属分类:算法与数据结构

题目描述

https://leetcode-cn.com/problems/jump-game/

LeetCode 55: 跳跃游戏

解决思路

1. 溯回法

最直观最容易想到的解法

很不幸,算法复杂度太高,超时。

LeetCode 55: 跳跃游戏

2. 溯回+记录

经过的位置不再经过,加一个记录表 记录经过的位置

能通过,但算法复杂度也很高

LeetCode 55: 跳跃游戏

3. 自底向上

从后往前进行推理,并且去掉递归的部分,自底向上的方法有更好的时间效率因为我们不再需要栈空间,可以节省很多缓存开销。更重要的事,这可以让之后更有优化的空间。设能经过最终点的位置为 good position,判断在 此位置 到 furthestJump范围内有无good position,有的话,说明此位置也为good position。最终判断位置 0 是否为good position。

LeetCode 55: 跳跃游戏

4. 贪心

从解法3可以看出,从后往前,如果某位置在furthestJump范围之内能经过Good position,那么此位置就为good position, 那么只需要计算一下此位置+furthestJump的超过最左边的Good position就好,不需要像解法3一样,一个一个查看了。

LeetCode 55: 跳跃游戏

总结

LeetCode 55: 跳跃游戏

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: