資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在C++中查詢二進位制矩陣中位差最大的兩行
假設我們有一個二進位制矩陣；我們必須找到該矩陣中位差最大的兩行。
因此，如果輸入類似於矩陣，則輸出將為 [2,3]，因為第 2 行和第 3 行之間的位差為 4，這是最大的。
為了解決這個問題，我們將遵循以下步驟：
定義 Trie 結構，包含值和兩個子節點。
定義一個函式 `get_max_bit_diff()`，它將接收 Trie 的根節點、矩陣、n（列數）、行索引作為引數。
temp := 根節點, count := 0
for i := 0 to n-1 do −
如果 temp 的子節點[matrix[row_index, i]] 不為空，則：
temp := temp 的子節點[matrix[row_index, i]]
否則，如果 temp 的子節點[1 - matrix[row_index, i]] 不為空，則：
temp := temp 的子節點[1 - matrix[row_index, i]]
(count 加 1)
leaf_index := temp 的葉子節點索引
temp_count := 0, temp := 根節點
for i := 0 to n-1 do −
如果 temp 的子節點[1 - matrix[row_index, i]] 不為空，則：
temp := temp 的子節點[1 - matrix[row_index, i]]
(temp_count 加 1)
否則，如果 temp 的子節點[matrix[row_index, i]] 不為空，則：
temp := temp 的子節點[matrix[row_index, i]]
P = if temp_count > count then 建立一個包含 (temp_count, temp 的葉子節點索引) 的對，否則建立一個包含 (count, leaf_index) 的對
返回 P
在主方法中，執行以下操作：
root = 一個新的 TrieNode
將第 0 行插入 root
max_bit_diff := -inf
定義一個對 pr 和另一個對 temp
for i := 1 to n-1 do −
temp := get_max_bit_diff(root, mat, m, i)
如果 max_bit_diff < temp.first，則：
max_bit_diff := temp.first
pr := 建立一個包含 (temp.second, i + 1) 的對
將第 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)
121 次檢視
