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 4
- 1 9
- 쿼리[i].length == 2
- 0 i i
힌트:
- x ^y ^x 의 결과는 무엇입니까?
- XOR의 접두어 합계를 계산합니다.
- 접두사 합계 값으로 쿼리를 처리합니다.
해결책:
접두사 XOR 기술을 사용할 수 있습니다. 작동 방식은 다음과 같습니다.
접근하다:
접두사 XOR 배열: 접두사 XOR 배열을 계산합니다. 여기서 접두사[i]는 배열 시작부터 인덱스 i까지 모든 요소의 XOR을 나타냅니다. 이를 통해 일정한 시간에 모든 하위 배열의 XOR을 계산할 수 있습니다.
-
하위 배열의 XOR:
- 왼쪽 인덱스와 오른쪽 인덱스 간 요소의 XOR을 계산하려면 다음을 수행하세요.
- 남은 경우> 0이면 접두어[오른쪽] ^ 접두어[왼쪽 - 1]로 왼쪽에서 오른쪽으로 XOR을 계산할 수 있습니다.
- left == 0이면 결과는 단순히 접두사[right]입니다.
- 왼쪽 인덱스와 오른쪽 인덱스 간 요소의 XOR을 계산하려면 다음을 수행하세요.
이를 통해 접두사 XOR 배열을 구성한 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다.
계획:
- 접두사 XOR 배열을 만듭니다.
- 각 쿼리에 대해 접두사 XOR 배열을 사용하여 [left_i, right_i] 범위에 대한 XOR을 계산합니다.
PHP에서 이 솔루션을 구현해 보겠습니다: 1310. 하위 배열의 XOR 쿼리
<?php /** * @param Integer[] $arr * @param Integer[][] $queries * @return Integer[] */ function xorQueries($arr, $queries) { ... ... ... /** * go to ./solution.php */ } // Example 1 $arr1 = [1, 3, 4, 8]; $queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]]; print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8] // Example 2 $arr2 = [4, 8, 2, 10]; $queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]]; print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4] ?>
설명:
-
접두사 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)
- 각 쿼리 [left, right]에 대해 다음을 사용하여 하위 배열 arr[left]와 arr[right]의 XOR을 계산합니다.
시간 복잡도:
- 접두사 배열 만들기: O(n), 여기서 n은 배열의 길이입니다.
- 쿼리 처리: O(q), 여기서 q는 쿼리 수입니다.
- 전체 시간 복잡도: O(n q), 이는 주어진 제약 조건에 효율적입니다.
이 접근 방식을 사용하면 최대 30,000개의 배열에서 최대 30,000개의 쿼리를 효율적으로 처리할 수 있습니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
- 링크드인
- 깃허브
위 내용은 하위 배열의 XOR 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

PHP 로깅은 웹 애플리케이션을 모니터링하고 디버깅하고 중요한 이벤트, 오류 및 런타임 동작을 캡처하는 데 필수적입니다. 시스템 성능에 대한 귀중한 통찰력을 제공하고 문제를 식별하며 더 빠른 문제 해결을 지원합니다.

Laravel은 직관적 인 플래시 방법을 사용하여 임시 세션 데이터 처리를 단순화합니다. 응용 프로그램에 간단한 메시지, 경고 또는 알림을 표시하는 데 적합합니다. 데이터는 기본적으로 후속 요청에만 지속됩니다. $ 요청-

PHP 클라이언트 URL (CURL) 확장자는 개발자를위한 강력한 도구이며 원격 서버 및 REST API와의 원활한 상호 작용을 가능하게합니다. PHP CURL은 존경받는 다중 프로모토콜 파일 전송 라이브러리 인 Libcurl을 활용하여 효율적인 execu를 용이하게합니다.

Laravel은 간결한 HTTP 응답 시뮬레이션 구문을 제공하여 HTTP 상호 작용 테스트를 단순화합니다. 이 접근법은 테스트 시뮬레이션을보다 직관적으로 만들면서 코드 중복성을 크게 줄입니다. 기본 구현은 다양한 응답 유형 단축키를 제공합니다. Illuminate \ support \ Facades \ http를 사용하십시오. http :: 가짜 ([ 'google.com'=> 'Hello World', 'github.com'=> [ 'foo'=> 'bar'], 'forge.laravel.com'=>

고객의 가장 긴급한 문제에 실시간 인스턴트 솔루션을 제공하고 싶습니까? 라이브 채팅을 통해 고객과 실시간 대화를 나누고 문제를 즉시 해결할 수 있습니다. 그것은 당신이 당신의 관습에 더 빠른 서비스를 제공 할 수 있도록합니다.

Alipay PHP ...

기사는 PHP 5.3에 도입 된 PHP의 LSB (Late STATIC BING)에 대해 논의하여 정적 방법의 런타임 해상도가보다 유연한 상속을 요구할 수있게한다. LSB의 실제 응용 프로그램 및 잠재적 성능

이 기사에서는 프레임 워크에 사용자 정의 기능 추가, 아키텍처 이해, 확장 지점 식별 및 통합 및 디버깅을위한 모범 사례에 중점을 둡니다.


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

PhpStorm 맥 버전
최신(2018.2.1) 전문 PHP 통합 개발 도구

Atom Editor Mac 버전 다운로드
가장 인기 있는 오픈 소스 편집기

mPDF
mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

Dreamweaver Mac版
시각적 웹 개발 도구

뜨거운 주제



