Skip to content

Instantly share code, notes, and snippets.

@zfz
Last active February 18, 2019 21:16
Show Gist options
  • Save zfz/e977c5a7e95145618757d1ae0ab66526 to your computer and use it in GitHub Desktop.
Save zfz/e977c5a7e95145618757d1ae0ab66526 to your computer and use it in GitHub Desktop.
class Solution(object):
def solution(self, A):
n = len(A)
res = [n-1] # last element is counted
even = {n-1: True, None: False}
odd = {n-1: True, None: False}
def check_pos(i, flag):
if flag % 2:
if i in odd:
return odd[i]
elif flag % 2 == 0:
if i in even:
return even[i]
jump_pos = find_pos(i, flag)
if jump_pos == n-1:
return True
elif 0 <= jump_pos < n-1:
if (flag+1) % 2:
if jump_pos in even:
return even[jump_pos]
elif (flag+1) % 2 == 0:
if jump_pos in odd:
return odd[jump_pos]
check_res = check_pos(jump_pos, (flag+1) % 2)
if (flag+1) % 2:
even[jump_pos] = check_res
elif (flag+1) % 2 == 0:
odd[jump_pos] = check_res
return check_res
else:
return False
def find_pos(i, flag):
minimal = float('inf')
jump_pos = -1
if flag == 1:
for j in range(i+1, n):
if A[i] < A[j] and A[j]-A[i] < minimal:
minimal = A[j] - A[i]
jump_pos = j
else:
for j in range(i+1, n):
if A[j] < A[i] and A[i]-A[j] < minimal:
minimal = A[i] - A[j]
jump_pos = j
return jump_pos
for i in range(n-2, -1, -1):
if check_pos(i, 1):
res.append(i)
return res
if __name__ == "__main__":
print(Solution().solution([10, 13, 12, 14, 15]))
print(Solution().solution([14, 13, 12, 14, 15]))
print(Solution().solution([10, 11, 14, 11, 10]))
print(Solution().solution([10, 12, 14, 13, 15]))
print(Solution().solution([10, 11, 14, 11, 10]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment