LeetCode
刷 LeetCode 防止老年痴呆。
小于 1 分钟
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
思路：还是贪心算法
对于每个位置，维护当前可以到达的最远位置(边界)，保存这个边界位置并继续遍历数组并更新每个位置可以到达的最远位置，如果遍历到了边界，则更新边界为当前可以到达的最远位置，并且步数+1。注意到只需要遍历到倒数第二个位置，因为如果最后一个位置可以到达，那么在倒数第二个位置的时候，边界一定是大于等于最后一个位置的。 这里就需要考虑末尾是否可以到达这个问题了，虽然题目说了假设总可以到达最后一个位置，但是多考虑一点肯定没坏处。代码中注释的很清楚了，如果遍历到某个边界位置，并且边界位置就是更新后的最远可到达位置，那么最远只能到达当前位置。
大约 2 分钟
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。 示例1： 输入**: [2,3,1,1,4] 输出: true 解释: 位置0 -> 位置1 -> 末尾 示例2： 输入: [3,2,1,0,4] 输出: false 解释: 最远到达位置3，之后再无法向后跳
思路一：贪心法
贪心算法的思路跟简单，从前向后遍历每个位置，若当前位置能达到，则更新可以到达的最远的位置，最后若能到达最后一个位置返回true。
大约 2 分钟