Jump Game


跳转游戏, 当前下标的值代表最大能跳多远, 判断是否能跳到尾部

我的做法

思路:
从后往前判断, 每次判断最小路径

代码:

结果:

每次判断的是最小的路径, 所以效率上并不高
如果一个数组值连续, 那么会将所有元素都迭代一次

dalao的做法

核心是 left_most, 初始值是最大索引
emmm, 好奇怪, 循环的次数几乎是一样的, 我也只做了一次判断
为什么它的算法时间要比我少一倍? (难道是最开始的判断?, 或者多了一个width?)
dalao的要更直接得多, 判断当前格子可行走总数量是否大于最大的
他的算法更容易理解


PS: 这位dalao给出了几种解法, 这只是其中一种, 不过我觉得我想到了他貌似没想到的点
如果一个数组他每两个元素之间直接可以跳, 偏偏第一个元素值为0, 例如:
[0, 1, 2, 3, 4, 5, 6....]
他会所有遍历一次, 但只要第一个值为0, 那么一切迭代到最后都是白费的
不过这看情况, 大多数情况下不会, 那么这种判断就会成为拖累