【数据结构入门精讲 | 第十三篇】考研408、公司面试树专项练习（二）

在上一篇中我们进行了树的判断题、选择题、填空题专项练习，在这一篇中我们将进行编程题的相关练习。


目录

    • 编程题
      • R7-1 目录树
      • R7-1 是否同一棵二叉搜索树
      • R7-2 二叉搜索树的结构
      • R7-3 平衡二叉树的根
      • R7-1 完全二叉搜索树
      • R7-1 修理牧场
      • R7-2 嘴强王者
      • R7-3 房屋分拆
      • R7-4 动态区间求和
      • R7-1 哈夫曼编码

编程题

R7-1 目录树

在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。

输入格式:

输入首先给出正整数N（≤104），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：

  • 路径和名称中的字符仅包括英文字母（区分大小写）；
  • 符号“\”仅作为路径分隔符出现；
  • 目录以符号“\”结束；
  • 不存在重复的输入项目；
  • 整个输入大小不超过2MB。

输出格式:

假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。

输入样例:

7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\

输出样例:

rootadzabcabcddcb

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#define MAXN 100010
using namespace std;struct node {string name;int isCata;				// 目录文件标记vector<node*> child;	// 孩子指针
};bool cmp(node* a, node* b) {if(a->isCata != b->isCata)	return a->isCata > b->isCata;else return a->name < b->name;
}void dfs(node* root,int level) {if(root == NULL)	return ;// 先输出自己for(int i  = 0; i < level; ++i)	printf("  ");printf("%s\n",root->name.c_str()) ;// 排序所有孩子 ： 目录在前，文件在后，字典升序sort(root->child.begin(),root->child.end(),cmp);// 向下递归for(int i = 0; i < root->child.size(); ++i)dfs(root->child[i],level+1);}int n;
int main() {scanf("%d",&n);getchar();// 建立根节点 node* root = new node;root->name = "root";root->isCata = 1;string tmp,str;node* curRoot;for(int j = 0; j < n; ++j) {// 每一个新的路径，都将根设为 root curRoot = root;getline(cin,str);for(int i = 0; i <= str.size(); ++i) {if(str[i] == '\\') {	// 情况 1. 是目录  ： 切换当前目录，// 在当前父目录中寻找，看是否存在int flag = 0;for(int k = 0; k < curRoot->child.size(); ++k) {// 1.1 有该目录if(curRoot->child[k]->name == tmp && curRoot->child[k]->isCata == 1) {	// 则切换当前目录curRoot =  curRoot->child[k];flag = 1;break;}}// 1.2 没有该目录则创建一个if(!flag) { // 创建结点node* newnode = new node;newnode->name = tmp;newnode->isCata = 1;// 加入父目录curRoot->child.push_back(newnode) ;// 切换当前目录curRoot = newnode;}// 单词清零tmp.clear();// 情况 2. 是文件}else if(i == str.size()) {		if(!tmp.empty()) {	// 到达最后，而单词不空，说明是文件// 将文件加入到父节点中node* newnode = new node;newnode->name = tmp;newnode->isCata = 0;curRoot->child.push_back(newnode) ;}tmp.clear();} else {						// 情况 3. 累加单词字母tmp += str[i];}}}// 输出过程dfs(root,0);return 0;
}

R7-1 是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct TreeNode *Tree;struct TreeNode{ElementType Data;Tree Left;Tree Right;int flag; //判别一个序列，没被访问设为0，被访问设为1 
};typedef Tree BinTree;BinTree Create(int N);
BinTree NewNode(int V);
BinTree Insert(BinTree T,int V);
int Judge(BinTree T,int N);
int check(BinTree T,int V);
void ResetT(BinTree T);
void FreeTree(BinTree T);int main()
{int N,L,i;BinTree T; scanf("%d",&N);while(N){scanf("%d",&L);T = Create(N);for(i = 0; i < L;i++){if(Judge(T,N)) printf("Yes\n");else printf("No\n");ResetT(T); /* 清除T中的标记flag*/}FreeTree(T); /* 比较完一组就释放*/scanf("%d",&N);}
}
void FreeTree(BinTree T)
{if(T->Left)  FreeTree(T->Left);if(T->Right)  FreeTree(T->Right);free(T);
}void ResetT(BinTree T)
{if(T->Left)  ResetT(T->Left);if(T->Right)  ResetT(T->Right);T->flag = 0;}BinTree Create(int N)
{BinTree T = NULL;int V,i;scanf("%d",&V);T = NewNode(V);for(i = 0;i < N-1;i++){scanf("%d",&V);T = Insert(T,V);}return T;}BinTree NewNode(int V)
{BinTree BT;BT = (BinTree)malloc(sizeof(struct TreeNode));BT->Data = V;BT->Left = NULL;BT->Right = NULL;BT->flag = 0;return BT;
}
BinTree Insert(BinTree T,int V)
{BinTree TNode;if(!T) T = NewNode(V);else{if(T->Data < V){T->Right = Insert(T->Right,V);}if(T->Data > V){T->Left = Insert(T->Left,V);}}return T;}/*当发现序列中的某个数和T不一样，必须把序列后面的数都读完*/
int Judge(BinTree T,int N)
{int i;int V;int flag = 0;/*flag:0 代表目前一致 flag:1 代表已经不一致  */scanf("%d",&V);if(V!=T->Data) flag = 1;else T->flag = 1;for (i = 1; i < N;i++){scanf("%d",&V);/* 若check为0，则return 0；之前出现的节点没有被访问过，出现新的节点，所以树不一致*/if(!flag && !check(T,V)) flag = 1;}if(flag)return 0;else return 1;}
int check(BinTree T,int V)
{if(T->flag){if(V > T->Data) return check(T->Right,V);if(V < T->Data) return check(T->Left,V);// 若相等，则说明之前已经出现过一个相同的数，则两个树不一致if(V == T->Data) return 0; }else{if(V == T->Data) {T->flag = 1;return 1;}else{return 0;}}
}

R7-2 二叉搜索树的结构

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：

  • A is the root，即"A是树的根"；
  • A and B are siblings，即"A和B是兄弟结点"；
  • A is the parent of B，即"A是B的双亲结点"；
  • A is the left child of B，即"A是B的左孩子"；
  • A is the right child of B，即"A是B的右孩子"；
  • A and B are on the same level，即"A和B在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

输入样例：

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例：

Yes
Yes
Yes
Yes
Yes
No
No
No

#include <iostream>
#include <string>
#include <string.h>
#include <map>
using namespace std;const int MAX = 1e7 + 10;
int tree[MAX]; //二叉搜索树
int deepth[MAX]; //结点深度
int tem;
map<int, int> num; //键值对应的结点编号void creatTree(int x, int d) //建立二叉搜索树
{if (tree[x] == 0x3f3f3f3f){tree[x] = tem;num.insert(make_pair(tem, x));deepth[x] = d;}else{if (tem < tree[x])creatTree(x * 2, d + 1);elsecreatTree(x * 2 + 1, d + 1);}return;
}int main()
{int n; cin >> n;memset(tree, 0x3f, sizeof(tree)); //将每个元素初始化为0x3f3f3f3ffor (int i = 0; i < n; i++){cin >> tem;creatTree(1, 1);}int k; cin >> k;while (k--){string str;int a, b;cin >> a >> str;if (str == "and"){cin >> b >> str >> str;if (str == "siblings"){if (num.find(a) == num.end() || num.find(b) == num.end())cout << "No" << endl;else if (num[a] / 2 == num[b] / 2)cout << "Yes" << endl;elsecout << "No" << endl;}else{getline(cin, str);if (num.find(a) == num.end() || num.find(b) == num.end())cout << "No" << endl;else if (deepth[num[a]] == deepth[num[b]])cout << "Yes" << endl;elsecout << "No" << endl;}}else{cin >> str >> str;if (str == "root"){if (num.find(a) == num.end())cout << "No" << endl;else if (num[a] == 1)cout << "Yes" << endl;elsecout << "No" << endl;}else if (str == "parent"){cin >> str >> b;if (num.find(a) == num.end() || num.find(b) == num.end())cout << "No" << endl;else if (num[a] == num[b] / 2)cout << "Yes" << endl;elsecout << "No" << endl;}else if (str == "left"){cin >> str >> str >> b;if (num.find(a) == num.end() || num.find(b) == num.end())cout << "No" << endl;else if (num[b] * 2 == num[a])cout << "Yes" << endl;elsecout << "No" << endl;}else{cin >> str >> str >> b;if (num.find(a) == num.end() || num.find(b) == num.end())cout << "No" << endl;else if (num[b] * 2 + 1 == num[a])cout << "Yes" << endl;elsecout << "No" << endl;}}}return 0;
}

R7-3 平衡二叉树的根

将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。

输入格式:

输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。

输出格式:

在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。

输入样例1:

5
88 70 61 96 120

输出样例1:

70

输入样例2:

7
88 70 61 96 120 90 65

输出样例2:

88

#include <iostream>
using namespace std;struct Node {int data;Node* lc;Node* rc;
};int height(Node* T) {return T == NULL ? 0 : max(height(T->lc), height(T->rc)) + 1;
}Node* turn1(Node* T) { //单向右旋Node* A = T->lc;T->lc = A->rc;A->rc = T;return A;
}Node* turn2(Node* T) { //单向左旋Node* A = T->rc;T->rc = A->lc;A->lc = T;return A;
}Node* turn3(Node* T) { //先左旋后右旋T->lc = turn2(T->lc);return turn1(T);
}Node* turn4(Node* T) { //先右旋后左旋T->rc = turn1(T->rc);return turn2(T);
}Node* Insert(Node* T, int x) {if (!T)T = new Node({ x,NULL,NULL });else if (x < T->data) {T->lc = Insert(T->lc, x);if (height(T->lc) - height(T->rc) == 2)T = (x < T->lc->data ? turn1(T) : turn3(T));}else if (x > T->data) {T->rc = Insert(T->rc, x);if (height(T->lc) - height(T->rc) == -2)T = (x > T->rc->data ? turn2(T) : turn4(T));}return T;
}int main() {Node* Tree = NULL;int n, t;cin >> n;while (n--) {cin >> t;Tree = Insert(Tree, t);}cout << Tree->data << endl;return 0;}

R7-1 完全二叉搜索树

一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。

输入格式：

首先第一行给出一个正整数 N（≤1000），随后第二行给出 N 个不重复的非负整数。数字间以空格分隔，所有数字不超过 2000。

输出格式：

在一行中输出这棵树的层序遍历序列。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10
1 2 3 4 5 6 7 8 9 0

输出样例：

6 3 8 1 5 7 9 0 2 4

#include <iostream>
#include <algorithm>
using namespace std;int in[1001];
int res[1001];
int n,len;void dfs(int i){if(i>n)return;dfs(2*i);res[i] = in[++len];dfs(2*i+1);
} int main(){cin >> n;for(int i = 1;i<=n;i++){cin >> in[i];}sort(in+1,in+1+n);dfs(1);for(int i = 1;i<=n;i++){if(i==1)cout << res[i];elsecout << " " << res[i];}return 0;
}

R7-1 修理牧场

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

输入首先给出正整数N（≤104），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成N块的最少花费。

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

49

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx=1e18;
const int N=1E6+100;
const int p=1e4;
const double eps =1e-8;priority_queue<int,vector<int>,greater<int>>pmin;
int n,t,sum;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>t;pmin.push(t);}while(pmin.size()!=1){int k1,k2;k1=pmin.top();pmin.pop();k2=pmin.top();pmin.pop();sum+=(k1+k2);pmin.push(k1+k2);}cout<<sum;
}

