內卷大廠系列《跳躍遊戲三連擊》

語言: CN / TW / HK

theme: vuepress

一起養成寫作習慣!這是我參與「掘金日新計劃 · 4 月更文挑戰」的第15天,點選檢視活動詳情

一、跳躍遊戲 I

給定一個非負整數陣列 nums ,你最初位於陣列的 第一個下標

陣列中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個下標。

示例 1

java 輸入:nums = [2,3,1,1,4] 輸出:true 解釋:可以先跳 1 步,從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。

示例 2

java 輸入:nums = [3,2,1,0,4] 輸出:false 解釋:無論怎樣,總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 , 所以永遠不可能到達最後一個下標。

leetcode

1、分析

小人從0位置想跳到N-1位置,陣列中的值代表能跳的最大步數

陣列下標換算問題,設定一個變數max,代表能跳到右側的最大位置

2、實現

java public static boolean canJump(int[] nums) { if (nums == null || nums.length < 2) { return true; } // max代表能跳到右側的最大位置 int max = nums[0]; for (int i = 1; i < nums.length; i++) { if (i > max) { return false; } max = Math.max(max, i + nums[i]); } return true; }

二、跳躍遊戲 II

給你一個非負整數陣列 nums ,你最初位於陣列的第一個位置。

陣列中的每個元素代表你在該位置可以跳躍的最大長度。

你的目標是使用最少的跳躍次數到達陣列的最後一個位置。

假設你總是可以到達陣列的最後一個位置。

示例 1:

java 輸入: nums = [2,3,1,1,4] 輸出: 2 解釋: 跳到最後一個位置的最小跳躍數是 2。   從下標為 0 跳到下標為 1 的位置,跳 1 步,然後跳 3 步到達陣列的最後一個位置。

示例 2:

java 輸入: nums = [2,3,0,1,4] 輸出: 2

leetcode

1、分析

跳躍步數:不是跳躍一步的含義,比如1步內最遠能跳到哪的意思。

設定三個變數,step跳躍步數,cur當前跳躍步數內最遠能到哪,next下一步最遠能跳到哪

幾步跳躍(step)能到達最右位置(cur),再跳一次能到達最右位置(next)

step、cur、next的初始值如下:

0步跳躍step=0,能到達最右位置cur=0,在跳一步能到達最右位置next=arr[0]

  • step:當前最少跳躍步數能到i位置
  • cur:跳躍的步數不超過step,最右能到哪個位置
  • next:跳躍的步數不超過step+1,最右能到哪個位置

i > cur,說明step步不足以到i,step++,增加步數(跳躍次數),cur = next,說白了next就是提前準備好,為了下次step cover不住的時候,next給cur

i ≤ cur,說明step步內還能到i,能cover住,看能不能更新next(next = max(next, i+arr[i])),next得時刻注意能不能變的更遠

2、實現

java public static int jump(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int step = 0; int cur = 0; int next = arr[0]; for (int i = 1; i < arr.length; i++) { if (cur < i) { step++; cur = next; } next = Math.max(next, i + arr[i]); } return step; }

三、跳躍遊戲 III

這裡有一個非負整數陣列 arr,你最開始位於該陣列的起始下標 start 處。當你位於下標 i 處時,你可 以跳到 i + arr[i] 或者 i - arr[i]。

請你判斷自己是否能夠跳到對應元素值為 0 的 任一 下標處。

注意,不管是什麼情況下,你都無法跳到陣列之外。

示例 1

java 輸入:arr = [4,2,3,0,3,1,2], start = 5 輸出:true 解釋: 到達值為 0 的下標 3 有以下可能方案: 下標 5 -> 下標 4 -> 下標 1 -> 下標 3 下標 5 -> 下標 6 -> 下標 4 -> 下標 1 -> 下標 3

示例 2

java 輸入:arr = [4,2,3,0,3,1,2], start = 0 輸出:true 解釋: 到達值為 0 的下標 3 有以下可能方案: 下標 0 -> 下標 4 -> 下標 1 -> 下標 3

示例 3

java 輸入:arr = [3,0,2,1,2], start = 2 輸出:false 解釋:無法到達值為 0 的下標 1 處。

leetcode

1、分析

當前來到i位置,只有兩種選擇,往左跳或往右跳,類似二叉樹。

寬度優先遍歷(佇列)的作用:二叉樹,兩個分支,既可以往左邊走(left),又可以往右邊走(right)

  • key:陣列下標,value:層數
  • 去重,記錄走過的決策

2、實現

java public static boolean canReach(int[] arr, int start) { if (arr == null || start < 0 || start > arr.length - 1) { return false; } // 通過佇列實現寬度優先遍歷 Queue<Integer> queue = new LinkedList<>(); // 按層遍歷 HashMap<Integer, Integer> levelMap = new HashMap<>(); queue.add(start); levelMap.put(start, 0); while (!queue.isEmpty()) { int cur = queue.poll(); int level = levelMap.get(cur); if (cur + arr[cur] < arr.length && arr[cur + arr[cur]] == 0) { return true; } else { int left = cur - arr[cur]; if (left >= 0 && !levelMap.containsKey(left)) { queue.add(left); levelMap.put(left, level + 1); } int right = cur + arr[cur]; if (right < arr.length && !levelMap.containsKey(right)) { queue.add(right); levelMap.put(right, level + 1); } } } return false; }