45. Jump Game II

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/jump-game-ii/description/

想法

贪心！
首先想到的两个字，但是又不知道具体怎么用了，可能忘记了贪心的核心思想…

其实也就是一张图，求最短路径，但是图相关的算法基本上全忘了

遍历，更新，应该就是这样吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        a = [sys.maxsize] * len(nums)
        a[0] = 0
        for i, n in enumerate(nums):
            for j in range(1, n + 1):
                if i + j < len(a):
                    a[i + j] = min(a[i + j], a[i] + 1)
        return a[-1]

算是比较暴力的解决办法，不出所料，TLE…
毕竟是hard的题，不会那么简单吧

贪心，深度优先

答案

参考一个人写的贪心的答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        end = 0
        furthest = 0
        for i, n in enumerate(nums[:-1]):
            furthest = max(furthest, i + n)
            if i == end:
                ans += 1
                end = furthest
        return ans

回顾

这个答案很精巧

贪心，抓住关键点：能通过一步，走到最远的地方

经典