num이라는 순환 목록이 있다고 가정합니다. 따라서 첫 번째 요소와 마지막 요소는 이웃입니다. 따라서 임의의 인덱스에서 시작하여 nums[i]가 양수 값이면 nums[i] 단계만큼 앞으로 이동할 수 있고, 그렇지 않으면 음수 값이면 뒤로 이동할 수 있습니다. 길이가 1보다 큰 사이클이 있는지 확인하여 경로가 앞으로만 이동하거나 뒤로만 이동하는지 확인해야 합니다.
따라서 입력이 nums =[-1, 2, -1, 1, 2]와 같으면 순방향 경로 [1 -> 3 -> 4 -> 1]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=숫자 크기
- n이 0과 같으면
- 거짓을 반환
- seen :=크기가 n이고 0으로 채워진 배열
- nums의 각 요소 x에 대해 x mod n을 가져와서 nums 업데이트
- iter :=0
- 0 ~ n - 1 범위의 i에 대해
- nums[i]가 0과 같으면
- 다음 반복으로 이동
- iter :=iter + 1
- pos :=사실
- neg :=참
- 커:=나
- 다음을 반복하여 수행합니다.
- nums[curr]와 see[curr]가 iter와 같으면
- 참 반환
- 본[curr]이 0이 아니면
- 루프에서 나오다
- nums[curr]> 0이면
- neg :=거짓
- 그렇지 않으면
- pos :=거짓
- neg와 pos가 모두 거짓이면
- 루프에서 나오다
- 본[curr] :=반복
- curr :=(curr + nums[curr] + n) 모드 n
- nums[curr]가 0과 같으면
- 루프에서 나오다
- nums[curr]와 see[curr]가 iter와 같으면
- nums[i]가 0과 같으면
- 거짓을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums): n = len(nums) if n == 0: return False seen = [0]*n nums = [x % n for x in nums] iter = 0 for i in range(n): if nums[i] == 0: continue iter += 1 pos = True neg = True curr = i while True: if nums[curr] and seen[curr] == iter: return True if seen[curr] : break if nums[curr] > 0: neg = False else: pos = False if not neg and not pos: break seen[curr] = iter curr = (curr + nums[curr] + n) % n if nums[curr] == 0: break return False nums = [-1, 2, -1, 1, 2] print(solve(nums))
입력
[-1, 2, -1, 1, 2]
출력
True