【leetcode刷题】T173-跳跃游戏 II

• 2019 年 10 月 4 日
• 筆記

【题目】

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:  输入: [2,3,1,1,4]  输出: 2  解释: 跳到最后一个位置的最小跳跃数是 2。       从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明: 假设你总是可以到达数组的最后一个位置。

【思路】

可以用动态规划来做，对于所有的j=i，dp[i] = min(dp[j] + 1)

怎么使用贪心算法呢？

使用变量max_i存储目前能够到达的最远位置，那么位置i能够到达最远位置为i+nums[i]，时刻更新max_i，并记录最小步数即可。

什么时候更新最小步数呢？

当所处位置i等于前一步能够到达最远的地方时。

就是说，对于[2, 3, 1, 1, 4]，首先设置max_i=0，end=0，count=0

i=0时，max_i = max(max_i, i + nums[i]) = 2

前一步（第0步）能够到达最远位置end为0，由于i == end，更新end为max_i，更新count=1

i=1时，max_i = max(max_i, i + nums[i]) = 4

i=2时，max_i=4，由于i == end，更新end为4，更新count=2

继续循环。

【代码】

python版本

class Solution(object):      def jump(self, nums):          """          :type nums: List[int]          :rtype: int          """          if len(nums) == 1:              return 0          count = 0          max_i = 0          end = 0          for i in range(len(nums)):              max_i = max(max_i, i + nums[i])              if i >= end:                  end = max_i                  count += 1              if end >= len(nums) - 1:                  return count

C++版本

class Solution {  public:      int jump(vector<int>& nums) {          if(nums.size() == 1)              return 0;          int count=0, max_i=0, end=0;          for(int i=0; i < nums.size(); i++){              max_i = max(max_i, i+nums[i]);              if(i >= end){                  count++;                  end = max_i;              }              if(end >= nums.size() - 1)                  return count;          }          return 0;      }  };