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

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

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

• ขั้นตอนการแก้:

• กำหนดโครงสร้าง Trie Node มี value และลูกสองตัว

• กำหนดฟังก์ชัน get_max_bit_diff() รับ root of trie, matrix, n, row_index

• temp := root, count := 0

• วนลูป i := 0 ถึง n-1:

  • ถ้า child[matrix[row_index][i]] ของ temp ไม่เป็น NULL: temp = child[...]
  • ถ้า child[1 - matrix[row_index][i]] ของ temp ไม่เป็น NULL: temp = child[...], count++

• leaf_index := leaf ของ temp

• temp_count := 0, temp := root

• วนลูป i := 0 ถึง n-1 อีกครั้ง เพื่อหาค่าตรงข้าม:

  • ถ้า child[1 - matrix[row_index][i]] ไม่เป็น NULL: temp = child[...], temp_count++
  • ถ้า child[matrix[row_index][i]] ไม่เป็น NULL: temp = child[...]

• P = ถ้า temp_count > count คืนคู่ (temp_count, leaf ของ temp) ไม่งั้นคืน (count, leaf_index)

• คืนค่า P

• ใน main:

  • root = TrieNode ใหม่
  • insert แถว 0 เข้า root
  • max_bit_diff := -inf
  • วนลูป i := 1 ถึง n-1:
    • temp = get_max_bit_diff(root, mat, m, i)
    • ถ้า max_bit_diff < temp.first: อัปเดต max_bit_diff และ pr = (temp.second, i+1)
    • insert แถว i เข้า root

• แสดงคู่ 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)