R7-2 嘴强王者

在召唤师峡谷中，优秀的召唤师总是喜欢比较自己的战斗力强弱，而青铜召唤师也不甘示弱，他们比较嘴炮的强弱。由于他们的嘴炮水平总是不断变化，难以通过人工进行比较，因此请你帮他们开发一个算法，找出其中的嘴强王者。

输入格式:

第一行两个正整数n,m，表示有n个选手，m次操作（1≤n≤105,1≤m≤5000)。

第二行有n个整数，分别表示第i个选手的初始嘴炮值ai；选手的编号从1到n。

接下来有m行，每行三个正整数x,l,r;

当x=1时，这是一个询问操作，询问区间[l,r]里面嘴炮值最高的召唤师，即嘴强王者；

当x=0时，这是一个更新操作，表示选手l的嘴炮值更新为r。

题目保证在每个查询区间内，嘴强王者是唯一的。

输出格式:

对于每个询问操作，在一行里面输出里面的嘴强王者的编号及其嘴炮值，用用空格分隔，行末没有多余空格。

输入样例:

5 6
1 2 3 4 5
1 1 5
0 3 6
1 3 4
1 4 5
0 2 9
1 1 5

输出样例:

在这里给出相应的输出。例如：

5 5
3 6
5 5
2 9

