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

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


编程题

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;
}

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

目录
相关文章
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
48 0
|
1月前
|
存储 缓存 算法
数据结构从入门到精通——链表
链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是,它不需要在内存中连续存储,因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择,尤其是在需要动态调整数据结构大小的场景中。
69 0
|
1月前
|
存储 消息中间件 算法
数据结构从入门到精通——顺序表
顺序表是一种常见的线性数据结构,它使用一段连续的存储单元依次存储数据元素。这种数据结构的特点是逻辑上相邻的元素在物理存储位置上也相邻,因此可以快速地访问表中的任意元素。 顺序表的实现通常依赖于数组,数组是一种静态的数据结构,一旦创建,其大小就是固定的。这意味着在顺序表中插入或删除元素可能会导致空间的浪费或不足。例如,如果在一个已经满了的顺序表中插入一个新元素,就需要重新分配更大的数组空间,并将原有元素复制到新数组中,这是一个相对耗时的操作。
51 0
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——算法的时间复杂度和空间复杂度
算法的时间复杂度和空间复杂度是评估算法性能的两个重要指标。时间复杂度主要关注算法执行过程中所需的时间随输入规模的变化情况,而空间复杂度则关注算法执行过程中所需的最大存储空间或内存空间。
60 0
|
17天前
|
存储 缓存 算法
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
最重要的是保持自信和冷静。提前准备,并对自己的知识和经验有自信,这样您就能在面试中展现出最佳的表现。祝您面试顺利!Java 是一种广泛使用的面向对象编程语言,在软件开发领域有着重要的地位。Java 提供了丰富的库和强大的特性,适用于多种应用场景,包括企业应用、移动应用、嵌入式系统等。下是几个面试技巧:复习核心概念、熟悉常见问题、编码实践、项目经验准备、注意优缺点、积极参与互动、准备好问题问对方和知其所以然等,多准备最好轻松能举一反三。
46 0
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
|
20天前
|
存储 NoSQL Java
Redis 数据结构操作入门
Redis 数据结构操作入门
15 0
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——队列
队列是一种特殊的线性数据结构,遵循先入先出(FIFO)的原则。它只允许在队列的末尾添加元素(称为入队操作),并从队列的开头移除元素(称为出队操作)。队列在多种应用中发挥着重要作用,如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。
46 0
|
18天前
|
Java 程序员
java线程池讲解面试
java线程池讲解面试
35 1
|
2月前
|
存储 关系型数据库 MySQL
2024年Java秋招面试必看的 | MySQL调优面试题
随着系统用户量的不断增加,MySQL 索引的重要性不言而喻,对于后端工程师,只有在了解索引及其优化的规则,并应用于实际工作中后,才能不断的提升系统性能,开发出高性能、高并发和高可用的系统。 今天小编首先会跟大家分享一下MySQL 索引中的各种概念,然后介绍优化索引的若干条规则,最后利用这些规则,针对面试中常考的知识点,做详细的实例分析。
235 0
2024年Java秋招面试必看的 | MySQL调优面试题
|
2月前
|
存储 算法 Java
铁子,你还记得这些吗----Java基础【拓展面试常问题型】
铁子,你还记得这些吗----Java基础【拓展面试常问题型】
45 1