[toc]
leetcode 45. 跳躍游戲 II.
題目描述
- 跳躍游戲 II
給定一個(gè)長(zhǎng)度為 n 的 0 索引整數(shù)數(shù)組 nums恕沫。初始位置為 nums[0]。
每個(gè)元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長(zhǎng)度鲸阔。換句話說迄委，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:
0 <= j <= nums[i]
i + j < n
返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)叙身。生成的測(cè)試用例可以到達(dá) nums[n - 1]信轿。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置财忽，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置紧唱。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
題目保證可以到達(dá) nums[n-1]
解題思路
法1
方法1:模擬跳躍\
要使跳躍的次數(shù)最少那么前后兩次跳躍之間必須默契配合才行
就是說第一次跳躍的位置必須考慮到第二次跳躍,兩次跳躍的可以總距離必須
最遠(yuǎn)才可以,也就是相鄰兩次具有相關(guān)性
我們可以使用動(dòng)態(tài)規(guī)劃的思想來(lái)解決這個(gè)問題
- 確定本次可以跳躍的區(qū)間
- 跳躍 的位置加上該位置可以跳躍的距離就是兩次跳躍的最遠(yuǎn)距離,最遠(yuǎn)距離最長(zhǎng)的就是本次跳躍的位置,
- 每次循環(huán),找出每次可以跳躍的區(qū)間,然后模擬跳到給位置上,在找下一個(gè)跳躍區(qū)間,直到跳完,既然跳躍的次數(shù)
- 時(shí)間復(fù)雜度(O())
- 空間復(fù)雜度(O())
執(zhí)行結(jié)果
法1
// 選擇跳躍的位置 返回最遠(yuǎn)兩次跳躍的長(zhǎng)度
func chise(nums []int) (r int) {
for i := 0; i < len(nums); i++ {
if r < i+nums[i] {
r = i + nums[i]
}
}
return
}
func jump(nums []int) (r int) {
t := 0
for i, j := 1, nums[0]+1; j < len(nums); r++ {
t = j
j = i + chise(nums[i:j]) + 1//從截止位置的后一個(gè)開始記錄區(qū)間(左閉右開的結(jié)構(gòu)特點(diǎn))
i = t
}
r++
return
}
執(zhí)行結(jié)果：
通過
顯示詳情
查看示例代碼
添加備注
執(zhí)行用時(shí)：
8 ms
, 在所有 Go 提交中擊敗了
97.23%
的用戶
內(nèi)存消耗：
5.8 MB
, 在所有 Go 提交中擊敗了
44.27%
的用戶
通過測(cè)試用例：
109 / 109
炫耀一下:
法2
法3
本文由mdnice多平臺(tái)發(fā)布
