[LeetCode]题解（python）：045-Jump Game II

题目来源：

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

题意分析：

　　给出一个数组。数组里面的数代表这个位置最多可以跳多少步。那么从起始位置跳到最后的位置至少需要多少步。比如 A = [2,3,1,1,4]，那么可以起始位置跳到最后的最短路径是2->3->4。一共2跳就可以了。

题目思路：

　　①看到这题的第一思路就是把他转化为图问题，每个位置对应的数就是他相邻的可以跳的节点。然后用最短路的思想去解决问题。这个的时间复杂度是O（n^2)。

　　②提交后发现时间很慢，所以查看了一下网上的做法。网上是不断扩展可以跳的区域，先把一跳到达的区域算出来，然后计算两跳的，一直到跳跃区域包括最后位置。这个方法的时间复杂度是O（n）。

代码（python）：

 1 import Queue
 2 class Solution(object):
 3     def jump(self, nums):
 4         """
 5         :type nums: List[int]
 6         :rtype: int
 7         """
 8         q = Queue.Queue()
 9         size = len(nums);visit = [False for i in range(size)]
10         count = [0 for i in range(size)]
11         if size <= 1:
12             return 0
13         q.put(0);visit[0] = True
14         while not q.empty():
15             tmp = q.get();n = nums[tmp]
16             for i in range(n):
17                 if tmp + n - i >= size - 1:
18                     return count[tmp] + 1
19                 if not visit[tmp + n - i]:
20                     visit[tmp + n - i] = True
21                     count[tmp + n - i] = count[tmp] + 1
22                     q.put(tmp + n - i)

最短路

 1 import Queue
 2 class Solution(object):
 3     def jump(self, nums):
 4         """
 5         :type nums: List[int]
 6         :rtype: int
 7         """
 8         count = 0
 9         size = len(nums)
10         if size <= 1:
11             return 0
12         right = 0;left = 0
13         while True:
14             count += 1
15             old_right = right
16             while left <= old_right:
17                 new_right = left + nums[left]
18                 if new_right >= size - 1:
19                     return count
20                 if new_right > right:
21                     right = new_right
22                 left += 1

扩展跳跃区域

转载请注明出处：http://www.cnblogs.com/chruny/p/4952760.html