> 백엔드 개발 > PHP 튜토리얼 > 각 쿼리에 대한 최대 XOR

각 쿼리에 대한 최대 XOR

Mary-Kate Olsen
풀어 주다: 2024-11-10 17:41:02
원래의
348명이 탐색했습니다.

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

<!--?php

/**

 * @param Integer[] $nums

 * @param Integer $maximumBit

 * @return Integer[]

 */

function getMaximumXor($nums, $maximumBit) {

    ...

    ...

    ...

    /**

     * go to ./solution.php

     */

}

 

// Example usage:

$nums = [0,1,1,3];

$maximumBit = 2;

print_r(getMaximumXor($nums, $maximumBit));  // Output should be [0, 3, 2, 3]

?-->

 

 

 

 

<h3>

   

   

  설명:

</h3>

 

<ol>

<li>

<p><strong>maxNum 계산</strong>:</p>

 

<ul>

<li>

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

</ul>

</li>

<li>

<p><strong>초기 XOR 계산</strong>:</p>

 

<ul>

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

</ul>

</li>

<li>

<p><strong>역방향 반복</strong>:</p>

 

<ul>

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

 

<ul>

<li>

currentXOR ^ maxNum은 현재 상태에 대한 최대 k를 제공합니다.</li>

<li>답변에 k를 추가하세요.</li>

</ul>

</li>

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

</ul>

</li>

<li>

<p><strong>답변 반환</strong>:</p>

 

<ul>

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

</ul>

</li>

</ol>

 

<h3>

   

   

  복잡성 분석

</h3>

 

<ul>

<li>

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

<li>

<strong>공간 복잡도</strong>: <em><strong>O(n)</strong></em>, 답변 저장용.</li>

</ul>

 

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

 

<p><strong>연락처 링크</strong></p>

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

 

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

 

<ul>

<li><strong>링크드인</strong></li>

<li><strong>깃허브</strong></li>

</ul>

 

 

           

 

             

   

 

             

         

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

원천:dev.to
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