[Leetcode] Jump Game 跳躍游戲

venmos 發布于2019-08-14 12:24 / 1820人閱讀

摘要：代碼記錄下當前區域的上界，以便待會更新下一個區域的上界更新下一個區域的上界更新下一個區域的下界后續如果要求返回最短跳躍路徑，如何實現可以使用，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。

Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/...

Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example: A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

貪心法 復雜度

時間 O(N) 空間 O(1)

思路

如果只是判斷能否跳到終點，我們只要在遍歷數組的過程中，更新每個點能跳到最遠的范圍就行了，如果最后這個范圍大于等于終點，就是可以跳到。

代碼

public class Solution {
    public boolean canJump(int[] nums) {
        int max = 0, i = 0;
        for(i = 0; i <= max && i < nums.length; i++){
            max = Math.max(max, nums[i] + i);
        }
        return i == nums.length;
    }
}

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

如果要計算最短的步數，就不能貪心每次都找最遠距離了，因為有可能一開始跳的遠的路徑，后面反而更慢。所以我們要探索所有的可能性，這里用快慢指針分出一塊當前結點能跳的一塊區域，然后再對這塊區域遍歷，找出這塊區域能跳到的下一塊區域的上下邊界，每塊區域都對應一步，直到上界超過終點時為之。

代碼

public class Solution {
    public int jump(int[] nums) {
        int high = 0, low = 0, preHigh = 0, step = 0;
        while(high < nums.length - 1){
            step++;
            //記錄下當前區域的上界，以便待會更新下一個區域的上界
            preHigh = high;
            for(int i = low; i <= preHigh; i++){
                //更新下一個區域的上界
                high = Math.max(high, i + nums[i]);
            }
            //更新下一個區域的下界
            low = preHigh + 1;
        }
        return step;
    }
}

后續 Follow Up

Q：如果要求返回最短跳躍路徑，如何實現？
A：可以使用DFS，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64453.html

Chrome 小恐龍游戲源碼探究八 -- 奔跑的小恐龍

摘要：例如，將函數修改為小恐龍眨眼這樣小恐龍會不停的眨眼睛。小恐龍的開場動畫下面來實現小恐龍對鍵盤按鍵的響應。接下來還需要更新動畫幀才能實現小恐龍的奔跑動畫。文章首發于我的 GitHub 博客前言上一篇文章：《Chrome 小恐龍游戲源碼探究七 -- 晝夜模式交替》實現了游戲晝夜模式的交替，這一篇文章中，將實現：1、小恐龍的繪制 2、鍵盤對小恐龍的控制 3、頁面失焦后，重新聚焦會重置...

paulquei 2019-08-23 17:09 評論0 收藏0
揭密微信跳一跳小游戲那些外掛

摘要：所以，我們這個小游戲發布以后，我們就開始花了很多很多時間來打擊外掛。二距離判斷像素點判斷該方法采用自目前最火的跳一跳小游戲輔助程序。作者：Hahn，騰訊高級UI工程師商業轉載請聯系騰訊WeTest獲得授權，非商業轉載請注明出處。原文鏈接：http://wetest.qq.com/lab/view/364.html WeTest 導讀張小龍：這個游戲發布以后，其實它的效果有點超...

lyning 2019-06-21 16:40 評論0 收藏0
leetcode45. Jump Game II

摘要：轉換為廣度優先算法即為我們只需要找到每一步的開始節點和結束下標，找到下一輪遍歷的最大下標，如果該下標超過了數組長度，那么結束遍歷，返回步數，否則將上一輪的最終節點加一作為起始節點，并將下一輪最大下標最為結束節點，繼續遍歷。題目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 評論0 收藏0
LeetCode[45] Jump Game II

摘要：復雜度思路每次設置一個窗口，觀察在這一步下能到達的最遠距離，不斷的移動這個窗口。計數，需要移動幾次，才能覆蓋到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 評論0 收藏0