각 쿼리에 대한 최대 XOR

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

난이도:중

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

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

• 음이 아닌 정수 k < 2^maximumBit 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.
  • 2^nd 쿼리: nums = [0,1,1], k = 3 이후 0 XOR 1 XOR 1 XOR 3 = 3.
  • 3^rd 쿼리: 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.
  • 2^nd 쿼리: nums = [2,3,4], k = 2 이후 2 XOR 3 XOR 4 XOR 2 = 7.
  • 3^rd 쿼리: 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 <= 10⁵
• 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

  
  
  설명:




maxNum 계산:



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



초기 XOR 계산:


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



역방향 반복:


nums의 마지막 요소부터 시작하여 각 단계의 최대 XOR을 계산합니다.



currentXOR ^ maxNum은 현재 상태에 대한 최대 k를 제공합니다.
답변에 k를 추가하세요.


그런 다음 currentXOR로 nums의 마지막 요소를 XOR하여 다음 반복을 위한 XOR 합계에서 해당 요소를 "제거"합니다.



답변 반환:


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





  
  
  복잡성 분석




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

공간 복잡도: O(n), 답변 저장용.


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

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

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


링크드인
깃허브



          

            
  

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