LeetCode 跳跃游戏1&2 贪心算法_leetcode 贪心算法 python

这两道题是比较典型的贪心算法题。从局部最优最终得出全局最优解。
第一题
如果每次都从当前位置跳到最远，有可能导致最终能到终点却跳不到终点，比如[3,2,2,0,4]，如果直接从3跳到0，0就没法跳了，到不了终点，但是其实可以从3->2，再从2->4这样就可以跳到终点。这是局部最远跳
所以这里的贪心思想，我觉得应该是这样：从i + 1 <=j<= i + nums[i]这个区间，都是当前位置 i 所能跳到的，我们要做的就是在这个区间内，找到下一个跳得最远的元素，也即找到最大的 j + nums[j]，这样的话，就能保证跳得尽可能远，最终得到的答案也是全局正确的。其实这种跳法，就是跳跃次数最少的跳法，也就是跳跃游戏2的问题，跳到终点所需的最少跳跃次数。因为我们每次都选出下一个能跳得最远的位置，保证最终是全局尽可能远的跳。
这样来看，这两个问题就可以用一种跳法来解决，对于第二个问题，就增加了一个记录跳跃次数的变量，两个问题的代码基本一样。时间复杂度都还不错。

#跳跃游戏1
#当前位置 i，跳nums[i]后到达了索引为 i + nums[i]的元素，所以只要保证
#i + nums[i]大于等于最后一个元素的索引，就能跳到最后。
class Solution:  
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 1:
            return True
        i = 0
        while i < n:
            if nums[i] == 0 and i < n-1:  #跳到了0并且还不是最后一个元素
                return False
            tmp = i + nums[i]
            if tmp >= n-1:  #从当前位置可以直接跳到终点
                return True
            max_jump = 0
            index = i+1
            for j in range(i+1, tmp+1):  #寻找下一个跳得最远的元素
                if nums[j] + j >= max_jump:
                    max_jump = nums[j] + j
                    index = j
            i = index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        if n <= 1:
            return count
        i = 0
        while i < n:
            if nums[i] == 0 and i < n-1:
                return False
            if i == n-1:   #已经跳到最后一个位置，直接返回
                return count
            tmp = i + nums[i]
            if tmp >= n-1:  #当前位置i不是最后一个位置，所以还需要再跳一步
                return count + 1 #才能到达终点，所以返回count+1
            max_jump = 0
            index = i+1
            for j in range(i+1, tmp+1):   #同问题1
                if j + nums[j] >= max_jump:
                    max_jump = j + nums[j]
                    index = j
            i = index
            count += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23