注意因为key和value都不会重复出现，所以可以将题目中描述的两个映射关系用一个映射实现 #include <iostream> #include <string> #include <unordered_map> using namespace std; int main() { unordered_map<string, string> dictionary; while (true) { string s; getline(cin, s); if (s == "@END@...

map映射查找问题 #include <iostream> #include <string> #include <map> #include <unordered_map> using namespace std; int main() { int N; cin >> N; getchar(); //读取int类型数字后面的换行符 unordered_map<string, string> umap; while (N--) { string s; ...

采用优先队列解决问题 #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int N; while (cin >> N) { if (N == 0) break; priority_queue<int, vector<int>, greater<int>> pq; while (N--) { int...

需要将去重复考虑进去 #include <iostream> #include <queue> #include <set> using namespace std; int main() { int N; while (cin >> N) { priority_queue<int> pq; vector<int> vec; set<int> st; while (N--) { int val; ...

采用哈夫曼树的思想 在机试中最常考察优先队列的应用便是哈夫曼树(Huffman Tree)。在一颗树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果树中结点带有表示某种意义的权值，那么从根结点到达该结点的带权路径长度再乘以该结点的权值就被称为该结点的带权路径长度。树中所有叶子结点的带权路径长度之和为该树的带权路径长度之和。给定n个带有权值的结点，以它们为叶子结点构造一颗带权路径长度和最小的二叉树，该二叉树即为哈夫曼树，同时也称为最优树。 由于n个带有权值的结点构成的哈夫曼树可能不唯一，所以关于哈夫曼树的机试题往往考察的是求解最小带权路径长度和...

解法一 #include <iostream> #include <vector> #include <queue> #include <string> #include <math.h> using namespace std; struct cmp { pair<double, int> stringToValue(string s) { int pos1 = s.find("+i"); string s1 = s.substr(0, pos1); strin...

并查集思想 本题也可以使用并查集解决。在使用并查集时，只要注意合并函数中需要总是保持点权更大的结点为集合的根结点(原先的合并函数是随意指定其中一个根结点为合并后集合的根结点)，就能符合题目的要求。 而为了达到题目对总边权与成员人数的要求，需要定义两个数组: 一个数组用来存放以当前结点为根结点的集合的总边权（totalWeight）。 另一个数组用来存放以当前结点为根结点的集合中的成员人数（gangs）。 这样当所有通话记录合并处理完毕后，这两个数组就自动存放了每个集合的总边权和成员人数，再根据题意进行筛选即可。 （摘自算法笔记） #include <iostream> #inclu...

先根据前序遍历和中序遍历结果递归建树，再后续遍历 #include <iostream> #include <string> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char c) : data(c), left(NULL), right(NULL) {} }; TreeNode* creatBinaryTree(string pStr, string iStr) { if (pSt...

#include <iostream> #include <vector> using namespace std; struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char c) : val(c), left(nullptr), right(nullptr) {} }; //index参数类型是引用，index需要随着递归次数不断发生变化 TreeNode* creatBinaryTree(string str, int& index)...

并查集 #include <iostream> #include <vector> using namespace std; const int MAXN=1000010; vector<int> s(MAXN, -1); vector<bool> visited(MAXN, false); int Find(vector<int>& s, int x) { int root = x; while (s[root] >= 0) { root = s[root]; } w...

并查集 #include <iostream> #include <vector> #include <string> using namespace std; void Union(vector<int>& s, int a, int b) { //ABC 将A看作B和C的父结点 s[b] = a; } int Find(vector<int>& s, int a, int b) { int cnt = 0; while (s[a] >= 0) { cn...

并查集 这道题需要判断所给出的集合能否构成树，因此不仅需要判断所有节点属于一个集合，还需要判断各个节点是否符合树的定义。 而判断各个节点是否符合树的定义可以转换为判断它的入度是否符合要求，根节点的入度为0，其余节点的入度为1。只要各个节点满足入度要求，只有一个根节点，以及各个节点都属于同一个集合，就可以构成一颗树。 #include <iostream> #include <vector> using namespace std; const int maxN = 10000; vector<int> inDegree(maxN, 0); vector&l...

并查集 #include <iostream> #include <vector> using namespace std; void Initial(vector<int>& s) { for (int i = 1; i < s.size(); i++) { s[i] = -1; } } int Find(vector<int>& s, int x) { int root = x; while (s[root] >= 0) { root = s[ro...

并查集问题 #include <iostream> #include <vector> using namespace std; void Initial(vector<int>& s) { for(int i = 1; i < s.size(); i++) { s[i] = -1; } } int Find(vector<int>& s, int x) { int root = x; while (s[root] >= 0) { root = s[r...