 # [刷题记录板] [leetcode] （Dec,19）每天两道题目，配 python参考解答

20主题 586积分 586 发表于 12-19-2014 12:42 PM | 显示全部楼层 |阅读模式

### 亲！马上注册或者登录会查看更多内容！

x

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)  python参考解答：

[code]class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
step = A
for i in range(1, len(A)):
if step > 0:
step -= 1
step = max(step, A【i】)
else:
return False
return True[/code]

[code]class Solution:
# @param A, a list of integers
# @return an integer
# def jump(self, A):
#     maxint = 1<<31 - 1
#     dp = [ maxint for i in range(len(A)) ]
#     dp = 0
#     for i in range(1, len(A)):
#         for j in range(i):
#             if A[j] >= (i - j):
#                 dp【i】 = min(dp【i】, dp[j] + 1)
#     return dp[len(A) - 1]
# dp is time limited exceeded!

# We use "last" to keep track of the maximum distance that has been reached
# by using the minimum steps "ret", whereas "curr" is the maximum distance
# that can be reached by using "ret+1" steps. Thus,curr = max(i+A【i】) where 0 <= i <= last.
def jump(self, A):
ret = 0
last = 0
curr = 0
for i in range(len(A)):
if i > last:
last = curr
ret += 1
curr = max(curr, i+A【i】)
return ret[/code]

### 本帖被以下淘专辑推荐:

 本版积分规则 回帖后跳转到最后一页   