일련의 숫자 num과 크기가 m인 또 다른 두 개의 배열 l과 r이 있다고 가정합니다. 이 l과 r은 [l[i], r[i]]와 같은 범위 쿼리를 나타냅니다. 부울 시퀀스 ans를 찾아야 합니다. 여기서 ans[i]는 하위 배열 nums[l[i]], nums[l[i] + 1], ... nums[r[i] - 1]일 때 참입니다. nums[r[i]]는 산술 시퀀스를 생성하도록 배열될 수 있습니다. 그렇지 않으면 false입니다.
수열은 적어도 두 개의 요소로 구성되고 연속된 두 요소의 차이가 모두 같으면 산술 연산이라고 합니다. 예를 들어, 일부 산술 시퀀스는 [2, 4, 6, 8, 10], [5, 5, 5, 5], [4, -2, -8, -14]이지만 [2, 2, 3, 6, 9].
따라서 입력이 nums =[6,8,7,11,5,9], l =[0,0,2], r =[2,3,5]와 같으면 출력은 [True , 거짓, 참] 왜냐하면 -
-
쿼리 [0, 2]의 경우 시퀀스는 [6,8,7]이고 [6,7,8]로 재배열될 수 있으며 유효합니다.
-
쿼리 [0, 3]의 경우 시퀀스는 [6,8,7,11]이며 산술 시퀀스로 재정렬할 수 없습니다.
-
쿼리 [2, 5]의 경우 시퀀스는 [7,11,5,9]이고 [5,7,9,11]로 재배열될 수 있으며 유효합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
new :=l과 같은 크기의 목록과 모든 참값으로 채움
-
범위 0에서 l - 1까지의 i에 대해 수행
-
data :=인덱스 l[i]에서 r[i]까지의 하위 목록
-
목록 데이터 정렬
-
d :=새 목록
-
범위 0에서 데이터 크기 - 2에 있는 j의 경우 수행
-
데이터 삽입[j+1] - d
끝에 데이터[j]
-
-
d :=d의 새 집합에서 새 목록
-
d의 크기가 1과 같지 않으면
-
new[i] :=거짓
-
-
-
새로 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, l, r): new = [True]*len(l) for i in range(len(l)): data = nums[l[i]:r[i]+1] data.sort() d = [] for j in range(len(data) - 1): d.append(data[j+1] - data[j]) d = list(set(d)) if len(d) != 1: new[i] = False return new nums = [6,8,7,11,5,9] l = [0,0,2] r = [2,3,5] print(solve(nums, l, r))
입력
[6,8,7,11,5,9], [0,0,2], [2,3,5]
출력
[True,False,True]