# 0055. 跳躍游戲 ## 題目地址(55. 跳躍游戲) <https://leetcode-cn.com/problems/jump-game/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非負整數數組，你最初位于數組的第一個位置。 數組中的每個元素代表你在該位置可以跳躍的最大長度。 判斷你是否能夠到達最后一個位置。 示例 1: 輸入: [2,3,1,1,4] 輸出: true 解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置。 示例 2: 輸入: [3,2,1,0,4] 輸出: false 解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠不可能到達最后一個位置。 ``` ``` ## 前置知識 - 貪心 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目是一道典型的`貪心`類型題目。思路就是用一個變量記錄當前能夠到達的最大的索引，并逐個遍歷數組中的元素去更新這個索引，遍歷完成判斷這個索引是否大于`數組長度 - 1`即可。 ## 關鍵點解析 - 記錄和更新當前位置能夠到達的最大的索引 ## 代碼 - 語言支持: Javascript,C++,Java,Python3 Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {boolean} */</span> <span class="hljs-keyword">var</span> canJump = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> max = <span class="hljs-params">0</span>; <span class="hljs-title">// 能夠走到的數組下標</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">if</span> (max < i) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-title">// 當前這一步都走不到，后面更走不到了</span> max = <span class="hljs-params">Math</span>.max(nums[i] + i, max); } <span class="hljs-keyword">return</span> max >= nums.length - <span class="hljs-params">1</span>; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">canJump</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums)</span> </span>{ <span class="hljs-keyword">int</span> n=nums.size(); <span class="hljs-keyword">int</span> k=<span class="hljs-params">0</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-params">0</span>;i<n;i++) { <span class="hljs-keyword">if</span>(i>k){ <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-title">// 能跳到最后一個位置</span> <span class="hljs-keyword">if</span>(k>=n<span class="hljs-params">-1</span>){ <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } <span class="hljs-title">// 從當前位置能跳的最遠的位置</span> k = max(k, i+nums[i]); } <span class="hljs-keyword">return</span> k >= n<span class="hljs-params">-1</span>; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">canJump</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">int</span> n=nums.length; <span class="hljs-keyword">int</span> k=<span class="hljs-params">0</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-params">0</span>;i<n;i++) { <span class="hljs-keyword">if</span>(i>k){ <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; } <span class="hljs-title">// 能跳到最后一個位置</span> <span class="hljs-keyword">if</span>(k>=n-<span class="hljs-params">1</span>){ <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } <span class="hljs-title">// 從當前位置能跳的最遠的位置</span> k = Math.max(k, i+nums[i]); } <span class="hljs-keyword">return</span> k >= n-<span class="hljs-params">1</span>; } } ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canJump</span><span class="hljs-params">(self, nums: List[int])</span> -> bool:</span> <span class="hljs-string">"""思路同上"""</span> _max = <span class="hljs-params">0</span> _len = len(nums) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(_len<span class="hljs-params">-1</span>): <span class="hljs-keyword">if</span> _max < i: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> _max = max(_max, nums[i] + i) <span class="hljs-title"># 下面這個判斷可有可無，但提交的時候數據會好看點</span> <span class="hljs-keyword">if</span> _max >= _len - <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">return</span> _max >= _len - <span class="hljs-params">1</span> ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。