LeetCode題解之跳躍游戲
前言
周五了，和大家玩個跳躍游戲
題目
給定一個非負整數數組 nums ，你最初位于數組的 第一個下標 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最后一個下標。
示例 1：輸入：nums = [2,3,1,1,4] 輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。
示例 2：輸入：nums = [3,2,1,0,4] 輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。
分析
簡單分析一下，由題目得出，要想到達最后一個下標，得滿足兩個條件：
- 1、假設每個位置都能跳到，那么我們只需要遍歷數組，看看有沒有位置能直接通過這個位置上的數字跳到結尾。
比如[2,3,2,1,4]，我們遍歷數字，看看哪個位置可以跳到最后，可以發現第三個位置的數字是2，所以可以通過第三個位置跳到最后的下標，數組成立。
- 2、上述假設成立的還有個條件就是 每個位置是否都能跳到。
比如[2,0,2,1,4]，按照上面的邏輯，第三個位置是可以跳到最后下標。但是，第三個位置是否能到達呢?如果第三個位置都到不了，那又何談最后的位置呢?在這個例子中，第一個位置為2，是可以跳到第三個位置的。
如果改成[1,0,2,1,4]，第三個位置就到不了了。
結合上述分析，我們可以得出以下解法：
- public boolean canJump(int[] nums) {
- //能到達的最大位置k
- int k =0;
- //遍歷數組
- for(int i=0;i<nums.length;i++){
- //如果達不到i位置，就直接返回false
- if(k<i) return false;
- k=Math.max(k,i+nums[i]);
- }
- return true;
- }
也可以在每次獲取k之后再判斷一次，如果滿足條件就直接返回，減少循環次數：
- public boolean canJump(int[] nums) {
- //能到達的最大位置k
- int k =0;
- //獲取數組長度
- int l = nums.length;
- //遍歷數組
- for(int i=0;i<l;i++){
- if(k<i) return false;
- k=Math.max(k,i+nums[i]);
- if (k >= l-1) {
- return true;
- }
- }
- return false;
- }
這種在到了某個位置，作出當前最好的選擇 的算法一般稱為貪心算法。
貪心算法的思路就是把問題分為若干個子問題，然后針對每個子問題進行局部求解，最終得到整個問題的解。
貪心算法主要有兩個特點：
- 總是作出在當前看來最好的選擇。
- 從局部的最優選擇到整體最優解。
所以“貪心”的意思大概就是目光短淺，只看到到眼前的最好，而不會從整體的角度思考。
雖然不能保證最后的解法是最優的，但是這種辦法確實是能夠解決問題的，將大問題化解成小問題，小問題好好解決。
那有什么時候會有更好的解呢?這就引出 動態規劃了。
動態規劃的思想同樣是解決子問題，但是每一步的選擇都會依賴于相關的子問題解，所以有時候的復雜問題選擇動態規劃能有更好的解法，因為他對于子問題間的相關性更強。
就等下次聊了，拜拜。
時間復雜度
O(n)
空間復雜度
O(1)
參考
https://blog.csdn.net/qq_42363032/article/details/103597453
https://leetcode-cn.com/problems/jump-game/submissions/
本文轉載自微信公眾號「碼上積木」，作者積木zz 。轉載本文請聯系碼上積木公眾號。
