資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究給定節點在 C++ 子樹中所有節點的 XOR
對於這個問題，我們給定了一棵 n 樹，其中一些查詢是樹的節點。我們的任務是列印由給定節點形成的子樹的所有節點的 XOR。
我們舉個例子來理解這個問題，
查詢 − {1, 6, 5}
輸出 −
0 0 5
說明 −
1^6^3^2^4^7^5 6^2^4 5
為了解決這個問題，我們將透過一次遍歷樹來計算子樹所有節點的異或，並將其儲存起來。現在，我們將計算所有子樹的子節點的所有節點的異或，然後為所有給定的子樹計算。儲存結果可以節省時間。
示例
展示我們解決方案實現的程式，
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > graph;
vector<int> values, xorValues;
int computeXorValues(int i, int prev){
int x = values[i];
for (int j = 0; j < graph[i].size(); j++)
if (graph[i][j] != prev) {
x ^= computeXorValues(graph[i][j], i);
}
xorValues[i] = x;
return x;
}
int solveQuerry(int u){
return xorValues[u];
}
int main(){
int n = 7;
graph.resize(n);
xorValues.resize(n);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[1].push_back(4);
graph[2].push_back(5);
graph[2].push_back(6);
values.push_back(1);
values.push_back(2);
values.push_back(3);
values.push_back(4);
values.push_back(5);
values.push_back(6);
values.push_back(7);
computeXorValues(0, -1);
int queries[] = { 0, 2, 4, 6 };
int q = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < q; i++)
cout<<"Solution for querry "<<(i+1)<<": "<<solveQuerry(queries[i])<<endl;
return 0;
}輸出
Solution for querry 1: 0 Solution for querry 2: 2 Solution for querry 3: 5 Solution for querry 4: 7
更新時間：20-Apr-2020
245 次瀏覽
廣告