C++の配列内の2つの数値の最大XOR

空でない数値の配列a0、a1、a2、…、an-1があるとします。ここで、0≤ai<231です。aiの最大の結果を見つける必要があります。 XOR aj、ここで0≤i、j

これを解決するには、次の手順に従います-

• insertNode（）を定義します。これにはvalとheadが必要です

• curr：=ヘッド

• 31から0の範囲のiの場合

  • ビット：=val /（2 ^ i）AND 1

  • currのchild[bit]がnullの場合、currのchild [bit]：=new node

  • curr：=currの子[ビット]

• find（）メソッドを定義します。これは、入力としてvalとheadを取ります

• curr：=ヘッド、ans：=0

• 31から0の範囲のiの場合

  • ビット：=val /（2 ^ i）AND 1

  • currのchild[bit]がnullの場合、ans：=ans OR（2 ^ 1）/ p>

  • curr：=currの子[ビット]

• ansを返す

• メインの方法から、次のようにします-

• ans：=0

• n：=numsのサイズ

• ヘッド：=新しいノード

• 0からn– 1の範囲のiの場合、insertNode（nums [i]、head）

• 0からn– 1の範囲のiの場合、ans：=ansの最大値と検索（nums [i]、head）

• ansを返す

例（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]

28