#include<bits/stdc++.h>
#include<math.h>
using namespace std;int n, m;
int v[18][1 << 17];
int h = 1;void build() {for (int i = 1; i <= h; i++) {int span = pow(2, i);for (int j = 1; j <= n; j += span) {v[i][j] = max(v[i - 1][j], v[i - 1][j + (span / 2)]);}}
}int update(int index, int val, int ll, int rr) {int idx = log2(rr - ll + 1);int mid = (ll + rr) / 2;if (ll > index || rr < index) return v[idx][ll];if (ll == rr) {if (ll == index) {v[0][index] = val;return val;}else return v[0][ll];}// 更新最大值return v[idx][ll] = max(update(index, val, ll, mid), update(index, val, mid + 1, rr));
}int find(int l, int r, int ll, int rr) {if (rr < l || ll > r) return 0;int idx = log2(rr - ll + 1);if (ll >= l && rr <= r) return v[idx][ll];int mid = (ll + rr) / 2;return max(find(l, r, ll, mid), find(l, r, mid + 1, rr));
}int main() {cin >> n >> m;while (pow(2, h) < n) h++;map<int, set<int>> mp; // 用来记录下标的小技巧for (int i = 1; i <= n; i++) {cin >> v[0][i];mp[v[0][i]].insert(i);}build();for (int i = 0; i < m; i++) {int x, l, r;cin >> x >> l >> r;if (x == 1) {int ans = find(l, r, 1, pow(2, h));int idx = *mp[ans].lower_bound(l); // 二分快速查找当前的下标cout << idx << " " << ans << endl;}else {mp[v[0][l]].erase(l); // 更新时删除原来的下标mp[r].insert(l); // 添加新的下标update(l, r, 1, pow(2, h));}}return 0;
}

