主題

LeetCode - 45. Jump Game II 解題心得

Not In My Back Yard | 2021-05-16 00:00:06 | 巴幣 0 | 人氣 55

題目連結:


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

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

你的目標是在最少的跳躍數下抵達最後的索引值。

你可以假設你一定可以抵達結尾。

限制:
1 ≦ nums.length ≦ 1000
0 ≦ nums[i] ≦ 10 ^ 5



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

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


解題思維:
定義一陣列 D,其中 D[i] 代表著從位置 i 跳到結尾所需的最少跳躍數、以及一數 n = nums.length。

根據題意,D[i] 應為
D[i + 1] 、 D[i + 2] 、 …… D[i + nums[i]]
中的最小值 + 1。意即 D[i] =
min(D[i + 1], D[i + 2], ……, D[i + nums[i]]) + 1
注意,這邊沒有考慮進 i + nums[i] 可能會超過範圍(≧ n)之情形。

一開始,除了 D[n - 1] = 0 以外,其他 D[i] 之初始值為一個很大的數字(例如,值超過 n 的數字),代表其他位置當前無法跳到結尾。

接著我們從 nums[n - 2] 掃到 nums[0],期間我們對每個數字 nums[i] 根據遞迴式找到
D[i + 1] 、 D[i + 2] 、 …… D[i + nums[i]]
中的最小值(記得忽略超出範圍的索引值)之後,將該值 + 1 即是 D[i] 之值。

掃完之後,D[0] 之值即是所求。




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

創作回應

更多創作