一氧卧、 leetcode 55 跳躍游戲
給定一個非負整數(shù)數(shù)組或舞，你最初位于數(shù)組的第一個位置淹办。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個位置低葫。
示例 1:
輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置仍律。示例 2:
輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣嘿悬，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 水泉， 所以你永遠不可能到達最后一個位置善涨。
解題思路：
- 如果某一個作為起跳點的格子可以跳躍的距離是3，那么表示后面3個格子都可以作為起跳點草则。
- 可以對每一個都能作為起跳點的格子都嘗試一次钢拧，把能跳到最遠的距離不斷更新。
- 如果可以一直跳到最后炕横，就返回
true源内，如果在遍歷數(shù)組的過程中，發(fā)現(xiàn)當前數(shù)組下標大于所能到達的最遠距離看锉，那么直接返回false姿锭。
boolean canJump(int[] nums){
int maxReach = 0;
for(int i = 0; i < nums.length; i++){
if(i > maxReach) return false;
maxReach = Math.max(maxReach, nums[i] + i);
}
return true;
}
二、leetcode 45 跳躍游戲 II
給定一個非負整數(shù)數(shù)組伯铣，你最初位于數(shù)組的第一個位置呻此。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置腔寡。
示例：
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2焚鲜。從下標為 0 跳到下標為 1 的位置，跳 1 步放前，然后跳 3 步到達數(shù)組的最后一個位置忿磅。
解題思路：
- 如果某一個作為起跳點的格子可以跳躍的距離是3，那么表示后面3個格子都可以作為起跳點凭语。
- 可以對每一個能作為起跳點的格子都嘗試跳一次葱她，把能跳到最遠的距離不斷更新。
- 如果從這個起跳點起跳叫做第1次跳躍似扔，那么從后面3個格子起跳都可以叫做第2次跳躍吨些。
- 所以搓谆，當一次跳躍結(jié)束時，從下一個格子開始豪墅，到現(xiàn)在能跳到最遠的距離泉手，都是下一次跳躍的起跳點。
- 對每一次跳躍用
for循環(huán)來模擬 - 跳完一次之后偶器，更新下一次起跳點的范圍
- 在新的范圍內(nèi)跳斩萌，更新能跳到最遠的距離
- 對每一次跳躍用
- 記錄跳躍次數(shù)，如果跳到了終點屏轰，就得到了結(jié)果颊郎。
public int jump(int[] nums){
int start = 0;
int end = 1;
int ans = 0;
while(end < nums.length){
int maxPos = 0;
for(int i = start; i < end; i++){
maxPos = Math.max(maxPos, i + nums[i]);
}
start = end;
end = maxPos + 1;
ans++;
}
return ans;
}
三、leetcode 1306 跳躍游戲 III
這里有一個非負整數(shù)數(shù)組
arr亭枷，你最開始位于該數(shù)組的起始下標start處袭艺。當你位于下標i處時，你可以跳到i + arr[i]或者i - arr[i]叨粘。請你判斷自己是否能夠跳到對應元素值為 0 的 任意 下標處猾编。
注意，不管是什么情況下升敲，你都無法跳到數(shù)組之外
示例 1：
輸入：arr = [4,2,3,0,3,1,2], start = 5
輸出：true
解釋：
到達值為 0 的下標 3 有以下可能方案：
下標 5 -> 下標 4 -> 下標 1 -> 下標 3
下標 5 -> 下標 6 -> 下標 4 -> 下標 1 -> 下標 3
示例 2：輸入：arr = [4,2,3,0,3,1,2], start = 0
輸出：true
解釋：
到達值為 0 的下標 3 有以下可能方案：
下標 0 -> 下標 4 -> 下標 1 -> 下標 3
示例 3：輸入：arr = [3,0,2,1,2], start = 2
輸出：false
解釋：無法到達值為 0 的下標 1 處答倡。
思路：
深度優(yōu)先遍歷，依賴一個visited數(shù)組驴党，用以記錄已經(jīng)訪問過的位置
class Solution {
public boolean canReach(int[] arr, int start) {
boolean[] visited = new boolean[arr.length];
return search(arr, start, visited);
}
private boolean search(int[] arr, int start, boolean[] visited){
if(start < 0 || start >= arr.length || visited[start]) return false;
if(arr[start] == 0) return true;
visited[start] = true;
return search(arr, start+arr[start], visited) || search(arr, start-arr[start], visited);
}
}