R7-3 房屋分拆

厂长买了一整间房屋作为车间，现准备将整个房屋分成若干个车间。装修公司规定分拆房屋的价格等于被分拆房屋的面积。如想将面积为200的房间分拆为面积为80、70和50的三个车间，第一次将房屋分拆为面积120和80的两个房间，花费200，第二次将面积为120的房间分拆为面积为70和50的两个房间，花费120，总花费为320。如果采用另一种方案，第一次将面积200的房屋分拆为150和50，花费200，第二次将面积为150的房间分拆为80和70的房间，花费150，则总花费为350。显然第一种方案花费更少。请编写程序为厂长设计花费最少的分拆方案。

输入格式:

输入为两行，第一行为一个整数n，表示所需的车间数量。第二行为n个正整数，以空格间隔，给出每个车间需要的面积。n不超过100000，且保证最终结果小于231。

输出格式:

输出为一个整数，表示将整个房屋分拆为n个车间所需的最少花费。

输入样例:

8
1 1 1 1 2 3 4 5

输出样例:

49

#include<stdio.h>
#include<stdlib.h>
typedef struct Node * Heap; /*堆结构*/
struct Node
{int * Data;int Size;
};
typedef Heap MinHeap;/*最小堆*/
Heap CreateHeap(int n)//最小堆的创建
{MinHeap H=(MinHeap)malloc(sizeof(struct Node));H->Data=(int *)malloc(2*(n+1)*sizeof(int));H->Size=0;//初始化 H->Data[0]=0;/*最小堆的哨兵*/return H;
}
void Insert(Heap H,int m)//建初堆
{int i;i=++H->Size;for(; H->Data[i/2]>m; i/=2)H->Data[i]=H->Data[i/2];H->Data[i]=m;
}
int Del(Heap H)//重建小跟堆
{int parent,child;int min,x;min=H->Data[1];x=H->Data[H->Size--];//用最后一个元素替代已经输出的堆顶元素for(parent=1; parent*2<=H->Size ; parent=child) //沿较小的孩子向下筛选{{child=parent*2;if((child!=H->Size)&&(H->Data[child]>H->Data[child+1])) child++;if(H->Data[child]>=x) break;else H->Data[parent]=H->Data[child];}
H->Data[parent]=x;
return min;
}
int main()
{int n,m,i,sum=0,a,b;scanf("%d",&n);Heap H=CreateHeap(n);for(i=1; i<=n; i++){scanf("%d",&m);Insert(H,m);/*将所有元素入堆(H)*/}while(H->Size!=1){a=Del(H);//去掉最小值再重建堆b=Del(H);//去掉次小值再重建堆b=a+b;sum+=b;//不断累加求和Insert(H,b);}printf("%d\n",sum);
// 	system("pause");return 0; 
}

R7-4 动态区间求和

在这里插入图片描述

输入样例:

3 2
1 2 3
1 2 0
2 1 3

输出样例:

6

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;typedef long long ll;
const int MAXN = 1e6 + 5;
ll n, q, c[MAXN];//树状数组， 下标为某一个元素， 值为这个元素出现的次数int lowbit(int x) {return x&(-x);
}//update将第x个整数加上v
void update(int x, int v)
{for (int i = x; i <= n; i += lowbit(i)) {c[i] += v;}
}//getSum返回前x个整数之和
ll getSum(int x) { ll sum = 0;for (int i = x; i > 0; i -= lowbit(i)) {sum += c[i];}return sum;
}int main()
{cin >> n >> q;memset(c, 0, sizeof(c));for (int i = 1; i <= n; i++) {int temp;cin >> temp;update(i, temp);}while (q--){int a, b, c;cin >> a >> b >> c;if (a == 1) {update(b, c);}else if (a == 2) {cout << getSum(c) - getSum(b - 1) << endl;}}
}

