資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學統計從根節點到路徑上所有邊的按位異或結果等於 K 的節點數
統計從根節點到路徑上所有邊的按位異或結果等於 K 的節點數。我們嘗試確定給定樹中節點的數量，其中從根節點到該節點路徑上所有邊的按位異或結果等於給定值 K。這就是所謂的統計從根節點到路徑上所有邊的按位異或結果等於 K 的節點數問題。這個有趣的點在於有效地計算從根節點到節點的每條路徑上的異或值，同時遍歷樹。在本文中，我們將探討解決此問題的幾種方法，包括 Trie 資料結構、字首異或陣列和深度優先搜尋。每種方法都提供了對有效統計此類節點的不同見解，並提供瞭解決涉及樹的相關問題的有用技術。
使用的方法
深度優先搜尋 (DFS)
字首異或陣列
Trie 資料結構
深度優先搜尋 (DFS)
使用這種方法，我們使用深度優先搜尋遍歷樹，同時跟蹤從根節點到當前節點的所有邊的異或值。在雜湊對映中保持遍歷過程中遇到的每個異或值的計數。在每個節點處，我們嘗試檢查雜湊對映是否包含當前路徑的異或值與 K 的異或結果。如果是，則增加計數，因為路徑上存在節點，其與當前節點的異或值產生值 K。然後繼續深度優先搜尋遍歷以檢查其他路徑。
演算法
從頭開始設定一個雜湊對映來跟蹤在 DFS 遍歷期間看到的異或值的計數。
使用深度優先搜尋遍歷樹，並記下從根節點到當前節點的每條邊的異或值。
檢查每個節點，檢視雜湊對映是否包含當前路徑的異或值與 K 的異或結果。如果是，則相應地增加計數。
遞迴地探索當前節點的每個子節點，根據需要更改當前路徑的異或值。
遍歷完成後，計數將反映從根節點到路徑上所有邊的按位異或結果等於 K 的節點數。
時間複雜度為 O(N)，其中 N 是樹中節點的數量。
示例
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<int, vector<int>> graph;
unordered_map<int, int> xorCount;
void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfs(int node, int parent, int xorValue, int k) {
xorValue ^= node;
if (xorCount.find(xorValue ^ k) != xorCount.end())
xorCount[xorValue ^ k]++;
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, xorValue, k);
}
}
}
int main() {
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
int k = 3;
xorCount[0] = 1;
dfs(1, -1, 0, k);
cout << "Count of nodes whose XOR of all edges leading to root equals " << k << ": ";
cout << xorCount[k] << endl;
return 0;
}
輸出
Count of nodes whose XOR of all edges leading to root equals 3: 0
滑動視窗法
在這種方法中，使用字首異或陣列快速計算從根節點到特定節點的每條路徑上所有邊的異或值。當我們向下遍歷樹時，我們使用深度優先搜尋方法計算字首異或值。對於每個節點，我們檢查字首異或陣列是否包含當前路徑的異或值與 K 的異或結果。如果是，則相應地增加計數。
演算法
從頭開始建立一個字首異或陣列，並用連線每個節點到根節點的所有邊的異或值填充它。
使用深度優先搜尋遍歷，向下遍歷樹，同時更新字首異或陣列。
檢查每個節點，檢視字首異或陣列是否包含當前路徑的異或值與 K 的異或結果。如果是，則相應地增加計數。
透過遞迴探索當前節點的每個子節點來更新字首異或陣列。
遍歷完成後，計數將反映從根節點到路徑上所有邊的按位異或結果等於 K 的節點數。時間複雜度為 O(N)，其中 N 是樹中節點的數量。
示例
#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, int parent, const vector<vector<int>>& graph,
vector<int>& prefixXOR, int currentXOR) {
prefixXOR[node] = currentXOR;
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, graph, prefixXOR, currentXOR ^ child);
}
}
}
void countXORPaths(int node, int parent, const vector<vector<int>>& graph, const vector<int>& prefixXOR, int K, int& count) {
if (prefixXOR[node] == K)
count++;
for (int child : graph[node]) {
if (child != parent) {
countXORPaths(child, node, graph, prefixXOR, K, count);
}
}
}
int main() {
int n = 6;
int root = 0;
vector<vector<int>> graph(n);
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0, 5};
vector<int> prefixXOR(n, 0);
dfs(root, -1, graph, prefixXOR, 0);
int K = 2;
int count = 0;
countXORPaths(root, -1, graph, prefixXOR, K, count);
cout << count << endl;
return 0;
}
輸出
2
Trie 資料結構
在這種方法中，遍歷過程中遇到的字首異或值儲存在 Trie 資料結構中。對於每個節點，我們檢查 Trie 是否包含當前路徑的異或值與 K 的異或結果。如果是，則相應地增加計數。Trie 有效地處理異或運算，並允許我們快速查詢所需的異或值。
演算法
建立一個新的空 Trie 資料結構例項來儲存遍歷期間遇到的任何字首異或值。
執行樹的深度優先搜尋遍歷，當我們向下遍歷樹時，使用字首異或值更新 Trie。
檢查每個節點，檢視 Trie 是否包含當前路徑的異或值與 K 的異或結果。如果是，則相應地增加計數。
遞迴地探索當前節點的每個子節點，同時更新 Trie。
遍歷完成後，計數將反映從根節點到路徑上所有邊的按位異或結果等於 K 的節點數。
時間複雜度為 O(N)，其中 N 是樹中節點的數量。
示例
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TrieNode {
unordered_map<int, TrieNode*> children;
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode* curr = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (curr->children.find(bit) == curr->children.end())
curr->children[bit] = new TrieNode();
curr = curr->children[bit];
}
}
bool search(int num) {
TrieNode* curr = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (curr->children.find(1 - bit) != curr->children.end())
curr = curr->children[1 - bit];
else
curr = curr->children[bit];
}
return true;
}
private:
TrieNode* root;
};
struct TreeNode {
int val;
vector<TreeNode*> children;
};
int countPrefixXOR(TreeNode* root, Trie& trie, int curXOR, int targetXOR) {
curXOR ^= root->val;
trie.insert(curXOR);
int count = trie.search(curXOR ^ targetXOR);
for (TreeNode* child : root->children) {
count += countPrefixXOR(child, trie, curXOR, targetXOR);
}
return count;
}
int main() {
// Sample Tree Creation
TreeNode* root = new TreeNode();
root->val = 1;
TreeNode* node1 = new TreeNode();
node1->val = 0;
root->children.push_back(node1);
TreeNode* node2 = new TreeNode();
node2->val = 1;
root->children.push_back(node2);
TreeNode* node3 = new TreeNode();
node3->val = 0;
node1->children.push_back(node3);
TreeNode* node4 = new TreeNode();
node4->val = 1;
node1->children.push_back(node4);
TreeNode* node5 = new TreeNode();
node5->val = 1;
node2->children.push_back(node5);
int K = 5;
Trie trie;
int result = countPrefixXOR(root, trie, 0, K);
cout << "The count of nodes with prefix XOR equal to K is: " <<
result << endl;
return 0;
}
輸出
The count of nodes with prefix XOR equal to K is: 6
結論
所有三種方法都能有效地統計從根節點到路徑上所有邊的按位異或結果等於或大於 K 的節點數。選擇哪種方法取決於特定的需求、可用的資料結構以及樹的大小。DFS 方法簡單易用，但對於大型樹可能不是最佳選擇。對於效能關鍵型應用程式，字首異或陣列和 Trie 方法更可取，因為它們對於大型樹更有效，並提供恆定時間的異或運算。
瀏覽量：134
