nums라는 숫자 목록과 또 다른 숫자 k가 있다고 가정합니다. 인덱스 k와 인덱스 i에서 시작하면 정확히 nums[i] 단계만큼 왼쪽이나 오른쪽으로 이동할 수 있습니다. 목록의 끝에 도달할 수 있는지 여부를 확인해야 합니다.
따라서 입력이 nums =[0, 0, 2, 1, 3, 3, 1, 1] k =2와 같으면 출력은 인덱스 2에서 시작한 다음 인덱스 4로 점프하는 것처럼 True가 됩니다. 그런 다음 마지막 인덱스 7로 이동합니다.
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
n:=숫자 크기
-
방문:=크기가 n이고 0으로 채워진 목록
-
tovisit :=크기 1의 목록, 그리고 거기에 k를 삽입
-
tovisit의 크기가 <0인 동안 수행
-
i:=tovisit의 마지막 요소 및 tovisit에서 삭제
-
i가 n-1과 같으면
-
참을 반환
-
-
방문[i]이 1과 같지 않으면
-
방문[i]:=1
-
위로:=i + 숫자[i]
-
아래로:=i - 숫자[i]
-
위
-
방문 마지막에 삽입
-
아래로>=0이면
-
방문 끝에 아래로 삽입
-
-
거짓을 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다-
예시
class Solution: def solve(self, nums, k): n=len(nums) visited = [0]*n tovisit = [k] while len(tovisit)>0: i=tovisit.pop() if i==n-1: return True if visited[i]!=1: visited[i]=1 up=i+nums[i] dn=i-nums[i] if up=0: tovisit.append(dn) return False ob = Solution() nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2 print(ob.solve(nums, k))
입력
[0, 0, 2, 1, 3, 3, 1, 1], 2
출력
True