R7-1 哈夫曼编码

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c[1] f[1] c[2] f[2] ... c[N] f[N]

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c[i] code[i]

其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。

输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

输入样例：

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

输出样例：

Yes
Yes
No
No

#include<iostream>
#include<queue>
#include<vector>
#include<string> 
#include<map>
using namespace std;int c[100],f[100],n,m;
string code[100];//存储序列
char ch[100];
map<char,int> mp;bool check(int WPL){int a,b,wpl = 0;for(int i = 0;i<n;++i){for(int j = i+1;j<n;++j){a = code[i].find(code[j]);//前缀判断，存在则返回第一个位置，否则返回最后一个位置b = code[j].find(code[i]);if((a==0) || (b==0)){return false;}}wpl+=mp[ch[i]]*code[i].length();//计算当前wpl}if(wpl==WPL) return true;else return false;
}int main(){cin>>n;priority_queue<int,vector<int>,greater<int> > pqu;//优先队列，排序for(int i = 0;i<n;++i){scanf(" %c %d",&c[i],&f[i]);pqu.push(f[i]);mp[c[i]] = f[i];//存储字母的权值}int WPL= 0,tmp = 0;while(pqu.size()>1){//compute WPLtmp = pqu.top();pqu.pop();tmp+=pqu.top();pqu.pop();WPL+=tmp;pqu.push(tmp);}cin >> m;for(int i = 0;i<m;++i){for(int j = 0;j<n;++j){scanf(" %c",&ch[j]);cin >>code[j];}if(check(WPL))cout <<"Yes"<<endl;elsecout <<"No"<<endl;}return 0;
}

至此，树的编程题就结束了，在下一篇中我们将介绍散列表的相关知识点。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/223145.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Django 简单图书管理系统

Django 简单图书管理系统

一、图书需求 1. 书籍book_index.html中有超链接&#xff1a;查看所有的书籍列表book_list.html页面 2. 书籍book_list.html中显示所有的书名&#xff0c;有超链接&#xff1a;查看本书籍详情book_detail.html(通过书籍ID)页面 3. 书籍book_detail.html中书的作者和出版社&…
阅读更多...
Stable Diffusion系列（三）：网络分类与选择

Stable Diffusion系列（三）：网络分类与选择

文章目录 网络分类模型基座模型衍生模型二次元模型2.5D模型写实风格模型 名称解读 VAELora嵌入文件放置界面使用 网络分类 当使用SD webui绘图时&#xff0c;为了提升绘图质量&#xff0c;可以多种网络混合使用&#xff0c;可选的网络包括了模型、VAE、超网络、Lora和嵌入。 …
阅读更多...
Vue3视图渲染技术(2)

Vue3视图渲染技术(2)

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 本…
阅读更多...
kubernetes集群 应用实践 kafka部署

kubernetes集群 应用实践 kafka部署

kubernetes集群 应用实践 kafka部署 零.1、环境说明 零.2、kafka架构说明 zookeeper在kafka集群中的作用 一、Broker注册 二、Topic注册 三、Topic Partition选主 四、生产者负载均衡 五、消费者负载均衡 一、持久化存储资源准备 1.1 创建共享目录 [rootnfsserver ~]# mkdir -…
阅读更多...
医学实验室检验科LIS信息系统源码

医学实验室检验科LIS信息系统源码

实验室信息管理是专为医院检验科设计的一套实验室信息管理系统&#xff0c;能将实验仪器与计算机组成网络&#xff0c;使病人样品登录、实验数据存取、报告审核、打印分发&#xff0c;实验数据统计分析等繁杂的操作过程实现了智能化、自动化和规范化管理。 实验室管理系统功能介…
阅读更多...
阿里云ECS配置IPv6后，如果无法访问该服务器上的网站，可检查如下配置

阿里云ECS配置IPv6后，如果无法访问该服务器上的网站，可检查如下配置

1、域名解析到这个IPv6地址,同一个子域名可以同时解析到IPv4和IPv6两个地址&#xff0c;这样就可以给网站配置ip4和ipv6双栈&#xff1b; 2、在安全组规则开通端口可访问&#xff0c;设定端口后注意授权对象要特殊设置“源:::/0” 3、到服务器nginx配置处&#xff0c;增加端口…
阅读更多...
二值选择模型-以stata为工具

二值选择模型-以stata为工具

二值选择模型-以stata为工具 文章目录 1. 命令语法2. 模型 代码示例2.1 读取数据2.2 建立模型2.3 数据预测1. 命令语法 二值选择模型是计量经济学中常用的一种模型，用于处理因变量为二值（0或1）的情况。 这种模型通常用来研究个体在面临两个或多个离散选择时的决策行为。其中…
阅读更多...
Mybatis之增删改查

Mybatis之增删改查

目录 一、引言 二、Mybatis——增 举例&#xff1a;添加用户 三、Mybatis——删 举例&#xff1a;删除用户 四、Mybatis——改 举例&#xff1a;修改用户 五、Mybatis——查 六、注意 END&#xff1a; 一、引言 书接上回&#xff0c;我们在了解完mybatis之后&#xff0c;肯…
阅读更多...
会员管理怎么做？

会员管理怎么做？

会员管理是企业运营的重要组成部分&#xff0c;它涉及到会员的招募、维护、激励、保留、转化等多个环节。下面&#xff0c;我们将结合具体的案例&#xff0c;详细介绍会员管理的具体做法。 首先&#xff0c;会员的招募是会员管理的第一步 企业需要通过各种方式吸引消费者成为会…
阅读更多...
【大数据】NiFi 中的 Controller Service

【大数据】NiFi 中的 Controller Service

NiFi 中的 Controller Service 1.Service 简介1.1 Controller Service 的配置1.1.1 SETTING 基础属性1.1.2 PROPERTIES 使用属性1.1.3 COMMENT 页签 1.2 Service 的使用范围 2.全局参数配置3.DBCPConnectionPool 的使用样例4.在 ExcuseGroovyScript 组件中使用 Service 1.Servi…
阅读更多...
【Prometheus|报错】Out of bounds

【Prometheus|报错】Out of bounds

【背景】进入Prometheus地址的9090端口&#xff0c;pushgateway&#xff08;0/1&#xff09;error : out of bounds 【排查分析】 1、out of bounds报错&#xff0c;是由于Prometheus向tsdb存数据出错&#xff0c;与最新存数据的时间序列有问题&#xff0c;有可能当前时间与最…
阅读更多...
步兵 cocos2dx 加密和混淆

步兵 cocos2dx 加密和混淆

文章目录 摘要引言正文代码加密具体步骤代码加密具体步骤测试和配置阶段IPA 重签名操作步骤 总结参考资料 摘要 本篇博客介绍了针对 iOS 应用中的 Lua 代码进行加密和混淆的相关技术。通过对 Lua 代码进行加密处理&#xff0c;可以确保应用代码的安全性&#xff0c;同时提高性…
阅读更多...
小白入门之安装MYSQL

小白入门之安装MYSQL

重生之我在大四学JAVA 第三章 安装MYSQL 把MySQL复制到要安装的路径下解压 到解压后的bin路径下复制路径 接着以“管理员”身份打开命令行(如下图所示) 注意&#xff1a;一定要是管理员身份&#xff0c;否则由于后续部分命令需要权限&#xff0c;出现错误&#xff01; 转到…
阅读更多...
C# .Net学习笔记—— Expression 表达式目录树

C# .Net学习笔记—— Expression 表达式目录树

目录 一、什么是表达式目录树 二、Func与Expression的区别 1、Func是方法 3、使用ILSpy反编译解析看一下 ​编辑 ​编辑 4、拼装练习 5、动态生成硬编码&#xff08;通用、性能好&#xff09; 5、表达式目录树动态生成的用途&#xff1a; 6、递归解析表达式目录树 7、…
阅读更多...
凸优化 2：如何判定凸函数？

凸优化 2：如何判定凸函数？

凸优化 2&#xff1a;如何判定凸函数&#xff1f; 如何判断一个目标函数是凸函数&#xff1f;如果是凸函数&#xff0c;那ta的定义域是凸集合 一个函数求俩次梯度&#xff0c;大于等于0&#xff0c;那这个函数就是一个凸函数在同样条件下&#xff0c;怎么设计为凸函数模型&…
阅读更多...
Go后端开发 -- 环境搭建

Go后端开发 -- 环境搭建

Go后端开发 – 环境搭建 文章目录 Go后端开发 -- 环境搭建一、环境配置二、IDE的选择三、使用go mod构建项目1.初始化项目2.添加依赖项3.运行项目 四、环境报错1.VS Code中gopls报错 一、环境配置 Go官网下载地址&#xff1a;https://golang.org/dl/ https://go.dev/dl/ Go官方…
阅读更多...
安装nodejs，配置环境变量并将npm设置淘宝镜像源

安装nodejs，配置环境变量并将npm设置淘宝镜像源

安装nodejs并将npm设置淘宝镜像源 1. 下载nodejs 个人不喜欢安装包&#xff0c;所以是下载zip包的方式。这里我下载的node 14解压包版本 下载地址如下&#xff1a;https://nodejs.org/dist/v14.15.1/node-v14.15.1-win-x64.zip 想要其他版本的小伙伴去https://nodejs.org/di…
阅读更多...
nodejs+vue+ElementUi资源互助共享平台的设计

nodejs+vue+ElementUi资源互助共享平台的设计

后台&#xff1a;管理员功能有个人中心&#xff0c;用户管理&#xff0c;卖家管理&#xff0c;咨询师管理&#xff0c;萌宝信息管理&#xff0c;幼儿知识管理&#xff0c;保姆推荐管理&#xff0c;音频资源管理&#xff0c;二手商品管理&#xff0c;商品分类管理&#xff0c;资…
阅读更多...
第26关 K8s日志收集揭秘：利用Log-pilot收集POD内业务日志文件

第26关 K8s日志收集揭秘：利用Log-pilot收集POD内业务日志文件

------> 课程视频同步分享在今日头条和B站 大家好&#xff0c;我是博哥爱运维。 OK&#xff0c;到目前为止&#xff0c;我们的服务顺利容器化并上了K8s&#xff0c;同时也能通过外部网络进行请求访问&#xff0c;相关的服务数据也能进行持久化存储了&#xff0c;那么接下来…
阅读更多...
管理 Jenkins 详细指南

管理 Jenkins 详细指南

目录 系统配置 安全 状态信息 故障 排除 工具和操作 系统配置 系统&#xff0c;配置全局设置和路径&#xff0c;端口更改&#xff0c;下载地址等。 工具&#xff0c;配置工具、其位置和自动安装程序。 插件&#xff0c;添加、删除、禁用或启用可以扩展 Jenkins 功能的插…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023