给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置,跳1步,然后跳3步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
贪心。
class Solution: def jump(self, nums: List[int]) -> int: end = mx = steps = 0 for i, num in enumerate(nums[:-1]): mx = max(mx, i + num) if i == end: end = mx steps += 1 return steps
class Solution { public int jump(int[] nums) { int end = 0; int mx = 0; int steps = 0; for (int i = 0; i < nums.length - 1; ++i) { mx = Math.max(mx, i + nums[i]); if (i == end) { end = mx; ++steps; } } return steps; } }
class Solution { public: int jump(vector<int>& nums) { int mx = 0, steps = 0, end = 0; for (int i = 0; i < nums.size() - 1; ++i) { mx = max(mx, i + nums[i]); if (i == end) { end = mx; ++steps; } } return steps; } };
func jump(nums []int) int { mx, steps, end := 0, 0, 0 for i := 0; i < len(nums)-1; i++ { mx = max(mx, i+nums[i]) if i == end { end = mx steps++ } } return steps } func max(a, b int) int { if a > b { return a } return b }
public class Solution { public int Jump(int[] nums) { int end = 0; int mx = 0; int steps = 0; for (int i = 0; i < nums.Length - 1; ++i) { mx = Math.Max(mx, i + nums[i]); if (i == end) { end = mx; ++steps; } } return steps; } }