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

2023-12-28 10:25:28

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


编程题

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\

输出样例:

root
  a
    d
      z
      a
    bc
  ab
    cd
    d
  c
  b
#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,即"AB是兄弟结点";
  • A is the parent of B,即"AB的双亲结点";
  • A is the left child of B,即"AB的左孩子";
  • A is the right child of B,即"AB的右孩子";
  • A and B are on the same level,即"AB在同一层上"。

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

输出格式:

对每句陈述,如果正确则输出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);
        else
            creatTree(x * 2 + 1, d + 1);
    }
    return;
}
 
int main()
{
    int n; cin >> n;
    memset(tree, 0x3f, sizeof(tree)); //将每个元素初始化为0x3f3f3f3f
    for (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;
                else
                    cout << "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;
                else
                    cout << "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;
                else
                    cout << "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;
                else
                    cout << "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;
                else
                    cout << "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;
                else
                    cout << "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];
		else
			cout << " " << 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 WPL
		tmp = 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;
		else
			cout <<"No"<<endl;
	}
	return 0;
}

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

文章来源:https://blog.csdn.net/2301_77485708/article/details/135162369
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。