大家好，我是曉星航。今天為大家帶來的是 跳躍游戲面試題 相關的講解！😀

題目簡介

題目解答

思路：這樣以來，我們依次遍歷數組中的每一個位置，并實時維護最遠可以到達的位置。對于當前遍歷到的位置 i，如果它在最遠可以到達的位置 的范圍內，那么我們就可以從起點通過若干次跳躍到達該位置，因此我們可以用 i+nums[i]更新 最遠可以到達的位置。

在遍歷的過程中，如果最遠可以到達的位置大于等于數組中的最后一個位置，那就說明最后一個位置可達，我們就可以直接返回 True 作為答案。反之，如果在遍歷結束后，最后一個位置仍然不可達，我們就返回 False 作為答案。

解法一：貪心算法＋動態規劃

代碼：

class Solution {public static boolean canJump(int[] nums) {if (nums == null) {return false;}//前n-1個元素能夠跳到的最遠距離int k = 0;for (int i = 0; i <= k; i++) {//第i個元素能夠跳到的最遠距離int temp = i + nums[i];//更新最遠距離k = Math.max(k, temp);//如果最遠距離已經大于或等于最后一個元素的下標,則說明能跳過去,退出. 減少循環if (k >= nums.length - 1) {return true;}}//最遠距離k不再改變,且沒有到末尾元素return false;}
}

代碼注釋很好的解釋了每一行代碼是干嘛的，看不懂的可以參考注釋。
這里引入一個話方便大家理解i和k是什么：k好比修路，只要前面一直有修好的路，i(人)就能一直往前走。

復雜度分析：

• 時間復雜度：O(n)，其中n為數組的大小。只需要訪問nums數組一遍，共n個位置。
• 空間復雜度：O(1)，不需要額外的空間開銷。

題目鏈接

55. 跳躍游戲
感謝各位讀者的閱讀，本文章有任何錯誤都可以在評論區發表你們的意見，我會對文章進行改正的。如果本文章對你有幫助請動一動你們敏捷的小手點一點贊，你的每一次鼓勵都是作者創作的動力哦！😘