題目
Jump Game II - LeetCode
我們可以認(rèn)為“ nums”中每個(gè)項(xiàng)目的數(shù)字代表一個(gè)覆蓋區(qū)域酌泰。 因此，為了解決這個(gè)問(wèn)題匕累，我們希望用最少的區(qū)域覆蓋整個(gè)范圍陵刹。值得注意的是，這我們雖然把這種算法稱為貪婪算法欢嘿，一般而言衰琐，貪婪算法找出的不是最優(yōu)解。但是炼蹦，在這道題目中羡宙，覆蓋最遠(yuǎn)的下個(gè)區(qū)域是相比其他區(qū)域而言是占優(yōu)策略Strategic dominance, 所以，在這道題目中框弛，我們是可以通過(guò)貪婪得到最優(yōu)解的辛辨。
算法的思路如下：
1.根據(jù)當(dāng)前位置及其區(qū)域，找到范圍從i 到（i + num）的相鄰區(qū)域。
2.將這些區(qū)域的最遠(yuǎn)覆蓋范圍與最大范圍進(jìn)行比較：如果（i + num）大于最大范圍斗搞，則設(shè)置下一個(gè)覆蓋范圍從r開(kāi)始指攒，最大范圍等于i + num。
3.將當(dāng)前位置更新為r僻焚。
4.繼續(xù)這樣做允悦，直到覆蓋整個(gè)區(qū)域。
class Solution:
def jump(self, nums) -> int:
if not nums or len(nums) == 1:
return 0
des = len(nums) - 1
res = 0
i = 0
max_range = 0
nxt = 0
while i < des:
if i + nums[i] >= des:
return res + 1
for r in range(i + 1, i + nums[i] + 1):
if r + nums[r] > max_range:
max_range = r + nums[r]
nxt = r
i = nxt
res += 1
如何刷題 : Leetcode 題目的正確打開(kāi)方式
我的GitHub : Jedi-XL
其他題目答案：leetcode題目答案講解匯總（Python版 持續(xù)更新）
我的博客里還有其他好東西： 苔原帶
