>  기사  >  백엔드 개발  >  각 쿼리에 대한 최대 XOR

각 쿼리에 대한 최대 XOR

Mary-Kate Olsen
Mary-Kate Olsen원래의
2024-11-10 17:41:02264검색

Maximum XOR for Each Query

1829년. 각 쿼리에 대한 최대 XOR

난이도:

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

음이 아닌 정수 n개로 구성된 정렬된 배열 수와 정수 maximumBit가 제공됩니다. 다음 쿼리를 n 수행하려고 합니다:

  • 음이 아닌 정수 k < 2maximumBit nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k가 최대화됩니다. k는 i번째 쿼리
  • 에 대한 답입니다.
  • 현재 배열 nums에서 마지막 요소를 제거합니다.

배열 답변을 반환합니다. 여기서 답변[i]는 i번째 쿼리에 대한 답변입니다.

예 1:

  • 입력: nums = [0,1,1,3], maximumBit = 2
  • 출력: [0,3,2,3]
  • 설명: 쿼리에 대한 답변은 다음과 같습니다.
    • 1번째번째 쿼리: nums = [0,1,1,3], k = 0 이후 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
    • 2nd 쿼리: nums = [0,1,1], k = 3 이후 0 XOR 1 XOR 1 XOR 3 = 3.
    • 3rd 쿼리: nums = [0,1], k = 2 이후 0 XOR 1 XOR 2 = 3.
    • 4번째 쿼리: nums = [0], k = 3 이후 0 XOR 3 = 3.

예 2:

  • 입력: nums = [2,3,4,7], maximumBit = 3
  • 출력: [5,2,6,5]
  • 설명: 쿼리에 대한 답변은 다음과 같습니다.
    • 1번째번째 쿼리: nums = [2,3,4,7], k = 5 이후 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
    • 2nd 쿼리: nums = [2,3,4], k = 2 이후 2 XOR 3 XOR 4 XOR 2 = 7.
    • 3rd 쿼리: nums = [2,3], k = 6 이후 2 XOR 3 XOR 6 = 7.
    • 4번째 쿼리: nums = [2], k = 5(2 XOR 5 = 7이므로).

예 3:

  • 입력: nums = [0,1,2,2,5,7], maximumBit = 3
  • 출력: [4,3,6,4,6,7]

제약조건:

  • nums.length == n
  • 1 <= n <= 105
  • 1 <= maximumBit <= 20
  • 0 <= 숫자[i] < 2최대비트
  • nums​​​는 오름차순
  • 으로 정렬됩니다.

힌트:

  1. 가능한 최대 XOR 결과는 항상 2(maximumBit) - 1입니다.
  2. 접두사에 대한 대답은 해당 접두사를 2(maximumBit)-1과 XOR한 XOR입니다.

해결책:

배열에 있는 요소의 XOR을 효율적으로 계산하고 k가 2^maximumBit보다 작도록 k 값을 사용하여 결과를 최대화해야 합니다. 이 문제를 해결하는 방법은 다음과 같습니다.

관찰 및 접근 방식

  1. XOR 최대화:
    maximumBit 비트에 대한 접두어 합계와 XOR할 수 있는 최대 수는 ( 2^{text{maximumBit}} - 1 )입니다. 이는 모두 1인 개수(예: 이진수로 111...1)를 XOR하면 항상 결과가 최대화되기 때문입니다.

  2. 접두사 XOR 계산:
    각 쿼리에 대해 XOR을 다시 계산하는 대신 전체 배열에 대해 누적 XOR을 유지할 수 있습니다. XOR에는 A XOR B XOR B = A라는 속성이 있으므로 배열의 마지막 요소를 제거하려면 누적 XOR에서 해당 요소를 XOR하면 됩니다.

  3. 알고리즘:

    • 처음에는 nums에 있는 모든 요소의 XOR을 계산합니다. 이것을 currentXOR이라고 부르자.
    • 각 검색어에 대해(마지막부터 처음까지):
      • maxNum = 2^maximumBit - 1인 maxNum과 currentXOR을 XOR하여 해당 쿼리에 대한 k의 최적 값을 계산합니다.
      • 결과 목록에 k를 추가하세요.
      • currentXOR에서 XOR을 수행하여 nums의 마지막 요소를 제거합니다.
    • 결과 목록에는 역순으로 답변이 포함되므로 마지막에 역순으로 작성하세요.

PHP에서 이 솔루션을 구현해 보겠습니다: 1829. 각 쿼리에 대한 최대 XOR






설명:

  1. maxNum 계산:

    • maxNum은 2^maximumBit - 1로 계산됩니다. 이는 지정된 비트 길이에 대해 이진수로 모두 1이 포함된 숫자입니다.
  2. 초기 XOR 계산:

    • nums의 모든 요소를 ​​XOR하여 누적 XOR(currentXOR)을 얻습니다. 이는 배열에 있는 모든 숫자의 XOR을 나타냅니다.
  3. 역방향 반복:

    • nums의 마지막 요소부터 시작하여 각 단계의 최대 XOR을 계산합니다.
      • currentXOR ^ maxNum은 현재 상태에 대한 최대 k를 제공합니다.
      • 답변에 k를 추가하세요.
    • 그런 다음 currentXOR로 nums의 마지막 요소를 XOR하여 다음 반복을 위한 XOR 합계에서 해당 요소를 "제거"합니다.
  4. 답변 반환:

    • 목록을 역순으로 처리했기 때문에 답변에는 값이 역순으로 포함되므로 최종 목록은 이미 요구 사항에 맞게 올바르게 정렬되었습니다.

복잡성 분석

  • 시간 복잡도: O(n), O(n)에서 초기 XOR을 계산하고 각 쿼리는 일정한 시간에 처리됩니다.
  • 공간 복잡도: O(n), 답변 저장용.

이 코드는 효율적이며 제약 조건의 상한을 잘 처리해야 합니다.

연락처 링크

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

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

  • 링크드인
  • 깃허브

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

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