1310. 하위 배열의 XOR 쿼리
난이도:중
주제: 배열, 비트 조작, 접두사 합계
양의 정수로 구성된 배열 arr이 제공됩니다. 쿼리[i] = [lefti, righti].
인 배열 쿼리도 제공됩니다.각 쿼리에 대해 왼쪽i에서 오른쪽i으로 요소의 XOR을 계산합니다(즉, arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).
답변답변[i]이 i번째 쿼리에 대한 답인 배열 답변을 반환합니다.
예 1:
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:
제약조건:
힌트:
해결책:
접두사 XOR 기술을 사용할 수 있습니다. 작동 방식은 다음과 같습니다.
접두사 XOR 배열: 접두사 XOR 배열을 계산합니다. 여기서 접두사[i]는 배열 시작부터 인덱스 i까지 모든 요소의 XOR을 나타냅니다. 이를 통해 일정한 시간에 모든 하위 배열의 XOR을 계산할 수 있습니다.
하위 배열의 XOR:
이를 통해 접두사 XOR 배열을 구성한 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다.
PHP에서 이 솔루션을 구현해 보겠습니다: 1310. 하위 배열의 XOR 쿼리
설명:
접두사 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].
질의 응답:
- 각 쿼리 [left, right]에 대해 다음을 사용하여 하위 배열 arr[left]와 arr[right]의 XOR을 계산합니다.
- 접두사[오른쪽] ^ 접두사[왼쪽 - 1] (왼쪽 > 0인 경우)
- 접두사[오른쪽](왼쪽인 경우 == 0)
시간 복잡도:
이 접근 방식을 사용하면 최대 30,000개의 배열에서 최대 30,000개의 쿼리를 효율적으로 처리할 수 있습니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
위 내용은 하위 배열의 XOR 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!