>  기사  >  백엔드 개발  >  하위 배열의 XOR 쿼리

하위 배열의 XOR 쿼리

DDD
DDD원래의
2024-09-13 22:17:421013검색

XOR Queries of a Subarray

1310. 하위 배열의 XOR 쿼리

난이도:

주제: 배열, 비트 조작, 접두사 합계

양의 정수로 구성된 배열 arr이 제공됩니다. 쿼리[i] = [lefti, righti].

인 배열 쿼리도 제공됩니다.

각 쿼리에 대해 왼쪽i에서 오른쪽i으로 요소의 XOR을 계산합니다(즉, arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).

답변답변[i]이 i번째 쿼리에 대한 답인 배열 답변을 반환합니다.

예 1:

  • 입력: arr = [1,3,4,8], 쿼리 = [[0,1],[1,2],[0,3],[3,3]]
  • 출력: [2,7,14,8]
  • 설명: 배열 요소의 이진 표현은 다음과 같습니다.
  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

쿼리의 XOR 값은 다음과 같습니다.

  [0,1] = 1 xor 3 = 2
  [1,2] = 3 xor 4 = 7
  [0,3] = 1 xor 3 xor 4 xor 8 = 14
  [3,3] = 8

예 2:

  • 입력: arr = [4,8,2,10], 쿼리 = [[2,3],[1,3],[0,0],[0,3]]
  • 출력: [8,0,4,4]

제약조건:

  • 1 <= arr.length, query.length <= 3 * 104
  • 1 <= arr[i] <= 109
  • 쿼리[i].length == 2
  • 0 <= 왼쪽i <= 오른쪽i < 길이

힌트:

  1. x ^y ^x 의 결과는 무엇입니까?
  2. XOR의 접두어 합계를 계산합니다.
  3. 접두사 합계 값으로 쿼리를 처리합니다.

해결책:

접두사 XOR 기술을 사용할 수 있습니다. 작동 방식은 다음과 같습니다.

접근하다:

  1. 접두사 XOR 배열: 접두사 XOR 배열을 계산합니다. 여기서 접두사[i]는 배열 시작부터 인덱스 i까지 모든 요소의 XOR을 나타냅니다. 이를 통해 일정한 시간에 모든 하위 배열의 XOR을 계산할 수 있습니다.

  2. 하위 배열의 XOR:

    • 왼쪽 인덱스와 오른쪽 인덱스 간 요소의 XOR을 계산하려면 다음을 수행하세요.
      • 남은 경우> 0이면 접두어[오른쪽] ^ 접두어[왼쪽 - 1]로 왼쪽에서 오른쪽으로 XOR을 계산할 수 있습니다.
      • left == 0이면 결과는 단순히 접두사[right]입니다.

이를 통해 접두사 XOR 배열을 구성한 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다.

계획:

  1. 접두사 XOR 배열을 만듭니다.
  2. 각 쿼리에 대해 접두사 XOR 배열을 사용하여 [left_i, right_i] 범위에 대한 XOR을 계산합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1310. 하위 배열의 XOR 쿼리






설명:

  1. 접두사 XOR 구성:

    • 배열 접두사는 prefix[i]가 arr[0]부터 arr[i]까지 모든 요소의 XOR을 포함하도록 구성됩니다.
    • 예를 들어 arr = [1, 3, 4, 8]인 경우 접두사 배열은 [1, 1^3, 1^3^4, 1^3^4^8] 또는 [1, 2입니다. , 6, 14].
  2. 질의 응답:

    • 각 쿼리 [left, right]에 대해 다음을 사용하여 하위 배열 arr[left]와 arr[right]의 XOR을 계산합니다.
      • 접두사[오른쪽] ^ 접두사[왼쪽 - 1] (왼쪽 > 0인 경우)
      • 접두사[오른쪽](왼쪽인 경우 == 0)

시간 복잡도:

  • 접두사 배열 만들기: O(n), 여기서 n은 배열의 길이입니다.
  • 쿼리 처리: O(q), 여기서 q는 쿼리 수입니다.
  • 전체 시간 복잡도: O(n q), 이는 주어진 제약 조건에 효율적입니다.

이 접근 방식을 사용하면 최대 30,000개의 배열에서 최대 30,000개의 쿼리를 효율적으로 처리할 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 하위 배열의 XOR 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.