C++で最大のビット差を持つバイナリ行列の行のペアを検索します

バイナリ行列があるとします。与えられた行列の中で、ビット差が最大の行のペアを見つける必要があります。

したがって、入力が行列のような場合、行2と行3のビット差が4であるため、出力は[2,3]になります。これは最大です。

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

• 値と2つの子を使用してTrie構造を定義します。

• 関数get_max_bit_diff（）を定義します。これは、trie、matrix、n、row_index、

  のルートを取ります。

• temp：=root、count：=0

• 初期化i：=0の場合、i

  • tempのchild[matrix[row_index、i]]がNULLでない場合、-

    • temp：=tempの子[matrix[row_index、i]]

  • それ以外の場合、tempのchild [1-matrix [row_index、i]]がNULLでない場合、-

    • temp：=tempの子[1-matrix[row_index、i]]

    • （カウントを1つ増やします）

• leaf_index：=一時的な葉

• temp_count：=0、temp：=root

• 初期化i：=0の場合、i

  • tempのchild[1-matrix[row_index、i]]がNULLでない場合、-

    • temp：=tempの子[1-matrix[row_index、i]]

    • （temp_countを1増やします）

  • それ以外の場合、tempのchild [matrix [row_index、i]]がNULLでない場合、-

    • temp：=tempの子[matrix[row_index、i]]

• P =temp_count> countの場合は、（temp_count、leaf of temp）を使用してペアを作成し、それ以外の場合は（count、leaf_index）を使用してペアを作成します

• Pを返す

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

• ルート=新しいTrieNode

• ルートに0行目を挿入

• max_bit_diff：=-inf

• 1つのペアprと別のペアtempを定義します

• 初期化i：=1の場合、i

  • temp：=get_max_bit_diff（root、mat、m、i）

  • max_bit_diff <最初のtempの場合、次に-

    • max_bit_diff：=temp.first

    • pr：=（temp.second、i + 1）を使用してペアを作成します

  • i番目の行をルートに挿入します

• ディスプレイペアpr

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
class TrieNode {
   public:
   int leaf;
   TrieNode *child[2];
   TrieNode(){
      leaf = 0;
      child[0] = child[1] = NULL;
   }
};
void insert(TrieNode *root, int matrix[][MAX], int n, int row_index){
   TrieNode * temp = root;
   for (int i=0; i<n; i++) {
      if(temp->child[ matrix[row_index][i] ] == NULL)
         temp->child[ matrix[row_index][i] ] = new TrieNode();
         temp = temp->child[ matrix[row_index][i] ];
      }
      temp->leaf = row_index +1 ;
   }
   pair<int, int>get_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) {
      TrieNode * temp = root;
      int count = 0;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
         else if (temp->child[1 - matrix[row_index][i]] != NULL) {
            temp = temp->child[1- matrix[row_index][i]];
            count++;
         }
      }
      int leaf_index = temp->leaf;
      int temp_count = 0 ;
      temp = root;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ 1 - matrix[row_index][i] ] !=NULL) {
            temp = temp->child[ 1- matrix[row_index][i] ];
            temp_count++;
         }
         else if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
      }
      pair <int ,int> P = temp_count > count ? make_pair(temp_count, temp->leaf): make_pair(count, leaf_index);
      return P;
}
void get_max_diff( int mat[][MAX], int n, int m) {
   TrieNode * root = new TrieNode();
   insert(root, mat, m, 0);
   int max_bit_diff = INT_MIN;
   pair<int ,int> pr, temp ;
   for (int i = 1 ; i < n; i++) {
      temp = get_max_bit_diff(root, mat, m ,i);
      if (max_bit_diff < temp.first ) {
         max_bit_diff = temp.first;
         pr = make_pair( temp.second, i+1);
      }
      insert(root, mat, m, i );
   }
   cout << "(" << pr.first <<", "<< pr.second << ")";
}
int main() {
   int mat[][MAX] = {
      {1 ,1 ,1 ,1 },
      {1, 0, 1 ,1},
      {0 ,1 ,0 ,0},
      {1 ,0 ,0 ,0}
   };
   get_max_diff(mat, 4, 4) ;
}

入力

{{1 ,1 ,1 ,1 },
{1, 0, 1 ,1},
{0 ,1 ,0 ,0},
{1 ,0 ,0 ,0}}, 4,4

出力

(2,3)