ค้นหาคู่ของแถวในเมทริกซ์ไบนารีที่มีความแตกต่างบิตสูงสุดใน C++

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องหาคู่ของแถวในเมทริกซ์ที่กำหนดซึ่งมีความแตกต่างบิตสูงสุด

ดังนั้น หากอินพุตเป็นเหมือนเมทริกซ์ ผลลัพธ์จะเป็น [2,3] เนื่องจากความแตกต่างบิตระหว่างแถวที่ 2 และแถวที่ 3 คือ 4 ซึ่งเป็นค่าสูงสุด

• เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดโครงสร้าง Trie ที่มีค่าและลูกสองคน

• กำหนดฟังก์ชัน get_max_bit_diff() ซึ่งจะทำการรูทของ trie, matrix, n, row_index,

• temp :=root, นับ :=0

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • ถ้า child[ matrix[row_index, i] ] ของ temp ไม่ใช่ NULL ดังนั้น -

    • temp :=child[ matrix[row_index, i] ] ของอุณหภูมิ

  • มิฉะนั้นเมื่อ child[1 - matrix[row_index, i]] ของ temp ไม่ใช่ NULL ดังนั้น -

    • temp :=child[1- matrix[row_index, i]] ของอุณหภูมิ

    • (เพิ่มจำนวนขึ้น 1)

• leaf_index :=ใบไม้แห่งอุณหภูมิ

• temp_count :=0, temp :=root

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • ถ้า child[ 1 - matrix[row_index, i] ] ของ temp ไม่ใช่ NULL ดังนั้น -

    • temp :=child[ 1- matrix[row_index, i] ] ของอุณหภูมิ

    • (เพิ่ม temp_count ขึ้น 1)

  • มิฉะนั้นเมื่อ child[ matrix[row_index, i] ] ของ temp ไม่ใช่ NULL ดังนั้น -

    • temp :=child[ matrix[row_index, i] ] ของอุณหภูมิ

• P =ถ้า temp_count> นับ ให้สร้างคู่โดยใช้ (temp_count, leaf of temp) หรือสร้างคู่โดยใช้ (count, leaf_index)

• กลับ P

• จากวิธีหลัก ให้ทำดังนี้ −

• root =TrieNode ใหม่

• แทรกแถวที่ 0 ลงในรูท

• max_bit_diff :=-inf

• กำหนดหนึ่งคู่ 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)

  • แทรกแถว ith ลงในรูท

• แสดงคู่ pr

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#includeใช้เนมสเปซ std;const int MAX =100;คลาส TrieNode { สาธารณะ:int leaf; TrieNode *ลูก[2]; TrieNode () { ใบไม้ =0; เด็ก[0] =เด็ก[1] =NULL; }};การแทรกเป็นโมฆะ (TrieNode *root, int matrix[][MAX], int n, int row_index){ TrieNode * temp =root; สำหรับ (int i=0; ichild[ matrix[row_index][i] ] ==NULL) temp->child[ matrix[row_index][i] ] =new TrieNode( ); temp =temp->child[ เมทริกซ์[row_index][i] ]; } temp->leaf =row_index +1; } คู่ get_max_bit_diff (TrieNode * root, int matrix [][MAX], int n, int row_index) { TrieNode * temp =root; จำนวน int =0; สำหรับ (int i=0; i child[ matrix[row_index][i] ] !=NULL) temp =temp->child[ matrix[row_index][i] ]; อย่างอื่น if (temp->child[1 - matrix[row_index][i]] !=NULL) { temp =temp->child[1- matrix[row_index][i]]; นับ++; } } int leaf_index =temp->leaf; int temp_count =0; อุณหภูมิ =รูท; สำหรับ (int i=0; i child[ 1 - matrix[row_index][i] ] !=NULL) { temp =temp->child[ 1- matrix[row_index][] ฉัน] ]; temp_count++; } อื่น if (temp->child[ matrix[row_index][i] ] !=NULL) temp =temp->child[ matrix[row_index][i] ]; } คู่  P =temp_count> นับ ? make_pair(temp_count, temp->leaf):make_pair(นับ, leaf_index); return P;} เป็นโมฆะ get_max_diff( int mat[][MAX], int n, int m) { TrieNode * root =TrieNode ใหม่ (); แทรก(รูท, เสื่อ, ม., 0); int max_bit_diff =INT_MIN; คู่ pr, temp; สำหรับ (int i =1; i  
อินพุต
 <ก่อน>{{1 ,1 ,1 ,1 },{1, 0, 1 ,1},{0 ,1 ,0 ,0},{1 ,0,0 ,0}}, 4,4 
ผลลัพธ์
 
(2,3)