越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/jump-game-ii/

We can build a graph (a DAG, to be exact), with the indices in nums as the vertices, and add an edge (i,j) if and only if i < j <= i+nums[i]. We need to find the shortest path from vertex 0 to vertex len(nums)-1.

The easiest way to approach this problem is using breadth first search (BFS). Because BFS does level-order traversal, in an unweighted graph, the vertices in level l have distance l to the origin. Generally BFS requires using a queue, but for this problem specifically, we can find the (upper) boundary of a level easily, which is the maximum of i+nums[i] for every vertex i in the previous level. Note that level 0 has only 1 vertex, 0. If the boundary of level l reaches or goes past the last element in nums (len(nums)-1), then the last element is in level l, i.e. the distance from it to the origin 0 is l.

Because we only traverse the array once, the time complexity of this algorithm is $\O(n)$. Obviously we only use constant extra space.

我们可以把 nums 中的每个下标作为定点构建一张(有向无环)图。对图中的每一个结点 i 和满足 i < j <= i+nums[i] 的所有 j,构造一条边 (i,j)。在这个图上寻找从结点 0 到结点 len(nums)-1 的最短路径即可。

最方便的解决方案是用广度优先搜索(BFS)。由于 BFS 逐层遍历的性质,在无权图中在第 l 层的结点离原点的距离即是 l。一般的 BFS 算法需要使用一个队列,但是由于这道题目的特殊性,我们可以知道每一层的边界,即是对上一层的所有结点 ii+nums[i] 的最大值。如果有一层 l 的边界达到或者超过了最后一个元素,那么最后一个元素 len(nums)-i 就在第 l 层,即距离原点 0 的距离为 l

由于只需要遍历数组一次,所以这种方案的时间复杂度为 $\O(n)$;而额外空间复杂度只有 $\O(1)$。

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        level = 0
        firstInLevel, lastInLevel = 0, 0
        while True:
            lastInNextLevel = -1
            for j in range(firstInLevel, lastInLevel+1):
                lastInNextLevel = max(lastInNextLevel, j + nums[j])
            if lastInNextLevel >= len(nums) - 1:
                # dest is in next level
                return level + 1
            level += 1
            firstInLevel = lastInLevel + 1
            lastInLevel = lastInNextLevel
        return level