찾다
백엔드 개발PHP 튜토리얼하위 배열의 XOR 쿼리

하위 배열의 XOR 쿼리

Sep 13, 2024 pm 10:17 PM

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 4
  • 1 9
  • 쿼리[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 쿼리

<?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]
?>

설명:

  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으로 문의하세요.
PHP 세션이 이미 시작되었는지 어떻게 확인할 수 있습니까?PHP 세션이 이미 시작되었는지 어떻게 확인할 수 있습니까?Apr 30, 2025 am 12:20 AM

PHP에서는 session_status () 또는 session_id ()를 사용하여 세션이 시작되었는지 확인할 수 있습니다. 1) session_status () 함수를 사용하십시오. php_session_active가 반환되면 세션이 시작되었습니다. 2) session_id () 함수를 사용하십시오. 비어 있지 않은 문자열이 반환되면 세션이 시작되었습니다. 두 방법 모두 세션 상태를 효과적으로 확인할 수 있으며 사용할 방법을 선택하면 PHP 버전 및 개인 선호도에 따라 다릅니다.

웹 응용 프로그램에서 세션을 사용하는 것이 필수적인 시나리오를 설명하십시오.웹 응용 프로그램에서 세션을 사용하는 것이 필수적인 시나리오를 설명하십시오.Apr 30, 2025 am 12:16 AM

SessionSareVitalInWebApplications, 특히 상수도가 포함되어 있습니다.

PHP에서 동시 세션 액세스를 어떻게 관리 할 수 ​​있습니까?PHP에서 동시 세션 액세스를 어떻게 관리 할 수 ​​있습니까?Apr 30, 2025 am 12:11 AM

PHP에서 동시 세션 액세스 관리 다음 방법으로 수행 할 수 있습니다. 1. 데이터베이스를 사용하여 세션 데이터를 저장하십시오. 이러한 방법은 데이터 일관성을 보장하고 동시성 성능을 향상시키는 데 도움이됩니다.

PHP 세션 사용의 한계는 무엇입니까?PHP 세션 사용의 한계는 무엇입니까?Apr 30, 2025 am 12:04 AM

phpsessionshaveseverallimitations : 1) StorageConstraintsCanleadToperFormanceIssues; 2) SecurityVulnerabilitiesSessionFixationAtCATACKSEXIST; 3) 확장 성분이 ANCHALLENGINGDUETOSERVERS-SCIFICSTORAGE; 4) SessionExpirationManagementCanbeproblematic; 5) Datapersis

로드 밸런싱이 세션 관리에 어떤 영향을 미치는지 설명하고 해결 방법을 설명하십시오.로드 밸런싱이 세션 관리에 어떤 영향을 미치는지 설명하고 해결 방법을 설명하십시오.Apr 29, 2025 am 12:42 AM

로드 밸런싱은 세션 관리에 영향을 미치지 만 세션 복제, 세션 끈적임 및 중앙 집중식 세션 스토리지로 해결할 수 있습니다. 1. 세션 복제 복사 서버 간의 세션 데이터. 2. 세션 끈은 사용자 요청을 동일한 서버로 안내합니다. 3. 중앙 집중식 세션 스토리지는 Redis와 같은 독립 서버를 사용하여 세션 데이터를 저장하여 데이터 공유를 보장합니다.

세션 잠금의 개념을 설명하십시오.세션 잠금의 개념을 설명하십시오.Apr 29, 2025 am 12:39 AM

SessionLockingIsateChniqueSureDureauser의 SessionLockingSsessionRemainSexclusivetoOneuseratatime.itiscrucialforpreptingdatacorruptionandsecurityBreachesInmulti-userApplications.sessionLockingSogingSompletEdusingserVerver-sidelockingMegynisms, unrasprantlockinj

PHP 세션에 대한 대안이 있습니까?PHP 세션에 대한 대안이 있습니까?Apr 29, 2025 am 12:36 AM

PHP 세션의 대안에는 쿠키, 토큰 기반 인증, 데이터베이스 기반 세션 및 Redis/Memcached가 포함됩니다. 1. Cookies는 클라이언트에 데이터를 저장하여 세션을 관리합니다. 이는 단순하지만 보안이 적습니다. 2. Token 기반 인증은 토큰을 사용하여 사용자를 확인합니다. 이는 매우 안전하지만 추가 논리가 필요합니다. 3. Database 기반 세션은 데이터베이스에 데이터를 저장하여 확장 성이 좋지만 성능에 영향을 줄 수 있습니다. 4. Redis/Memcached는 분산 캐시를 사용하여 성능 및 확장 성을 향상하지만 추가 일치가 필요합니다.

PHP의 맥락에서 '세션 납치'라는 용어를 정의하십시오.PHP의 맥락에서 '세션 납치'라는 용어를 정의하십시오.Apr 29, 2025 am 12:33 AM

SessionHijacking은 사용자의 SessionID를 얻음으로써 사용자를 가장하는 공격자를 말합니다. 예방 방법은 다음과 같습니다. 1) HTTPS를 사용한 의사 소통 암호화; 2) SessionID의 출처를 확인; 3) 보안 세션 생성 알고리즘 사용; 4) 정기적으로 SessionID를 업데이트합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

맨티스BT

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

ZendStudio 13.5.1 맥

ZendStudio 13.5.1 맥

강력한 PHP 통합 개발 환경