【leetcode刷題】T172-跳躍遊戲

• 2019 年 10 月 8 日
• 筆記

木又連續日更第10天（10/100）

貪心類型第1篇解題報告

leetcode第55題：跳躍遊戲

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

給定一個非負整數數組，你最初位於數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個位置。

示例 1:  輸入: [2,3,1,1,4]  輸出: true  解釋: 從位置 0 到 1 跳 1 步, 然後跳 3 步到達最後一個位置。    示例 2:  輸入: [3,2,1,0,4]  輸出: false  解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠不可能到達最後一個位置。  

【思路】

從一個點i能夠跳到最遠的地方為max_i = i+nums[i]，需要保證i < max_i。

最後返回max_i >= len(nums) – 1的布爾值即可。

【程式碼】

python版本

class Solution(object):      def canJump(self, nums):          """          :type nums: List[int]          :rtype: bool          """          max_i = 0          for i, n in enumerate(nums):              if i <= max_i:                  if i + nums[i] > max_i:                      max_i = i + nums[i]              else:                  return False          return max_i >= len(nums)-1  

C++版本

class Solution {  public:      bool canJump(vector<int>& nums) {          int tmp = 0;          for(int i=0; i<nums.size(); i++){              if(i > tmp)                  return false;              tmp = max(tmp, i+nums[i]);          }          return tmp >= nums.size()-1;      }  };