Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

하위 배열을 확인하는 프로그램은 Python에서 산술 시퀀스에서 재정렬할 수 있는지 여부를 확인할 수 있습니다.

<시간/>

일련의 숫자 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]