题目: 这里有一个非负整数数组arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。注意，不管是什么情况下，你都无法跳到数组之外。
来源: https://leetcode-cn.com/problems/jump-game-iii/
法一: 自己的代码
思路: 利用常规的回溯模板,类似于数独题的解法,每次回溯时,先判断以前是否遍历过,再判断索引位置值是否为0,再确定下次要回溯的索引,注意用这个模板的难点在于返回值的问题,如果没有调不到值为0的位置,则返回值有两种情况,一种是False,即第一次进去超左超右都跳出去了,这时返回False,另一种是回溯的时候,返回False,这时直接pass,这时如果其它的分支也是pass的话,最后的返回值是None,这一点要明确
from collections import defaultdict from typing import List class Solution: def canReach(self, arr: List[int], start: int) -> bool: l = len(arr) memo = defaultdict(int) def recursion(index, val): # 先判断之前是否判断过,如果判断过,直接返回False if memo[index] == 1: return False elif arr[index] == 0: return True memo[index] += 1 all = [] # 用于确定下次遍历的索引 if index + val > l-1: pass else: all.append((index+val, arr[index+val])) if index - val < 0: pass else: all.append((index-val, arr[index-val])) if len(all) == 0: return False for i,j in all: # 如果返回值为False或None,则继续判断,直到遍历完所有可以遍历的索引 a = recursion(i,j) if a is False or a is None: pass else: return a ans = recursion(index=start, val=arr[start]) if ans is None or ans is False: return False else: return True if __name__ == '__main__': duixiang = Solution() # a = duixiang.canReach(arr = [47,26,216,78,179,101,42,233,185,56,303,310,169,338,51,104,308,162,81,82,169,41,106,150, # 285,298,33,251,289,236,256,227,197,186,267,326,268,243,89,347,72,0,89,157,90,333,327,76, # 106,68,355,124,234,70,43,248,259,280,199,201,312,327,217,278,330,258,348,351,223,240,143, # 244,64,343,339,101,193,18,140,312,71,225,111,79,199,226,321,344,31,177,362,115,341,79,146, # 303,348,291,250,169,78,307,325,33,338,316,201,343,37,37,0,15,341,38,44,67,280,128,31,106,220, # 172,349,142,339,181,102,351,81,209,41,181,59,216,230,170,257,52,5,338,28,75,208,307,108,103, # 34,342,82,233,263,12,167,358,316,150,337,158,78,231,26,22,147,81,12,319,161,12,75,129,54, # 119,131,334,292,253,255,98,39,67,146,15,329,120,80,347,89,124,303,315,235,55,1,100,290,187, # 333,326,87,138,48,41,153,118,192,152,279,69,154,71,152,273,61,153,267,51,106,225,204,327,50, # 15,202,244,328,3,150,355,240,240,188,92,107,244,280,102,265,273,328,115,70,221,357,101,186, # 251,116,24,125,58,185,34,356,21,108,221,169,208,230,226,235,336,304,315,334,329,229,190,20, # 104,348,132,66,265,55,212,102,167,52,2,328,114,101,196,99,155,158,337,191,119,14,347,127,305, # 142,156,92,340,358,58,7,178,79,355,289,199,251,233,351,57,115,306,179,31,42,123,87,101,218,71, # 193,205,300,180,42,19,280,233,293,181,147, # 359,190,168,191,5,58,198,154,139,29,342,261,245,141,26,251,162,360,219,233,297,287,262,112, # 87,261,21,205,131,98,161,103,57], start = 313) a = duixiang.canReach(arr = [3,0,2,1,2], start = 2) # a = duixiang.canReach(arr = [4, 2, 3, 0, 3, 1, 2], start = 0) # a = duixiang.canReach(arr = [31, 70, 40, 4, 27, 28, 44, 17, 8, 16, 64, 14, 30, 17, 25, 61, 33, 50, 45, 67, 12, 43, 72, 0, 26, 24, 33, 66, 22, # 11, 61, 15, 2, 18, 51, 37, 34, 7, 14, 29, 37, 3, 40, 3, 61, 20, 24, 22, 53, 18, 58, 56, 16, 44, 14, 5, 6, 19, 72, # 46, 49, 10, 42, 40, 46, 10, 6, 34, 17, 68, 62, 34, 33, 68], start = 10) print(a)
法二: