PAT甲級的題目有關(guān)于樹的題目，1053参袱，1086电谣，1090，1102抹蚀，1106剿牺，1115，1119环壤，1038晒来，1110，1020郑现，1043
A1053
這題目比較簡單湃崩，給定一棵樹，給定一個數(shù)字接箫，要你找到所有和等于給定數(shù)字的路徑攒读。這個題目的樹沒有給出是二叉樹，自然不能按照原來二叉樹的方法來構(gòu)建了辛友。其實就是BFS薄扁，用DFS也是可以的，不過考慮到DFS還要新開一個數(shù)組來存儲路徑，還是使用BFS邓梅。
首先是樹的結(jié)構(gòu)脱盲，只需要在原來二叉樹的基礎(chǔ)上修改一下就好了。
typedef struct treeNode {
int val;
int weight;
vector<struct treeNode *> generator;
int parent = -1;
} *TreeNode, treeNode;
把原來的左右子樹修改成一個vector存儲即可日缨。樹的結(jié)構(gòu)中新添加了一個parent钱反，是用于找到根節(jié)點，因為題目給出的樹是一個列表匣距，接著是樹的父節(jié)點诈铛，不添加parent找不到父節(jié)點。如果parent是-1那么就是根節(jié)點了墨礁。
TreeNode createTree(int n, TreeNode *array, int allNodes) {
for (int i = 0; i < n; ++i) {
int index;
int num;
cin >> index >> num;
index_map[index] = true;
for (int j = 0; j < num; ++j) {
int next;
cin >> next;
array[next]->parent = index;
array[index]->generator.push_back(array[next]);
}
sort(array[index]->generator.rbegin(), array[index]->generator.rend(), cmp);
}
for (int k = 0; k < allNodes; ++k) {
if (array[k]->parent == -1) {
return array[k];
}
}
return nullptr;
}
創(chuàng)建樹的過程，注意后面有一個排序操作耳峦，題目的輸出要求按照次序輸出恩静。然后就是BFS操作了。
void findWeights(TreeNode root, int sum, vector<int> weightsAdd, int equalWeights) {
if (sum > equalWeights) {
return;
} else if (sum < equalWeights) {
sum += root->weight;
weightsAdd.push_back(root->weight);
if (sum == equalWeights) {
if (!index_map[root->val]) {
weights_path.push_back(weightsAdd);
weightsAdd.clear();
}
return;
}
for (int i = 0; i < root->generator.size(); ++i) {
TreeNode current = root->generator[i];
findWeights(current, sum, weightsAdd, equalWeights);
}
}
}
BFS把weightsAdd當(dāng)成是一個拷貝過來的局部變量蹲坷，不需要回滾操作驶乾，比DFS簡單多了。然后就是輸出了循签，只需要注意最后不要空格就好级乐。
其實也可以用數(shù)組來完成，所占空間可能更小县匠。
1086
這個題目做了很久风科，要是在上機考試碰見這個題目應(yīng)該就只有10來分了。題目大意是給定一個入棧出棧的序列乞旦，這個出入棧完成后得到的出棧序列是中序遍歷的序列贼穆，要你求這棵樹的后續(xù)遍歷。我直接從序列入手兰粉，發(fā)現(xiàn)push操作就是：如果當(dāng)前節(jié)點有左子樹故痊，就插入左子樹，否則就插入右子樹玖姑；pop操作是回退到上一課樹愕秫，按照這個操作就可以創(chuàng)建出一棵樹，然后后續(xù)遍歷即可焰络。然而內(nèi)存爆炸了戴甩。
之前考408的時候遇到過這樣的操作，好像是天勤ds里面闪彼，中序遍歷如果使用棧來實現(xiàn)等恐，入棧順序就是前序遍歷次序。所以題目表面上是給了一個序列，實際上給了前序和中序遍歷课蔬，讓你求后續(xù)遍歷囱稽。這個就很簡單了。
TreeNode create(int preL, int preR, int inL, int inR, int *preOrder, int *inOrder) {
int rootNum = preOrder[preL];
TreeNode root = new treeNode;
root->val = rootNum;
if (preL == preR) {
root->val = rootNum;
root->leftChild = root->rightChild = nullptr;
return root;
}
if (preL > preR) {
return nullptr;
}
int mid = -1;
for (int i = inL; i <= inR; ++i) {
if (inOrder[i] == rootNum) {
mid = i;
break;
}
}
int leftNumber = mid - inL;
int rightNumber = inR - mid;
root->leftChild = create(preL + 1, preL + leftNumber, inL, mid - 1, preOrder, inOrder);
root->rightChild = create(preR - rightNumber + 1, preR, mid + 1, inR, preOrder, inOrder);
return root;
}
關(guān)鍵就是創(chuàng)建樹的操作二跋，天勤的代碼題出過這類战惊，主要就是前中序遍歷的邊界數(shù)對就行。
1090
這個題目一開始讀的沒太懂扎即，兩次都超了吞获，只有14分。一開始還以為最后要給出的是路徑上零售商的數(shù)量谚鄙，沒想到是路徑的個數(shù)各拷。
很明顯是BFS，和上上題一樣：
//typedef struct treeNode {
// int val;
// vector<struct treeNode *> children;
// int parent = -1;
//} *TreeNode, treeNode;
double maxPrice = -1;
int maxNumber = -1;
//void BFS(TreeNode root, double currentPrice, double r, vector<int> path) {
// if (root) {
// path.push_back(root->val);
// currentPrice = currentPrice * ((100 + r) / 100);
// if (maxPrice < currentPrice) {
// maxPrice = currentPrice;
// maxNumber = path.size();
// }
// for (int i = 0; i < root->children.size(); ++i) {
// BFS(root->children[i], currentPrice, r, path);
// }
// }
//}
建樹是不行的闷营，直接就內(nèi)存爆炸烤黍。如此那就直接用數(shù)組吧，于是想到從尾巴開始傻盟，然而題目有關(guān)鍵一句：It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.假設(shè)在供應(yīng)鏈上的每名成員都只有一個供應(yīng)者速蕊，除了根部的供應(yīng)者，沒有環(huán)娘赴，那么就不需要像圖一樣設(shè)置訪問標(biāo)記规哲。
// for (int j = 0; j < n; ++j) {
// if (!visited[j]) {
// int paths = 0;
// int fa = array[j];
// while (fa != -1) {
// visited[fa] = true;
// fa = array[fa];
// paths++;
// }
// maxNumber = ((maxNumber > paths) ? maxNumber : paths);
// }
// }
還是超時了，因為如果從底部開始诽表，會出現(xiàn)很多重復(fù)的道路唉锌，所以最好還是從底部開始訪問，我也是在這里看了別人題解之后才知道竿奏，原來輸出的最后一個數(shù)字應(yīng)該是路徑的個數(shù)糊秆，翻譯錯了。
vector<int> v[100010];
void bfs(int root, int depth) {
if (v[root].size() == 0) {
if (maxPrice < depth) {
maxPrice = depth;
maxNumber = 1;
} else if (maxPrice == depth) {
maxNumber++;
}
return;
}
for (int i = 0; i < v[root].size(); ++i) {
bfs(v[root][i], depth + 1);
}
}
用一個vector數(shù)組把所有兒子串起來议双，遍歷訪問即可痘番。
1102
輸入詳情：每一個輸入包含了一個測試樣例。對于每一個例子平痰，第一行給出一個正整數(shù)汞舱，也及是樹的總節(jié)點數(shù)，因此宗雇，節(jié)點編號從0到N-1昂芜，然后下面N行每一行對應(yīng)節(jié)點0到N-1，每一行給出左右子樹赔蒲。如果子樹不存在泌神，用-來代替良漱，每一對孩子用空格分離。
輸出詳情：對于每一個樣例欢际，第一行打印翻轉(zhuǎn)樹的層序遍歷序列母市，然后第二行打印翻轉(zhuǎn)樹的中序遍歷序列，用空格隔開损趋，最后不能有空格患久。
這個題目就非常簡單了，唯一的考點就是交換兩樹的左右子樹浑槽，直接后序遍歷交換就好了蒋失，釋放樹的內(nèi)存也是后序遍歷實現(xiàn)。
for (int i = 0; i < n; ++i) {
array[i].val = i;
string left, right;
cin >> left >> right;
if (left == "-") {
array[i].leftChild = nullptr;
} else {
array[i].leftChild = &array[string2Number(left)];
array[string2Number(left)].parent = i;
}
if (right == "-") {
array[i].rightChild = nullptr;
} else {
array[i].rightChild = &array[string2Number(right)];
array[string2Number(right)].parent = i;
}
}
創(chuàng)建樹和前面幾個題目一樣桐玻。
void postExchange(TreeNode root) {
if (root) {
postExchange(root->leftChild);
postExchange(root->rightChild);
TreeNode temp = root->leftChild;
root->leftChild = root->rightChild;
root->rightChild = temp;
}
}
1106
一條供應(yīng)鏈網(wǎng)絡(luò)由零售商篙挽，經(jīng)銷商，供應(yīng)商組成镊靴，每一總角色在這條網(wǎng)絡(luò)（產(chǎn)品從生產(chǎn)者到消費者）中都起到相應(yīng)的作用铣卡。從根節(jié)點的供應(yīng)者開始，每個人從供應(yīng)商以P的價格購買邑闲，以比P價格高上百分之r的價格賣給經(jīng)銷商或者是零售商。只有零售商才會面對客戶梧油，假設(shè)每一個成員只有一個提供者苫耸，而且沒有循環(huán)。
輸出詳情：每一個輸入包含一個測試樣例儡陨。對于每一個樣例褪子，第一行包含一個正整數(shù)，標(biāo)識供應(yīng)鏈中成員總數(shù)骗村，P標(biāo)識根供應(yīng)者的價格嫌褪，也就是初始價格。r是比率胚股，每經(jīng)過一個經(jīng)銷商或者是零售商價格需要提升r比率笼痛。接下來N行中，每一行描述的格式：K,ID,......琅拌。第i行中Ki表示總共有Ki個接受者缨伊，其實就是說第i號的提供者有這么多個接受者。中間空格隔開进宝。
輸出詳情：對于每一個測試樣例刻坊，打印出零售商的最低價格，也就是最后一個`葉子的最低價格党晋，精確到四位小數(shù)谭胚，有多少個零售商可以拿到最低價格徐块。
讀完題，一看就知道BFS灾而，和前面那道題沒有什么區(qū)別胡控。
void BFS(int root, int depth, treeNode *array) {
if (depth > minDepth && minNumber > 0) {
return;
}
if (array[root].childen.size() == 0) {
if (depth < minDepth) {
minDepth = depth;
minNumber = 1;
} else if (depth == minDepth) {
minNumber++;
}
return;
}
for (int i = 0; i < array[root].childen.size(); ++i) {
BFS(array[root].childen[i], depth + 1, array);
}
}
僅僅修改此處即可卵凑。不過值得注意的是贝淤，我一開始是創(chuàng)建了一顆樹，后來發(fā)現(xiàn)超時霞揉，我一開始還以為是遞歸調(diào)用超時轻庆，于是我添加了：
if (depth > minDepth && minNumber > 0) {
return;
}
如果已經(jīng)找到了一個更短的癣猾，那么如果還有，要么和其相同余爆，要么更短纷宇，所以如果還有比他長的直接去掉。但是加上后PAT評測的時間有減少蛾方，但是還是有兩個數(shù)據(jù)是段錯誤像捶，修改一下，把一些多余數(shù)據(jù)去掉就可以了桩砰。推測原因應(yīng)該是內(nèi)存超限了拓春。
1115
這個題目就不翻譯了，非常簡單亚隅，就要你找倒數(shù)第一和倒數(shù)第二層的節(jié)點數(shù)加起來硼莽。層序遍歷是最為適合的了，BFS也可以煮纵。關(guān)鍵有幾個地方懂鸵，構(gòu)建樹：
TreeNode insert(TreeNode root, int num) {
if (root) {
if (root->val < num) {
root->rightChild = insert(root->rightChild, num);
} else {
root->leftChild = insert(root->leftChild, num);
}
return root;
} else {
root = new treeNode;
root->val = num;
root->leftChild = root->rightChild = nullptr;
return root;
}
}
在樹的結(jié)構(gòu)中添加一個層次屬性，記錄屬于第幾層行疏。
void level(TreeNode root) {
fill(depth, depth + MAX, 0);
queue<TreeNode> Queue;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
depth[cur->depth]++;
maxDepth = ((maxDepth > cur->depth) ? maxDepth : cur->depth);
if (cur->leftChild) {
cur->leftChild->depth = cur->depth + 1;
Queue.push(cur->leftChild);
}
if (cur->rightChild) {
cur->rightChild->depth = cur->depth + 1;
Queue.push(cur->rightChild);
}
}
}
每一次取出節(jié)點的時候順便直接存進(jìn)數(shù)組里面計數(shù)匆光，免得害得遍歷一次數(shù)組。水題一道酿联。
1119
假設(shè)在二叉樹中所有的關(guān)鍵字都是互不相同的正整數(shù)终息。一顆獨一無二的二叉樹可以由一對后序和中序遍歷序列得到，或者是前序和中序得到贞让。但是采幌，如果只給了后續(xù)和前序遍歷，那么對應(yīng)的二叉樹并非是唯一的震桶。
現(xiàn)在給一串后序和中序遍歷序列休傍，你應(yīng)該要輸出對應(yīng)的中序遍歷的序列，如果此樹不唯一蹲姐，只需要輸出他們其中一個即可磨取。
輸入詳情：每一個輸入包含一個測試樣例人柿，對于每一個樣例，第一個是一個正整數(shù)忙厌，表示整個二叉樹有多少個節(jié)點凫岖。第二行給出前序遍歷序列，第三行給出后續(xù)遍歷序列逢净，所有的數(shù)字之間右空格分隔哥放。
輸出詳情：對于每一個測試樣例，如果樹是唯一的爹土，輸出yes甥雕，如果不是，輸出no胀茵。下一行輸出中序遍歷序列社露。如果解不是唯一的，任何答案都可以琼娘。保證至少有一個解峭弟。
這個題目第一眼看到是一點思路都沒有，上了考場標(biāo)準(zhǔn)0分脱拼。首先分析一下前序遍歷和后續(xù)遍歷瞒瘸。前序遍歷：根，左子樹熄浓，右子樹情臭；后序遍歷：左子樹，右子樹玉组，根谎柄。那么如果這一棵樹都有左右子樹丁侄，那么這棵樹就是唯一的惯雳，如果這棵樹只有左子樹，或者右子樹鸿摇，那就有可能有多種情況石景，這唯一的一棵樹可以在左邊也可以在右邊。這也就是為什么不能唯一確定的原因拙吉，這個問題在考408的時候都沒有深究潮孽。
那么關(guān)鍵就是切分了：
TreeNode create(int preL, int preR, int postL, int postR, int *preSequences, int *postSequences) {
if (preL > preR) {
return nullptr;
}
TreeNode root = new treeNode;
root->val = preSequences[preL];
root->leftChild = root->rightChild = nullptr;
if (preL == preR) {
return root;
}
如果如果只有一個元素，說明就是一個節(jié)點筷黔，沒有左右子樹往史，直接返回。
if (k - preL > 1) {
root->leftChild = create(preL + 1, k - 1, postL, postL + k - preL - 2, preSequences, postSequences);
root->rightChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
} else {
flag = false;
root->leftChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
}
如果發(fā)現(xiàn)包括根節(jié)點在內(nèi)是大于1的佛舱，那么說明存在左右子樹椎例，那么肯定唯一挨决，如果不是大于1，那說明只有一顆子樹订歪，放左放右都可以脖祈。最后遍歷即可。
1083
給出一段數(shù)字,你應(yīng)該可以用他們組成最小的數(shù)字刷晋，舉個例子盖高，我們組成許多數(shù)字如32-321-0229-87or0229-321-3214等等不同組成方式的數(shù)字段。
這個題目真的非常簡單眼虱，之前在洛谷刷過差不多的喻奥。主要是幾個字符串比較的情況，如123 1230蒙幻，如果是這樣映凳，排序必須是1230123，因為最后的0是小于前面的第一個數(shù)1的邮破，但如果是123 1235诈豌，那么就要倒過來了，1231235抒和。其實就是貪心就好了矫渔。我也不知道為什么這個題目會歸類到樹這一塊。
int cmp(string a, string b) {
return a + b < b + a;
}
這句就是最關(guān)鍵的了摧莽，注意一些特殊情況庙洼，當(dāng)全是0的時候要輸出0即可。之前就是因為直接把打頭的0去掉镊辕，導(dǎo)致如果result = 0那么什么都不輸出油够。
1147
水題一道，題目直接給出是完全二叉樹了征懈，直接用數(shù)組表示即可石咬。
bool isHeap(int *array, int n, bool maxHeap) {
for (int i = 1; i <= n / 2; ++i) {
int left = i * 2;
int right = left + 1;
if (left <= n) {
if (maxHeap) {
if (array[left] > array[i]) {
return false;
}
} else {
if (array[left] < array[i]) {
return false;
}
}
}
if (right <= n) {
if (maxHeap) {
if (array[right] > array[i]) {
return false;
}
} else {
if (array[right] < array[i]) {
return false;
}
}
}
}
return true;
}
考查一下是否符合堆的要求即可。
1151
這個題目寫出來本以為勝券在握卖哎，這個規(guī)律很好找鬼悠，前序遍歷是根左右，中序遍歷是左根右亏娜，那么在中序遍歷里面給出的兩個關(guān)鍵字的根一定在兩個關(guān)鍵字之間焕窝，比如中序遍歷7 2 3 4 6 5 1 8，找26的最短祖先维贺，祖先看定在3它掂，4之間。對于前序遍歷溯泣，祖先肯定在26的前面虐秋，以此類推就好了晰韵。
所以首要一步就是要找到當(dāng)前兩個關(guān)鍵字的位置，然后看他中間的數(shù)是不是在前序遍歷的那兩個關(guān)鍵字的前面即可熟妓。一開始是直接遍歷找位置雪猪，結(jié)果超時了。
// map<int, bool> map_match;
//
// int first, second;
//
// if (aIndex > bIndex) {
// first = bIndex;
// second = aIndex;
// } else {
// first = aIndex;
// second = bIndex;
// }
//
// for (int j = first; j <= second; ++j) {
// map_match[inOrder[j]] = true;
// }
//
// for (int l = 0; l <= aPreIndex && l <= bPreIndex; ++l) {
// if (map_match[preOrder[l]]) {
// if (preOrder[l] != a && preOrder[l] != b) {
// cout << "LCA of " << a << " and " << b << " is " << preOrder[l] << "." << endl;
// break;
// } else if (preOrder[l] == a) {
// cout << a << " is an ancestor of " << b << "." << endl;
// break;
//
// } else if (preOrder[l] == b) {
// cout << b << " is an ancestor of " << a << "." << endl;
// break;
//
// }
// }
// }
超時的想法是先把中序遍歷里面的在關(guān)鍵字之間的變量都存在一個map里面起愈，然后遍歷前序遍歷直到遇到關(guān)鍵字只恨，結(jié)果超時了。在輸入的時候抬虽，就應(yīng)該事先把遍歷的位置用map存下來官觅，然后就只需要遍歷一次了：
//
// Created by GreenArrow on 2020/3/15.
//
#include <iostream>
#include <map>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
int preOrder[n];
int inOrder[n];
map<int, int> positionPre, positionIn;
for (int i = 0; i < n; ++i) {
cin >> inOrder[i];
positionIn[inOrder[i]] = i;
}
for (int j = 0; j < n; ++j) {
cin >> preOrder[j];
positionPre[preOrder[j]] = j;
}
for (int k = 0; k < m; ++k) {
int a, b;
cin >> a >> b;
int aIndex = -1;
int bIndex = -1;
int aPreIndex = -1;
int bPreIndex = -1;
if (positionIn.count(a)) {
aIndex = positionIn[a];
}
if (positionIn.count(b)) {
bIndex = positionIn[b];
}
if (aIndex == -1 && bIndex == -1) {
cout << "ERROR: " << a << " and " << b << " are not found." << endl;
continue;
} else if (aIndex != -1 && bIndex == -1) {
cout << "ERROR: " << b << " is not found." << endl;
continue;
} else if (aIndex == -1) {
cout << "ERROR: " << a << " is not found." << endl;
continue;
}
if (a == b) {
cout << a << " is an ancestor of " << b << "." << endl;
continue;
}
for (int i = 0; i < n; ++i) {
int temp = preOrder[i];
int inPosition = positionIn[temp];
if (temp == a) {
cout << a << " is an ancestor of " << b << "." << endl;
break;
} else if(temp == b){
cout << b << " is an ancestor of " << a << "." << endl;
break;
}
if(inPosition > aIndex && inPosition < bIndex){
cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
break;
} else if(inPosition > bIndex && inPosition < aIndex){
cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
break;
}
}
1110
這個題目想了挺久的，有點意思阐污，完全二叉樹的數(shù)組是全滿的休涤，所以只需要看看數(shù)組是不是全部能訪問就好了。首先建樹找根節(jié)點：
for (int i = 0; i < n; ++i) {
string left, right;
cin >> left >> right;
if (left == "-") {
array[i].left = -1;
} else {
array[i].left = string2number(left);
father[array[i].left] = i;
}
if (right == "-") {
array[i].right = -1;
} else {
array[i].right = string2number(right);
father[array[i].right] = i;
}
}
int root = -1;
for (int j = 0; j < n; ++j) {
if (father[j] == -1) {
root = j;
}
}
father的用處就是看看是不是根節(jié)點而已笛辟。沒有什么太大用處功氨，接著就是遍歷填數(shù)組了，用前中后序遍歷填寫都可以手幢，這里還是用層次遍歷好了：
int level(node *array, int root, int *array_tree) {
queue<int> Queue;
Queue.push(root);
array[root].index = 0;
array_tree[array[root].index] = 1;
vector<int> sequences;
while (!Queue.empty()) {
int cur = Queue.front();
sequences.push_back(cur);
Queue.pop();
if (array[cur].left != -1) {
Queue.push(array[cur].left);
array_tree[array[cur].index * 2 + 1] = 1;
array[array[cur].left].index = array[cur].index * 2 + 1;
}
if (array[cur].right != -1) {
Queue.push(array[cur].right);
array_tree[array[cur].index * 2 + 2] = 1;
array[array[cur].right].index = array[cur].index * 2 + 2;
}
}
return sequences[sequences.size() - 1];
}
然后只要看看遍歷過的數(shù)組有沒有空的捷凄，有空的那就不是完全二叉樹了。
1020
給定后序遍歷和中序遍歷求前序遍歷围来，這個考408的時候就寫過了跺涤，水題一道，直接上代碼监透。
//
// Created by GreenArrow on 2020/2/21.
//
#include <iostream>
#include <queue>
using namespace std;
typedef struct node {
int data;
node *left;
node *right;
} node;
node *create(int postl, int postr, int inl, int inr, int *post, int *in) {
if (postl > postr) {
return nullptr;
}
node *root = new node;
root->data = post[postr];
int index = 0;
for (int i = inl; i <= inr; ++i) {
if (in[i] == post[postr]) {
index = i;
break;
}
}
int leftTreeNumber = index - inl;
int rightTreeNumber = inr - index;
root->left = create(postl, postl + leftTreeNumber - 1, inl, index - 1, post, in);
root->right = create(postl + leftTreeNumber, postr - 1, index + 1, inr, post, in);
return root;
}
void levelOrder(node *root) {
queue<node *> Queue;
Queue.push(root);
int index = 0;
int arr[10010];
while (!Queue.empty()) {
node *next = Queue.front();
arr[index++] = next->data;
Queue.pop();
if (next != nullptr && next->left) {
Queue.push(next->left);
}
if (next != nullptr && next->right) {
Queue.push(next->right);
}
}
for (int i = 0; i < index; ++i) {
cout << arr[i];
if (i != index - 1) {
cout << " ";
}
}
cout << endl;
}
int main() {
int n;
cin >> n;
int postOrder[n], inOrder[n];
for (int i = 0; i < n; ++i) {
cin >> postOrder[i];
}
for (int j = 0; j < n; ++j) {
cin >> inOrder[j];
}
node *root = create(0, n - 1, 0, n - 1, postOrder, inOrder);
levelOrder(root);
}
1043
這個題也是水題桶错，就是麻煩，也就鏡像哪里有點麻煩胀蛮，遍歷的時候先遍歷右邊再遍歷左邊就好了院刁，代碼不貼了，占篇幅醇滥。
有關(guān)圖的題目：1122黎比，1142超营，1150鸳玩，1026，1013演闭，1021不跟，1034，1003米碰，1018窝革，1030购城，1087，1111
1122
這個題目能不能做出來就看你能不能記得簡單回路是啥玩意了虐译。簡單回路就是在回路序列里面瘪板，除了第一個與最后一個頂點相同，其他頂點各不相同漆诽；那么哈密頓回路就再加上訪問所有節(jié)點的條件侮攀。訪問到所有節(jié)點，只有第一個與最后一個節(jié)點相同厢拭，中間訪問的節(jié)點只訪問一次就叫哈密頓回路兰英。
那么判斷的幾個條件：
1.總點數(shù)是否等于n+1
2.第一項是否等于最后一項
3.相鄰節(jié)點之間是否能訪問
4.是否訪問了所有節(jié)點
bool Hamilton(int n, int *array, int vertex_n) {
if (vertex_n + 1 != n) {
return false;
}
bool visited[vertex_n + 1];
fill(visited + 1, visited + vertex_n + 1, false);
int pre = array[1];
visited[pre] = true;
for (int i = 2; i <= n; ++i) {
if (chess[pre][array[i]] != 1 && chess[array[i]][pre] != 1 && array[i] != pre) {
return false;
}
pre = array[i];
visited[pre] = true;
}
for (int j = 1; j <= vertex_n; ++j) {
if (!visited[j]) {
return false;
}
}
if (array[1] != array[n]) {
return false;
}
return true;
}
1142
這個題目也是水題，遍歷就好了供鸠，還不超時畦贸。首先遍歷一遍看看序列之間的數(shù)字是否都有通路，其次遍歷剩下不再序列里面的點看看能不能加入即可楞捂。
string isMaxClique(int vertex_n, int n, int *array) {
if(n == 0){
return "Not a Clique";
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (array[i] != array[j] && chess[array[i]][array[j]] == 0) {
return "Not a Clique";
}
}
}
for (int k = 1; k <= vertex_n; ++k) {
bool flag = true;
if (!visited[k]) {
for (int i = 1; i <= vertex_n; ++i) {
if (i == k) {
continue;
}
if (!visited[i]) {
continue;
}
if (chess[k][i] != 1) {
flag = false;
break;
}
}
if (flag) {
return "Not Maximal";
}
}
}
return "Yes";
}
水題一道薄坏。
1150
存在一個旅行推銷員的問題，給定一個城市列表和這些城市之間的距離寨闹，問颤殴，哪條最短的路能夠訪問所有的城市并且最后能回到出發(fā)的城市？這是哪個NPhard的問題鼻忠，也就是指示復(fù)雜度類型的問題涵但，在運籌學(xué)研究和計算機科學(xué)理論研究上有很重要的意義。
在這個問題里帖蔓，你應(yīng)該要從這些城市列表里面找到一個循環(huán)矮瘟，這個循環(huán)是旅行者問題的解。
輸入詳情：每一個輸入包含一個測試樣例塑娇。對于每一個案例澈侠，第一行給出兩個正整數(shù)，分別是城市的數(shù)量以及邊數(shù)埋酬。接下來是M行哨啃，每一個描述一條邊，邊的格式如下：城市1写妥，城市2拳球，距離。城市編號從1到N且距離為正數(shù)不超過100珍特。接下來一行給出正整數(shù)K祝峻，路徑的數(shù)量，緊接著K行描述路徑，路徑格式為n,C1,C2......莱找。
輸出詳情：對于每一條路酬姆，打印出路徑PathX:TotalDist，x是標(biāo)號奥溺，totalDist是路徑的總距離辞色。差不多就這樣。
這個題目讀起來浮定，很繁雜淫僻，一開始看的時候還以為他要我算出所有的簡單回路。其實也就是遍歷操作即可壶唤。和前面一道圖的題目類似雳灵，注意一些細(xì)節(jié)操作即可，水題一道闸盔。
int getClassification(int vertex_n, int n, int *array, int &classification) {
int pre = array[0];
int sum = 0;
int result = 0;
for (int i = 1; i < n; ++i) {
if (chess[pre][array[i]] != INT_MAX) {
sum += chess[pre][array[i]];
pre = array[i];
} else {
result = INT_MAX;
classification = 2;
return result;
}
}
if (array[0] != array[n - 1]) {
classification = 2;
result = sum;
return result;
}
bool flag2 = false;
for (int j = 1; j <= vertex_n; ++j) {
if (visited[j] == 0) {
classification = 2;
result = sum;
return result;
}
if (visited[j] >= 2) {
if (j == array[0] && visited[j] > 2) {
flag2 = true;
}
if (j != array[0] && visited[j] > 1) {
flag2 = true;
}
}
}
if (flag2) {
classification = 3;
result = sum;
return result;
}
classification = 1;
result = sum;
return result;
}
1126
在圖論中悯辙，一條路徑如果能訪問每條邊一次就叫做歐幾里得路徑。相同的迎吵，一條歐幾里得環(huán)一條起點和終點相同的歐幾里得路徑躲撰。在1736年，歐拉等人第一次在解決著名的七....問題是提出击费。如果一個圖是聯(lián)通圖并且所有的頂點的度為偶數(shù)拢蛋，那么它會存在一條歐幾里得環(huán)，這樣的圖我們稱為Eulerian蔫巩。（歐幾里得人谆棱？？圆仔？）如果此圖恰好有兩個奇數(shù)度的頂點垃瞧，則所有的歐幾里得路徑都是從其中一個頂點出發(fā)到另一個頂點結(jié)束，只有歐幾里得路徑而沒有歐幾里得環(huán)的圖稱為semi-Eulerian
輸入詳情：每一個輸入文件包含一個測試樣例坪郭，每一個案例開頭第一行包含兩個數(shù)字个从，N和M，分別是頂點總數(shù)和邊的總數(shù)歪沃。接下來的M行描述一條邊的兩端嗦锐。
輸出描述：第一行打印出頂點的度，按照頂點序號遞增的次序沪曙，第二行輸出圖的類型奕污。大概就是這樣吧。
這個題目很容易瞎了眼珊蟀，條件有幾個菊值，其一連通圖，其二度的數(shù)量育灸。首先可以用BFS或者DFS判斷是否是聯(lián)通圖腻窒，然后再判斷度的數(shù)量即可。先隨機找一個點開始BFS磅崭，如果一次BFS完成之后所有的點都被訪問了儿子，那么這個圖就是聯(lián)通圖，看到很多答案都是每一個點都BFS砸喻，其實沒有必要柔逼，僅僅一個點進(jìn)行BFS即可。
void BFS(int v) {
visited[v] = true;
for (int i = 0; i < nodes[v].size(); ++i) {
if (!visited[nodes[v][i]]) {
BFS(nodes[v][i]);
}
}
}
后面的判斷degress奇偶沒有很簡單割岛，也是水題愉适。
1013
這也是一個連通圖問題，給出n個城市癣漆，m條路维咸，問你如果這個城市消失了，需要添加多少條道路才能聯(lián)通惠爽。也是個水題癌蓖，你把當(dāng)前要消失的城市包括其有關(guān)路徑都去掉，然后看看有多少個聯(lián)通分量婚肆，有多少個聯(lián)通分量就證明有多少個地區(qū)是分開的租副，然后減一就是公路的數(shù)量。一開始的做法是復(fù)制一份新的地圖较性，把敵對城市去掉用僧，超時了，然而我這么做是多余的赞咙，完全可以在深度遍歷的時候忽略敵對城市即可永毅。
for (int k = 0; k < K; ++k) {
fill(visited, visited + N + 1, false);
int city;
scanf("%d", &city);
visited[city] = true;
int index = 0;
for (int l = 1; l <= N; ++l) {
if (!visited[l]) {
BFS(l, city);
index++;
}
}
直接把敵對城市設(shè)置成已經(jīng)訪問即可，這樣BFS不會去尋找已經(jīng)訪問的節(jié)點人弓。
1021
如果一個圖是聯(lián)通的而且又沒有環(huán)沼死，那么就可以看成是一顆樹。樹的高度就依賴于選擇的根是哪一個點〈薅模現(xiàn)在要求你找出高度最高的樹的根意蛀，這樣的根稱為最深根。
輸入詳情：每一個輸入包含一個測試樣例健芭，對于每一個樣例县钥，第一行一個正整數(shù)，表示頂點的數(shù)量慈迈，因此若贮，頂點編號從1到N省有，接下來N-1行描述邊。
輸出詳情：對于每一個測試樣例谴麦，打印出深的根蠢沿，如果根不是唯一，打印出所有的根匾效，并按照升序排列舷蟀。如果不是樹，打印出聯(lián)通分量的個數(shù)面哼。
考查深度優(yōu)先和聯(lián)通分量野宜，也是水題，BFS遍歷查找最深的根魔策，同時BFS把聯(lián)通分量給找出來匈子，因為查找最深的根和查找聯(lián)通分量是可以合在一起，關(guān)鍵就是怎么合起來了闯袒。修改一下BFS旬牲，讓其返回最深的層次：
void BFS(int v, int depth) {
visited[v] = true;
bool flag = true;
for (int i = 0; i < graph[v].size(); ++i) {
int u = graph[v][i];
if (!visited[u]) {
flag = false;
BFS(u, depth + 1);
}
}
if (flag) {
if (max_BFS < depth) {
max_BFS = depth;
}
}
}
每一次就看看當(dāng)前節(jié)點的下一個節(jié)點是不是全部都訪問過了，如果都訪問過了那就說明到底了搁吓，對比之前的然后返回原茅。完成后注意清空visited：
for (int j = 1; j <= N; ++j) {
fill(visited, visited + N + 1, false);
max_BFS = INT_MIN;
BFS(j, 0);
每一次完成需要清空，需要遍歷所有的點找到最深的根堕仔。順便在第一次BFS遍歷的時候看看是否有訪問到了所有的節(jié)點擂橘，如果沒有，那就沒有必要再找最深的點了摩骨，直接找聯(lián)通分量了：
int max = INT_MIN;
int index_ = 0;
bool flag = false;
for (int j = 1; j <= N; ++j) {
fill(visited, visited + N + 1, false);
max_BFS = INT_MIN;
BFS(j, 0);
//cout << max_BFS << endl;
index_++;
if (!flag)
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
flag = true;
//不聯(lián)通
for (int k = j + 1; k <= N; ++k) {
if (!visited[k]) {
BFS(k, 0);
index_++;
}
bool connected = true;
for (int l = 1; l <= N; ++l) {
if (!visited[l]) {
connected = false;
break;
}
}
if (connected) {
cout << "Error: " << index_ << " components" << endl;
return 0;
}
}
}
}
1034
警察找到犯罪團伙透明的方法是檢查他們的手機通贞，如果在A和B之間存在了電話聯(lián)系，那么久說A和B是有關(guān)系的恼五。關(guān)系的權(quán)重是定義了雙方通話的總時長昌罩。一個幫派是指幫派成員超過兩個人，并且這些人之間互相都有聯(lián)系灾馒，且通話量超過既定閾值K茎用。在每一個幫派，存在一個通話量權(quán)重最高的人睬罗，以此人為首」旃Γ現(xiàn)在給定一些通話列表，你應(yīng)該團伙以及頭目容达。
一開始沒看清題目古涧，以為名字是三個字母相同的，從A-Z花盐，就26個羡滑，然后寫出來只對了兩個點菇爪。然后做出來發(fā)現(xiàn)不是。我這里使用的是用向量存儲圖柒昏，單獨存儲邊凳宙，如果要計算一個圖的權(quán)重，遍歷圖中節(jié)點相加即可昙楚。這里的關(guān)系的雙向關(guān)系近速，也就是無向圖诈嘿，但是通話量是單向的顿仇，在計算聯(lián)通分量的時候需要按照無向圖計算惭等，計算權(quán)重的時候要按照有向圖的邊相加。如果按照上述做法，就麻煩了膜宋，我就是這么做的，其實A->B和B->A的權(quán)重是可以相加當(dāng)成一條邊計算高每，然后權(quán)重相加的時候只需要加一次就好了松邪，代碼優(yōu)化的地方可以很多，首先就是使用的存儲圖的結(jié)構(gòu)就可以使用矩陣作郭，然后權(quán)重計算不用分開算陨囊，相加在一起當(dāng)成是無向圖。
for (int i = 0; i < n; ++i) {
string A, B;
int weight;
cin >> A >> B >> weight;
int ANumber = string2number(A), BNumber = string2number(B);
name[ANumber] = A;
name[BNumber] = B;
visited[ANumber] = false;
visited[BNumber] = false;
graphs[ANumber].push_back(BNumber);
graphs[BNumber].push_back(ANumber);
if (edges.count(ANumber) == 0) {
vector<edge> e;
e.emplace_back(BNumber, weight);
edges[ANumber] = e;
} else {
edges[ANumber].push_back(edge(BNumber, weight));
}
totalPhone[ANumber] += weight;
totalPhone[BNumber] += weight;
}
這塊在輸入的時候把輸入的name給量化了夹攒，把所有通過節(jié)點的通話量加起來蜘醋，后面要選擇一個團伙的頭目需要使用到。邊也存儲下來咏尝，數(shù)組下標(biāo)就是起始點压语，邊存儲終點和權(quán)值。
void BFS(int v, int &size, int &total, vector<int> &gangs) {
visited[v] = true;
for (int i = 0; i < graphs[v].size(); ++i) {
if (!visited[graphs[v][i]]) {
gangs.push_back(graphs[v][i]);
total = addEdges(graphs[v][i], total);
size++;
BFS(graphs[v][i], size, total, gangs);
}
}
}
然后就是調(diào)用BFS了编检，最后還需要進(jìn)行排序輸出胎食。
1003
找最短路徑，算出最短路徑有多少條允懂，每一個城市會有相應(yīng)的人員厕怜，經(jīng)過這個城市就可以帶走這些人員，在這些最短路徑里面最多能帶走多少人蕾总。
很明顯是屬于最短路徑的問題酣倾，最短路徑很容易，關(guān)鍵是如何存儲下最短路徑的條數(shù)谤专≡晡可以使用一個Num數(shù)組存儲，一開始num[source] = 1置侍，代表當(dāng)前只有這一條路徑映之，當(dāng)出現(xiàn)了多條路徑之后拦焚，也就是在更新到達(dá)路徑的時候d[v]如果和之前的是相同的，num[v] += num[source]杠输，這樣其實模擬了一個乘法增長的過程赎败，因為后面的每一條路增加，其實都是倍數(shù)增長蠢甲。
void Dijikstra(int v, int n) {
fill(d, d + MAX, INT_MAX);
fill(visited, visited + MAX, false);
fill(w, w + MAX, 0);
fill(num, num + MAX, 0);
w[v] = people[v];
num[v] = 1;
d[v] = 0;
for (int i = 0; i < n; ++i) {
int min = INT_MAX;
int u = -1;
for (int j = 0; j < n; ++j) {
if (!visited[j] && min > d[j]) {
min = d[j];
u = j;
}
}
if (u == -1)
return;
visited[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited[k] && chess[u][k] != INT_MAX) {
if (d[k] > d[u] + chess[u][k]) {
d[k] = d[u] + chess[u][k];
w[k] = w[u] + people[k];
num[k] = num[u];
} else if (d[k] == d[u] + chess[u][k]) {
num[k] += num[u];
if (w[u] + people[k] > w[k]) {
w[k] = w[u] + people[k];
}
}
}
}
}
}
就是調(diào)用算法即可僵刮，如果還需要求路徑，只需要用一個vector即可鹦牛。
1018
大概就是說有幾個車站搞糕，當(dāng)容量為一半的時候是最佳狀態(tài)，現(xiàn)在需要去某一個車站曼追，問你那一條路徑是路徑最短窍仰，填補車輛最少，回收車輛最少礼殊【运保看上去好像是最短路徑，但是事實上這是一個深度搜索的問題晶伦，最短路徑?jīng)]有辦法保證送回和送出的數(shù)據(jù)是全局最優(yōu)的碟狞。
void DFS(int s, int end, int tempSend, int tempBack, int tempDis) {
visited[s] = true;
tempPath.push_back(s);
if (s == end) {
if (minDis > tempDis) {
path = tempPath;
minDis = tempDis;
minSend = tempSend;
minBack = tempBack;
} else if (minDis == tempDis) {
if (minSend > tempSend) {
path = tempPath;
minSend = tempSend;
minBack = tempBack;
} else if (minSend == tempSend) {
if (minBack > tempBack) {
path = tempPath;
minSend = tempSend;
minBack = tempBack;
}
}
}
return;
}
for (int i = 1; i <= n; ++i) {
if (!visited[i] && chess[s][i] != INT_MAX) {
int temp = bikes[i] - capacity / 2;
int tempB = tempBack;
int tempS = tempSend;
if (temp >= 0) {
tempB += temp;
} else {
if (temp + tempB < 0) {
tempS -= (temp + tempB);
tempB = 0;
} else {
tempB = (temp + tempB);
}
}
DFS(i, end, tempS, tempB, tempDis + chess[s][i]);
tempPath.pop_back();
visited[i] = false;
}
}
}
有點復(fù)雜，用Dijiskra也只能有25分婚陪，主要容易搞混的其實就是回收和放出那里：
int temp = bikes[i] - capacity / 2;
int tempB = tempBack;
int tempS = tempSend;
if (temp >= 0) {
tempB += temp;
} else {
if (temp + tempB < 0) {
tempS -= (temp + tempB);
tempB = 0;
} else {
tempB = (temp + tempB);
}
}
先算出當(dāng)前點需要多少族沃，如果不需要了還多出盈余，那就加上前面需要送回的近忙；如果缺了竭业，就看看以往需要送回的能不能填補，如果能填補及舍，那么減去已經(jīng)填補的未辆，如果不能填補，那么就要繼續(xù)送剩下的锯玛。
1030
給出一張旅行者地圖咐柜，地圖給出城市之間的距離已經(jīng)花費，現(xiàn)在要求你寫出程序幫助旅行者決定最短的路徑攘残，如果路徑最短并非唯一拙友，則給出最小花費，次最小花費的最短路徑保證唯一歼郭。
輸入詳情：每一個輸入包含了一個測試樣例遗契，每一個樣例由4個正整數(shù)開始，分別是城市數(shù)量病曾，告訴公路的數(shù)量牍蜂，起始點和目的地漾根。接下來M行分別就是邊的屬性。
輸出詳情：對于每一個測試樣例鲫竞，輸出最短路徑辐怕，路徑距離，路徑花費从绘。
這個題目相比上面一題要簡單不少寄疏，就是一個條件而已:
void Dijiskra(int s, int n) {
fill(visited, visited + MAX, false);
fill(d, d + MAX, edge(INT_MAX, INT_MAX));
d[s].distance = 0;
d[s].cost = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited[j] && d[j].distance < min) {
min = d[j].distance;
u = j;
}
}
if (u == -1) {
return;
}
visited[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited[k] && map[u][k].distance != INT_MAX) {
if (d[k].distance > d[u].distance + map[u][k].distance) {
d[k].distance = d[u].distance + map[u][k].distance;
d[k].cost = d[u].cost + map[u][k].cost;
path[k] = u;
} else if (d[k].distance == d[u].distance + map[u][k].distance) {
if (d[k].cost > d[u].cost + map[u][k].cost) {
d[k].distance = d[u].distance + map[u][k].distance;
d[k].cost = d[u].cost + map[u][k].cost;
path[k] = u;
}
}
}
}
}
}
1087
說是有幾個城市，城市之間存在路徑僵井，通過路徑需要花費陕截，而每經(jīng)過一個城市就可以獲得這個城市的快樂值，問路徑最短并且能得到最大快樂值的是那一條路驹沿。
這個題目比上上題和上上上題都要簡單艘策，和上一題難度差不多蹈胡，其實就是最短路徑加上一點條件而已渊季。
void Dijiskra(int s, int n) {
fill(visited, visited + MAX, false);
fill(d, d + MAX, INT_MAX);
fill(happy_total, happy_total + MAX, 0);
fill(num, num + MAX, 0);
num[s] = 1;
d[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited[j] && d[j] < min) {
min = d[j];
u = j;
}
}
visited[u] = true;
if (u == -1)
return;
for (int k = 0; k < n; ++k) {
if (!visited[k] && chess[u][k] != INT_MAX) {
if (d[k] > d[u] + chess[u][k]) {
d[k] = d[u] + chess[u][k];
happy_total[k] = happy_total[u] + name[k].happy;
num[k] = num[u];
path[k] = u;
} else if (d[k] == d[u] + chess[u][k]) {
num[k] += num[u];
if (happy_total[k] < happy_total[u] + name[k].happy) {
happy_total[k] = happy_total[u] + name[k].happy;
path[k] = u;
}
}
}
}
}
}
1111
這個題目和上一題很類似，兩個最短路徑就好了罚渐，當(dāng)然了也可以合成一個却汉。首先一個是求路程花費最短的，其次是求時間最短荷并，如果路徑最短有多條合砂，那就把時間最短的選出來；如果時間最短的有多條源织，把經(jīng)過城市最短的選出來翩伪。城市最短可以用一個數(shù)組記錄，每更新一次谈息，就繼承前一點的值加1缘屹。
void Dijiskra_t(int s, int n) {
fill(t, t + MAX, INT_MAX);
fill(visited_t, visited_t + MAX, false);
fill(size_time, size_time + MAX, 0);
size_time[s] = 1;
t[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited_t[j] && t[j] < min) {
u = j;
min = t[j];
}
}
visited_t[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited_t[k] && chess[u][k].time != INT_MAX) {
if (t[k] > t[u] + chess[u][k].time) {
t[k] = t[u] + chess[u][k].time;
size_time[k] = size_time[u] + 1;
path_t[k] = u;
} else if (t[k] == t[u] + chess[u][k].time) {
if (size_time[k] > size_time[u] + 1) {
size_time[k] = size_time[u] + 1;
path_t[k] = u;
}
}
}
}
}
}
DFS，BFS：1004侠仇，1021轻姿，1018（這兩題圖論已寫），1076逻炊，1079互亮，1094，1103余素，1027豹休，1130
1004
規(guī)定了根節(jié)點是1號，讓你找出每一層的葉子節(jié)點桨吊。這個題目也是個水題威根，但是有些小坑窑眯，稍不注意就拿不了30∫搅可以用BFS也可以用DFS磅甩，我是用BFS做的，因為直接在樹的結(jié)構(gòu)里面加上層次屬性就可以了姥卢。測試點2有一個小坑卷要，當(dāng)輸入1 0的時候要輸出1，因為在BFS里面我的最大層次是初始-1独榴，如果輸入1 0那么就不會進(jìn)入到while循環(huán)里面僧叉，結(jié)果什么都不輸出了，所以把最大層次初始化為0就好棺榔；還有當(dāng)n=0的時候不做處理瓶堕，什么都不輸出，需要直接return 0症歇；
int levelOrder(treeNode *root) {
int max = 0;
queue<treeNode *> Queue;
Queue.push(root);
root->depth = 0;
while (!Queue.empty()) {
treeNode *cur = Queue.front();
Queue.pop();
if (!cur->children.size())
depth[cur->depth]++;
for (int i = 0; i < cur->children.size(); ++i) {
cur->children[i]->depth = cur->depth + 1;
Queue.push(cur->children[i]);
if (cur->children[i]->depth > max) {
max = cur->children[i]->depth;
}
}
}
return max;
}
1076
這個題目郎笆，一開始看錯題目了，把粉絲和up主的關(guān)系看反了忘晤，第一行3 2 3 4應(yīng)該是2 3 4號用戶關(guān)注了1才對宛蚓。這個題目其實也很簡單，就是廣度優(yōu)先就好了：
int BFS(int s, int L, vector<int> graph[MAX]) {
fill(visited, visited + MAX, false);
fill(layer, layer + MAX, 0);
int number = 0;
layer[s] = 0;
visited[s] = true;
queue<int> Queue;
Queue.push(s);
while (!Queue.empty()) {
int cur = Queue.front();
Queue.pop();
if (layer[cur] <= L && cur != s) {
number++;
}
for (int i = 0; i < graph[cur].size(); ++i) {
int v = graph[cur][i];
if (!visited[graph[cur][i]]) {
Queue.push(graph[cur][i]);
layer[graph[cur][i]] = layer[cur] + 1;
visited[graph[cur][i]] = true;
}
}
}
return number;
}
1079
這個題目和之前的有一道類似设塔，這里還是用DFS凄吏，水題一道，直接DFS遍歷就好了闰蛔。需要注意痕钢，根節(jié)點是不唯一的，可能有多個根節(jié)點序六，需要把所有可能的根節(jié)點集中一起分開遍歷任连，最后還有一些內(nèi)存問題，這里說N是小于一萬难咕，然而我開一萬段溢出课梳，開十萬才行。
void DFS(treeNode *root, double price, double r) {
if (number[root->val] != -1 && root->children.size() == 0) {
total += number[root->val] * price;
return;
}
for (int i = 0; i < root->children.size(); ++i) {
DFS(root->children[i], price * ((100 + r) / 100), r);
}
}
1094
前面有過類似的余佃，要你求最多孩子的層數(shù)以及孩子數(shù)量暮刃。水題一道，層次遍歷就好了爆土，或者深度搜索也可以椭懊。
void BFS(TreeNode root) {
root->depth = 1;
queue<TreeNode> Queue;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
depth[cur->depth]++;
if (max_ < depth[cur->depth]) {
max_ = depth[cur->depth];
maxDepth = cur->depth;
}
for (int i = 0; i < cur->children.size(); ++i) {
Queue.push(cur->children[i]);
cur->children[i]->depth = cur->depth + 1;
}
}
}
1103
這個題目第一眼覺得是水題，寫完了才發(fā)現(xiàn)不對勁，很明顯是DFS氧猬，不過關(guān)鍵還是要確定上下界背犯。把所有p次方的數(shù)字存儲在一個數(shù)組里面，然后計算上界盅抚，因為底數(shù)最小是1漠魏，那么最大就是n - (k-1)大小了，所以底數(shù)最大就是對(n-(k-1))開p次方：
void init(int n, int p) {
for (int i = 0; i <= n; i++) {
int temp = kpow(i, p);
if (temp > n) {
break;
}
arr[i] = temp;
}
double num = (n - (K - 1));
double kDouble = P;
tempMax = pow(num, 1 / kDouble);
}
接著就是DFS妄均，倒序開始柱锹，找到那個和最大的就好了，沒必要再進(jìn)行比較了丰包。
void DFS(int i, int sumPre, int depth, int tempSum) {
if (depth == K) {
if (sumPre == N) {
if (sum < tempSum) {
sum = tempSum;
result.assign(numString.begin(), numString.begin() + K);
}
}
return;
}
if (sumPre >= N || depth > K) {
return;
}
for (; i >= 1; --i) {
if (sumPre + arr[i] <= N) {
numString[depth] = i;
DFS(i, sumPre + arr[i], depth + 1, tempSum + i);
}
}
}
如果遞歸層數(shù)到了k禁熏，那么就說明已經(jīng)有k個數(shù)了，查看是否等于n邑彪，并且和是否大于result瞧毙。如果沒到k層就大于等于n，那就不用看了寄症，直接回去宙彪。否則繼續(xù)DFS。然而超時了瘸爽，找了一天都不知道要怎么改您访，總感覺沒問題：
//
// Created by GreenArrow on 2020/3/24.
//
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> result;
int sum = -1;
vector<int> numString(10001, 0);
int arr[10010];
int N, K, P;
int kpow(int x, int y) {
int ret = x;
while (--y) {
ret *= x;
}
return ret;
}
void DFS(int i, int sumPre, int depth, int tempSum) {
if (depth == K) {
if (sumPre == N) {
if (sum < tempSum) {
sum = tempSum;
result.assign(numString.begin(), numString.begin() + K);
}
}
return;
}
if (sumPre >= N || depth > K) {
return;
}
for (; i >= 1; --i) {
if (sumPre + arr[i] <= N) {
numString[depth] = i;
DFS(i, sumPre + arr[i], depth + 1, tempSum + i);
}
}
}
int tempMax = 0;
void init(int n, int p) {
for (int i = 0; i <= n; i++) {
int temp = kpow(i, p);
if (temp > n) {
break;
}
arr[i] = temp;
}
double num = (n - (K - 1));
double kDouble = P;
tempMax = pow(num, 1 / kDouble);
}
int main() {
cin >> N >> K >> P;
if (N == K) {
cout << N << " = ";
for (int i = 0; i < K; ++i) {
cout << 1 << "^" << P;
if (i != K - 1) {
cout << " + ";
}
}
return 0;
}
init(N, P);
for (int i = tempMax; i >= 1; --i) {
DFS(i, 0, 0, 0);
}
if (result.size() == 0) {
cout << "Impossible";
return 0;
}
cout << N << " = ";
for (int j = 0; j < K; ++j) {
cout << result[j] << "^" << P;
if (j != K - 1) {
cout << " + ";
}
}
}
哭了都铅忿，最后還是仿造別人的過了剪决，但是查看了一下，思路和優(yōu)化點都一樣檀训。
1127
這個題目也是一個水題柑潦，我的做法可能稍微有點麻煩，是把每一層的數(shù)目記錄下來峻凫，然后按照不同層數(shù)查看是否需要扭轉(zhuǎn)次序渗鬼，方法很笨，但是還是過了荧琼∑┨ィ看到柳神有更好的做法，感興趣可自己搜尋一二命锄。
關(guān)鍵點還是在構(gòu)建樹這里堰乔，中序遍歷和后續(xù)遍歷構(gòu)建一棵樹這些題目見多不怪了，只要下標(biāo)數(shù)對了就好寫脐恩，層次遍歷變形一下即可镐侯。
TreeNode create(int inL, int inR, int postL, int postR, vector<int> inOrder, vector<int> postOrder) {
TreeNode root = nullptr;
root = new treeNode;
if (inL > inR) {
return nullptr;
}
if (inL == inR) {
root->val = inOrder[inL];
root->right = root->left = nullptr;
return root;
}
int rootNum = postOrder[postR];
int index = -1;
for (int i = inL; i <= inR; ++i) {
if (inOrder[i] == rootNum) {
index = i;
break;
}
}
int leftNum = index - inL;
root->val = rootNum;
root->left = create(inL, index - 1, postL, postL + leftNum - 1, inOrder, postOrder);
root->right = create(index + 1, inR, postL + leftNum, postR - 1, inOrder, postOrder);
return root;
}
void zlevel(TreeNode root) {
queue<TreeNode> Queue;
root->depth = 1;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
if (levelOrder.size() < cur->depth + 1) {
vector<int> newDepth;
newDepth.push_back(cur->val);
levelOrder.push_back(newDepth);
} else {
levelOrder[cur->depth].push_back(cur->val);
}
if (cur->left) {
cur->left->depth = cur->depth + 1;
Queue.push(cur->left);
}
if (cur->right) {
cur->right->depth = cur->depth + 1;
Queue.push(cur->right);
}
}
}
1130
按照中序遍歷就好了，水題一道驶冒，沒什么好說的苟翻，注意一些特殊情況就好了韵卤。
void inOrder(TreeNode root, TreeNode parent) {
if (root) {
if ((root->left != nullptr || root->right != nullptr) && root != parent)
result += "(";
inOrder(root->left, parent);
result += root->val;
inOrder(root->right, parent);
if ((root->left != nullptr || root->right != nullptr) && root != parent)
result += ")";
}
}
中序遍歷注意一下即可，只要是等于根的崇猫，那就不用輸出括號沈条。其余的創(chuàng)建樹之前的題目都寫過了。
