45. 跳躍游戲 II
題目
給定一個非負整數陣列，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/jump-game-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
題解思路
1>源代碼
# 貪心
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
steps = 0
maxpos = 0
end = 0
for i in range(n-1):
if maxpos>=i:
maxpos = max(maxpos, nums[i]+i)
if i==end:
steps += 1
end = maxpos
return steps
# 超時
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)-1
steps = 0
while n>0:
for i in range(n):
if i+nums[i]>=n:
steps += 1
n = i
break
return steps
2>演算法介紹
本題是一道貪心演算法的題目，但在初見此題的時候我想到的是使用暴力方法來解題，即從最后一個元素開始計算，每次在當前元素的前面找到能跳到當前位置的最遠元素，例如：
[2,3,1,1,4]
最后一個元素為4(nums[4])，在4之前能跳到最后一個元素位置分別有nums[1]和nums[3]，我們需要找到最遠的即為nums[1]，
這種方法時間復雜度為O(n^2)，在本題中會超時，
本題的另一種方法十分巧妙，仍然是使用貪心演算法的思想，舉例說明：
[2,3,1,1,4]
對于第一個元素來說，nums[0]可以到達的位置為nums[1]和nums[2]，而nums[1]最遠可以到達nums[4]，nums[2]最遠可以到達nums[3]，所以我們就選擇nums[1]，
對于后續步驟也同上可得，所以本例的跳躍為nums[0]->nums[1]->nums[4]，有了這個思路，我們就可以將本題的時間復雜度優化到O(n)，
然而本題最最巧妙的并不是演算法，而是這個演算法的實作，具體實作詳見代碼，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264568.html
標籤：其他
下一篇：產品辯證分析