C++의 배열에서 두 숫자의 최대 XOR

0 ≤ ai <231인 숫자 a0, a1, a2, … , an-1의 비어 있지 않은 배열이 있다고 가정합니다. ai의 최대 결과를 찾아야 합니다. XOR aj, 여기서 0 ≤ i, j

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

insertNode()를 정의하면 val과 head가 필요합니다.
커 :=머리
31에서 0 사이의 i에 대해
- 비트 :=val / (2^i) AND 1
- curr의 자식[비트]가 null이면 curr의 자식[비트]:=새 노드
- curr :=curr의 자식[비트]
find() 메서드를 정의합니다. 이것은 val과 head를 입력으로 사용합니다.
curr :=머리, ans :=0
31에서 0 사이의 i에 대해
- 비트 :=val / (2^i) AND 1
- curr의 자식[비트]가 null이면 ans :=ans OR (2^1)/p>
- curr :=curr의 자식[비트]
반환
기본 방법에서 다음을 수행하십시오 -
답변 :=0
n :=숫자 크기
헤드 :=새 노드
0 ~ n – 1 범위의 i에 대해 insertNode(nums[i], head)
for i in range 0 to n – 1, ans :=최대 ans 및 find (nums[i], head)
반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
struct Node{
   Node* child[2];
   Node(){
      child[1] = child[0] = NULL;
   }
};
class Solution {
   public:
   void insertNode(int val, Node* head){
      Node* curr = head;
      for(int i = 31; i>= 0; i--){
         int bit = (val >> i) & 1;
         if(!curr->child[bit]){
            curr->child[bit] = new Node();
         }
         curr = curr->child[bit];
      }
   }
   int find(int val, Node* head){
      Node* curr = head;
      int ans = 0;
      for(int i = 31; i>= 0; i--){
         int bit = (val >> i) & 1;
         if(curr->child[!bit]){
            ans |= (1 << i);
            curr = curr->child[!bit];
         } else {
            curr = curr->child[bit];
         }
      }
      return ans;
   }
   int findMaximumXOR(vector<int>& nums) {
      int ans = 0;
      int n = nums.size();
      Node* head = new Node();
      for(int i = 0; i < n; i++){
         insertNode(nums[i], head);
      }
      for(int i = 0; i < n; i++){
         ans = max(ans, find(nums[i], head));
      }
      return ans;
   }
};
main(){
   vector<int> v = {3,10,5,25,2,8};
   Solution ob;
   cout << (ob.findMaximumXOR(v));
}

입력

[3,10,5,25,2,8]

C++의 배열에서 두 숫자의 최대 XOR

예시(C++)

입력

출력