LintCode Q116 Jump Game Greedy in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2017年1月12日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
# write your code here
# greedy algorithme
# time complexity: O(n)
if A is None or len(A) == 0:
return False
farest = A[0]
for i in xrange(1, len(A)):
if i <= farest and i + A[i] > farest:
farest = i + A[i]
return farest >= len(A) - 1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。