資訊專欄INFORMATION COLUMN
摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。
Jump Game I 最新解法請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/...
Given an array of non-negative integers, you are initially positioned at the first index of the array.貪心法 復(fù)雜度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.
時(shí)間 O(N) 空間 O(1)
思路如果只是判斷能否跳到終點(diǎn)，我們只要在遍歷數(shù)組的過(guò)程中，更新每個(gè)點(diǎn)能跳到最遠(yuǎn)的范圍就行了，如果最后這個(gè)范圍大于等于終點(diǎn)，就是可以跳到。
代碼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.雙指針?lè)?/b> 復(fù)雜度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.)
時(shí)間 O(N) 空間 O(1)
思路如果要計(jì)算最短的步數(shù)，就不能貪心每次都找最遠(yuǎn)距離了，因?yàn)橛锌赡芤婚_(kāi)始跳的遠(yuǎn)的路徑，后面反而更慢。所以我們要探索所有的可能性，這里用快慢指針?lè)殖鲆粔K當(dāng)前結(jié)點(diǎn)能跳的一塊區(qū)域，然后再對(duì)這塊區(qū)域遍歷，找出這塊區(qū)域能跳到的下一塊區(qū)域的上下邊界，每塊區(qū)域都對(duì)應(yīng)一步，直到上界超過(guò)終點(diǎn)時(shí)為之。
代碼public class Solution {
public int jump(int[] nums) {
int high = 0, low = 0, preHigh = 0, step = 0;
while(high < nums.length - 1){
step++;
//記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界
preHigh = high;
for(int i = low; i <= preHigh; i++){
//更新下一個(gè)區(qū)域的上界
high = Math.max(high, i + nums[i]);
}
//更新下一個(gè)區(qū)域的下界
low = preHigh + 1;
}
return step;
}
}
后續(xù) Follow Up
Q：如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)？
A：可以使用DFS，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64453.html
摘要：例如，將函數(shù)修改為小恐龍眨眼這樣小恐龍會(huì)不停的眨眼睛。小恐龍的開(kāi)場(chǎng)動(dòng)畫(huà)下面來(lái)實(shí)現(xiàn)小恐龍對(duì)鍵盤按鍵的響應(yīng)。接下來(lái)還需要更新動(dòng)畫(huà)幀才能實(shí)現(xiàn)小恐龍的奔跑動(dòng)畫(huà)。 文章首發(fā)于我的 GitHub 博客 前言 上一篇文章：《Chrome 小恐龍游戲源碼探究七 -- 晝夜模式交替》實(shí)現(xiàn)了游戲晝夜模式的交替，這一篇文章中，將實(shí)現(xiàn)：1、小恐龍的繪制 2、鍵盤對(duì)小恐龍的控制 3、頁(yè)面失焦后，重新聚焦會(huì)重置...
摘要：所以，我們這個(gè)小游戲發(fā)布以后，我們就開(kāi)始花了很多很多時(shí)間來(lái)打擊外掛。二距離判斷像素點(diǎn)判斷該方法采用自目前最火的跳一跳小游戲輔助程序。 作者：Hahn， 騰訊高級(jí)UI工程師商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系騰訊WeTest獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 原文鏈接：http://wetest.qq.com/lab/view/364.html WeTest 導(dǎo)讀 張小龍：這個(gè)游戲發(fā)布以后，其實(shí)它的效果有點(diǎn)超...
摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開(kāi)始節(jié)點(diǎn)和結(jié)束下標(biāo)，找到下一輪遍歷的最大下標(biāo)，如果該下標(biāo)超過(guò)了數(shù)組長(zhǎng)度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點(diǎn)加一作為起始節(jié)點(diǎn)，并將下一輪最大下標(biāo)最為結(jié)束節(jié)點(diǎn)，繼續(xù)遍歷。 題目要求 Given an array of non-negative integers, you are initially positioned at the ...
摘要：復(fù)雜度思路每次設(shè)置一個(gè)窗口，觀察在這一步下能到達(dá)的最遠(yuǎn)距離，不斷的移動(dòng)這個(gè)窗口。計(jì)數(shù)，需要移動(dòng)幾次，才能覆蓋到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...
閱讀 2099·2021-11-02 14:48
閱讀 2776·2019-08-30 14:19
閱讀 2942·2019-08-30 13:19
閱讀 1310·2019-08-29 16:17
閱讀 3246·2019-08-26 14:05
閱讀 3001·2019-08-26 13:58
閱讀 3088·2019-08-23 18:10
閱讀 1117·2019-08-23 18:04
