前往
大廳
主題

LeetCode - 55. Jump Game 解題心得

Not In My Back Yard | 2021-05-15 00:00:08 | 巴幣 0 | 人氣 249

題目連結:


題目意譯:
給定一非負整數陣列 nums,而你一開始位於陣列的開頭索引值。

每個陣列元素代表著你在該位置所能跳的最大長度。

判斷你是否能抵達最後的索引值。

限制:
1 ≦ nums.length ≦ 3 × 10 ^ 4
0 ≦ nums[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: nums = [2,3,1,1,4]
輸出: true
解釋: 跳 1 步從索引值 0 到 1,然後跳 3 步到最後的索引值。

範例 2:
輸入: nums = [3,2,1,0,4]
輸出: false
解釋: 無論如何你都會抵達索引值 3 。其最大跳躍距離為 0,因此使其無法抵達最後的索引值。


解題思維:
令一數 L 表示為在 nums 中最靠左且可以跳到結尾的索引值、以及一數 n = nums.length。

一開始,我們讓 L 之值為 n - 1(因為 nums[n - 1] 就是結尾,不用跳就可以到結尾本身)。

接著我們從 nums[n - 2] 掃到 nums[0],期間如果 i + nums[i] ≧ L(0 ≦ i ≦ n - 2),則代表我們可以從位置 i 跳到位置 L。而這也就表示著我們可以從位置 i 跳到結尾,因此我們需要將 L 更新成 i(因為此時 i 比起當前的 L 更靠左)。

掃完之後,如果 L = 0,則代表我們可以從位置 0 跳到結尾,因此符合題目的要求,所以回傳真(True);反之,回傳假(False)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作