终于终于更上进度了，这一期又会带来最新的五道题目，终于更上姥姥更新的进度了，最近做题目越来越有感觉了，今天一共做了四个小时多的PTA，直接AC两道题+有一道题只差一分满分了（话说我的舍友都在刷字节跳动面试题还有Leetcode了，真的牛人）。话不多说，跟随我去看看本期的五道题把。

二叉搜索树的操作集

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1505905647748263936
这题的难点主要在于树的删除操作，在写代码之前一定要想清楚树的删除操作过程是怎么实现的，想通了就好写多了。如果想通了还是实现不了，说明不是理解数据结构不到位，而是不会写代码（这种的话还是推荐把C++基础打好再来把）。友情提醒，在树的问题中经常要做结点的判断，提前判断结点是否为NULL,否则就会出现访问错误。
代码如下：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. typedef int ElementType;
  5. typedef struct TNode *Position;
  6. typedef Position BinTree;
  7. struct TNode{
  8.     ElementType Data;
  9.     BinTree Left;
  10.     BinTree Right;
  11. };
  13. void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
  14. void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */
  16. BinTree Insert( BinTree BST, ElementType X );
  17. BinTree Delete( BinTree BST, ElementType X );
  18. Position Find( BinTree BST, ElementType X );
  19. Position FindMin( BinTree BST );
  20. Position FindMax( BinTree BST );
  22. int main()
  23. {
  24.     BinTree BST, MinP, MaxP, Tmp;
  25.     ElementType X;
  26.     int N, i;
  28.     BST = NULL;
  29.     scanf("%d", &N);
  30.     for ( i=0; i<N; i++ ) {
  31.         scanf("%d", &X);
  32.         BST = Insert(BST, X);
  33.     }
  34.     printf("Preorder:"); PreorderTraversal(BST); printf("\n");
  35.     MinP = FindMin(BST);
  36.     MaxP = FindMax(BST);
  37.     scanf("%d", &N);
  38.     for( i=0; i<N; i++ ) {
  39.         scanf("%d", &X);
  40.         Tmp = Find(BST, X);
  41.         if (Tmp == NULL) printf("%d is not found\n", X);
  42.         else {
  43.             printf("%d is found\n", Tmp->Data);
  44.             if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
  45.             if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
  46.         }
  47.     }
  48.     scanf("%d", &N);
  49.     for( i=0; i<N; i++ ) {
  50.         scanf("%d", &X);
  51.         BST = Delete(BST, X);
  52.     }
  53.     printf("Inorder:"); InorderTraversal(BST); printf("\n");
  55.     return 0;
  56. }
  57. /* 你的代码将被嵌在这里 */
  58. Position FindMax2( BinTree BST );
  59. Position FindMin2( BinTree BST );
  60. BinTree Insert( BinTree BST, ElementType X ){
  61.     if(BST == NULL){
  62.         BST = (BinTree)malloc(sizeof(struct TNode));
  63.         BST->Data = X;
  64.         BST->Left = NULL;
  65.         BST->Right = NULL;
  66.         return BST;
  67.     }
  68.     BinTree temp = BST;
  69.     while(1){
  70.         if(X >= temp->Data){
  71.             if(temp->Right != NULL)
  72.                 temp = temp->Right;
  73.             else{
  74.                 temp->Right = (BinTree)malloc(sizeof(struct TNode));
  75.                 temp = temp->Right;
  76.                 temp->Data = X;
  77.                 temp->Left = NULL;
  78.                 temp->Right = NULL;
  79.                 break;
  80.             }
  81.         }
  82.         else{
  83.             if(temp->Left != NULL)
  84.                 temp = temp->Left;
  85.             else{
  86.                 temp->Left = (BinTree)malloc(sizeof(struct TNode));
  87.                 temp = temp->Left;
  88.                 temp->Data = X;
  89.                 temp->Left = NULL;
  90.                 temp->Right = NULL;
  91.                 break;
  92.             }
  93.         }
  94.     }
  95.     return BST;
  96. }
  97. Position Find( BinTree BST, ElementType X ){
  98.     BinTree temp = BST;
  99.     while(1){
  100.         if(temp == NULL)
  101.             return NULL;
  102.         if(temp->Data == X)
  103.             return temp;
  104.         else{
  105.             if(X > temp->Data){
  106.                 if(temp->Right != NULL)
  107.                     temp = temp->Right;
  108.                 else
  109.                     return NULL;
  110.             }
  111.             else{
  112.                 if(temp->Left != NULL)
  113.                     temp = temp->Left;
  114.                 else
  115.                     return NULL;
  116.             }
  117.         }
  118.     }
  119. }
  120. Position Find2( BinTree BST, ElementType X ){
  121.     BinTree temp = BST;
  122.     BinTree temp2 = NULL;
  123.     while(1){
  124.         if(temp == NULL)
  125.             return NULL;
  126.         if(temp->Data == X)
  127.             return temp2;
  128.         else{
  129.             if(X > temp->Data){
  130.                 if(temp->Right != NULL){
  131.                     temp2 = temp;
  132.                     temp = temp->Right;
  133.                 }
  134.                 else
  135.                     return NULL;
  136.             }
  137.             else{
  138.                 if(temp->Left != NULL){
  139.                     temp2 = temp;
  140.                     temp = temp->Left;
  141.                 }
  142.                 else
  143.                     return NULL;
  144.             }
  145.         }
  146.     }
  147. }
  148. BinTree Delete( BinTree BST, ElementType X ){
  149.     BinTree temp = Find(BST,X);
  150.     if(temp == NULL){
  151.         printf("Not Found\n");
  152.         return BST;
  153.     }
  154.     BinTree temp2 = Find2(BST,X);
  155.     if(temp->Left == NULL && temp->Right == NULL){
  156.         if(temp2 == NULL){
  157.             BST = NULL;
  158.         }
  159.         else if(temp2->Left == temp){
  160.             temp2->Left = NULL;
  161.         }
  162.         else{
  163.             temp2->Right = NULL;
  164.         }
  165.         //printf("Found\n");
  166.         return BST;
  167.     }
  168.     else if(temp->Left != NULL && temp->Right == NULL){
  169.         if(temp2 == NULL){
  170.             BST = temp->Left;
  171.         }
  172.         else if(temp2->Left == temp){
  173.             temp2->Left = temp->Left;
  174.         }
  175.         else{
  176.             temp2->Right = temp->Left;
  177.         }
  178.         //printf("Found\n");
  179.         return BST;
  180.     }
  181.     else if(temp->Left == NULL && temp->Right != NULL){
  182.         if(temp2 == NULL){
  183.             BST = temp->Right;
  184.         }
  185.         else if(temp2->Left == temp){
  186.             temp2->Left = temp->Right;
  187.         }
  188.         else{
  189.             temp2->Right = temp->Right;
  190.         }
  191.         //printf("Found\n");
  192.         return BST;
  193.     }
  194.     else{
  195.         if((temp->Right)->Left == NULL){
  196.             if(temp2 == NULL){
  197.                 BinTree t1 = BST->Left;
  198.                 BST = BST->Right;
  199.                 BST->Left = t1;
  200.                 //printf("Found\n");
  201.                 return BST;
  202.             }
  203.             else{
  204.                 if(temp2->Left == temp){
  205.                     temp2->Left = temp->Right;
  206.                     (temp->Right)->Left = temp->Left;
  207.                 }
  208.                 else{
  209.                     temp2->Right = temp->Right;
  210.                     (temp->Right)->Left = temp->Left;
  211.                 }
  212.             }
  213.         }
  214.         else if(((temp->Right)->Left)->Left == NULL && ((temp->Right)->Left)->Right == NULL){
  215.             if(temp2 == NULL){
  216.                 BinTree t5 = BST->Left;
  217.                 BinTree t6 = BST->Right;
  218.                 BST = (temp->Right)->Left;
  219.                 BST->Left = t5;
  220.                 BST->Right = t6;
  221.                 (BST->Right)->Left = NULL;
  222.             }
  223.             else{
  225.             }
  226.         }
  227.         else if(((temp->Right)->Left)->Left != NULL){
  228.             BinTree t3 = FindMin((temp->Right)->Left);
  229.             BinTree t4 = FindMin2((temp->Right)->Left);
  230.             if(temp2 == NULL){
  231.                 BinTree t5 = BST->Left;
  232.                 BinTree t6 = BST->Right;
  233.                 BST = t3;
  234.                 BST->Left = t5;
  235.                 BST->Right = t6;
  236.                 if(t4 == NULL){
  237.                     (BST->Right)->Left = NULL;
  238.                 }
  239.                 else{
  240.                     if(t4->Left == t3)
  241.                         t4->Left = NULL;
  242.                     else
  243.                         t4->Right = NULL;
  244.                 }
  245.             }
  246.             else{
  248.             }
  249.         }
  250.         else{
  251.             BinTree t3 = FindMax((temp->Right)->Left);
  252.             BinTree t4 = FindMax2((temp->Right)->Left);
  253.             if(temp2 == NULL){
  254.                 BinTree t5 = BST->Left;
  255.                 BinTree t6 = BST->Right;
  256.                 BST = t3;
  257.                 BST->Left = t5;
  258.                 BST->Right = t6;
  259.                 if(t4 == NULL){
  260.                     (BST->Right)->Left = NULL;
  261.                 }
  262.                 else{
  263.                     if(t4->Left == t3)
  264.                         t4->Left = NULL;
  265.                     else
  266.                         t4->Right = NULL;
  267.                 }
  268.             }
  269.             else{
  271.             }
  272.         }
  273.         //printf("Found\n");
  274.         //PreorderTraversal(BST);
  275.         return BST;
  276.     }
  277. }
  278. Position FindMin( BinTree BST ){
  279.     BinTree temp = BST;
  280.     if(temp == NULL)
  281.         return BST;
  282.     while(1){
  283.         if(temp->Left != NULL)
  284.             temp = temp->Left;
  285.         else{
  286.             return temp;
  287.         }
  288.     }
  289. }
  290. Position FindMin2( BinTree BST ){
  291.     BinTree temp = BST;
  292.     BinTree temp2 = NULL;
  293.     if(temp == NULL)
  294.         return NULL;
  295.     while(1){
  296.         if(temp->Left != NULL){
  297.             temp2 = temp;
  298.             temp = temp->Left;
  299.         }
  300.         else{
  301.             return temp2;
  302.         }
  303.     }
  304. }
  305. Position FindMax2( BinTree BST ){
  306.     BinTree temp = BST;
  307.     BinTree temp2 = NULL;
  308.     if(temp == NULL)
  309.         return NULL;
  310.     while(1){
  311.         if(temp->Right != NULL){
  312.             temp2 = temp;
  313.             temp = temp->Right;
  314.         }
  315.         else{
  316.             return temp2;
  317.         }
  318.     }
  319. }
  320. Position FindMax( BinTree BST ){
  321.     BinTree temp = BST;
  322.     if(temp == NULL)
  323.         return BST;
  324.     while(1){
  325.         if(temp->Right != NULL)
  326.             temp = temp->Right;
  327.         else{
  328.             return temp;
  329.         }
  330.     }
  331. }

Huffman Codes问题

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1508006239265828866
这一题乍一看题目特别长（没错，当时唬住我了。。。这道题可以被分解为两个步骤：1）计算由哈夫曼树得到的最优编码的总长度；2）判断同学提交的编码是否符合“编码长度最优”和“无前缀问题”两个方面。理解了这一点就去写代码去吧！
代码如下：

#include<iostream>
#include<cstdio>
#define Maxsize 126
#define Maxsize2 1000

using namespace std;
class Node{
public:
    int leftnode;
    int rightnode;
    string c;
    int f;
    int h;
    Node(){
        leftnode = -1;
        rightnode = -1;
        c = " ";
        h = -1;
    }
};

int N,M;
int count = 0;
int extra = 0;
int length = 0;
Node a[Maxsize];
Node b[Maxsize];
string code[Maxsize2][Maxsize];

void Findmin();
void Findmin2();
void Qianxu(int index,int layer);

int main(){
    //读取数据
    cin >> N;
    for(int i = 0;i < N;i++){
        cin >> a[i].c;
        cin >> a[i].f;
        b[i].c = a[i].c;
        b[i].f = a[i].f;
    }
    while(count != (2*N - 2)){
    //通过建立霍夫曼树来判断最优编码的总长度
        Findmin();
        Findmin2();
        a[N+extra].leftnode = count;
        a[N+extra].rightnode = count+1;
        a[N+extra].f = a[count].f + a[count+1].f;
        extra ++;
        count += 2;
        //for(int i = 0;i < (N + extra);i++)
        //    cout<<a[i].f<<" ";
        //cout<<endl;
    }
    Qianxu(N+extra-1,0);
    for(int i = 0;i < N + extra;i++){
        //cout<<a[i].c<<" "<<a[i].leftnode<<" "<<a[i].rightnode<<" "<<a[i].f<<" "<<a[i].h<<endl; 
        if(a[i].c != " ")
            length += a[i].f * a[i].h;
    }
    //cout<<length<<endl;
    //得到最优编码的长度
    //判断下列编码符不符合最优码的要求
    cin >> M;
    string s1,s2;
    int templen;
    int flag2;
    for(int i = 0;i < M;i++){
        templen = 0;
        for(int j = 0;j < N;j++){
            cin >> s1;
            cin >> code[i][j];
            //cout<<code[i][j].size()<<" "<<b[j].f<<endl;
            templen += code[i][j].size() * b[j].f;
        }
        //此编码长度大于最优编码长度
        if(templen > length){
            //cout<<templen<<endl;
            cout<<"No"<<endl;
            continue;
        }
        //检查前缀问题
        flag2 = 0;
        for(int j = 0;j < N;j++){
            for(int k = 0;k < N;k++){
                if(k != j){
                    if(code[i][j].size() > code[i][k].size())
                        continue;
                    else if(code[i][j] == code[i][k].substr(0,code[i][j].size())){
                        cout<<"No"<<endl;
                        flag2 = 1;
                        break;
                    }
                }
            }
            if(flag2 == 1)
                break;
            if(j == N-1)
                cout<<"Yes"<<endl;
        }
    }
    return 0;
}

void Findmin(){
    int maxindex = -1;
    for(int i = count;i < (N + extra);i++){
        if(maxindex == -1)
            maxindex = i;
        else{
            if(a[i].f < a[maxindex].f)
                maxindex = i;
        }
    }
    if(maxindex != count){
        int temp,templeft,tempright;
        string temp2;
        temp = a[maxindex].f;
        temp2 = a[maxindex].c;
        templeft = a[maxindex].leftnode;
        tempright = a[maxindex].rightnode;
        a[maxindex].f = a[count].f;
        a[maxindex].c = a[count].c;
        a[maxindex].leftnode = a[count].leftnode;
        a[maxindex].rightnode = a[count].rightnode;
        a[count].f = temp;
        a[count].c = temp2;
        a[count].leftnode = templeft;
        a[count].rightnode = tempright;
    }
}

void Findmin2(){
    int maxindex = -1;
    for(int i = count+1;i < (N + extra);i++){
        if(maxindex == -1)
            maxindex = i;
        else{
            if(a[i].f < a[maxindex].f)
                maxindex = i;
        }
    }
    if(maxindex != count+1){
        int temp,templeft,tempright;
        string temp2;
        temp = a[maxindex].f;
        temp2 = a[maxindex].c;
        templeft = a[maxindex].leftnode;
        tempright = a[maxindex].rightnode;
        a[maxindex].f = a[count+1].f;
        a[maxindex].c = a[count+1].c;
        a[maxindex].leftnode = a[count+1].leftnode;
        a[maxindex].rightnode = a[count+1].rightnode;
        a[count+1].f = temp;
        a[count+1].c = temp2;
        a[count+1].leftnode = templeft;
        a[count+1].rightnode = tempright;
    }
}

void Qianxu(int index,int layer){
    if(a[index].leftnode == -1 && a[index].rightnode == -1){
        a[index].h = layer;
        return;
    }
    if(a[index].leftnode != -1)
        Qianxu(a[index].leftnode,layer+1);
    if(a[index].rightnode != -1)
        Qianxu(a[index].rightnode,layer+1);
}

列出图的连通集

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1510878544933298176
最简单的题目，没有之一，30分钟一次性AC，没什么多说的，无非就是深度优先搜索和广度优先搜索嘛。。
代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<string.h>
#define Maxsize 10

using namespace std;

int N,E;
int a[Maxsize][Maxsize];
int visited[Maxsize] = {0};

void DFS(int index);
void BFS(int index);

int main(){

    //读入数据
    cin >> N >> E;
    int temp1,temp2;
    for(int i = 0;i < E;i++){
        cin >> temp1 >> temp2;
        a[temp1][temp2] = 1;
        a[temp2][temp1] = 1;
    }
    //DFS
    for(int i = 0;i < N;i++){
        if(!visited[i]){
            cout<<"{";
            DFS(i);
            cout<<" }"<<endl;
        }
    }
    //BFS
    for(int i = 0;i < N;i++){
        if(visited[i]){
            cout<<"{";
            BFS(i);
            cout<<" }"<<endl;
        }
    }
    return 0;
}

void DFS(int index){
    visited[index] = 1;
    cout<<" "<<index;
    for(int i = 0;i < N;i++){
        if(a[index][i] != 0 && !visited[i])
            DFS(i);
    }
}

void BFS(int index){
    queue<int> q;
    int temp;
    q.push(index);
    visited[index] = 0;
    while(q.size() != 0){
        temp = q.front();
        q.pop();
        cout<<" "<<temp;
        for(int i = 0;i < N;i++){
            if(a[temp][i] != 0 && visited[i]){
                q.push(i);
                visited[i] = 0;
            }
        }
    }
}

Saving James Bond

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1510878544933298177
这一题如果审题正确，感觉20分钟可以AC的，直接将上一题的DFS拿来用稍微改改就好了（BTW，程序员也确实都有自己的一套代码库），问题是：我审题没审清楚，第一跳与后面几跳的循环不能放在一起写（至于为什么，可以去看看题目。其他没什么。
代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<string.h>
#define Maxsize 101

using namespace std;

int N,flag;
float D;
int a[Maxsize][Maxsize];
float x[Maxsize],y[Maxsize];
int escaped[Maxsize] = {0};
int visited[Maxsize] = {0};

int checkdist(float x1,float y1,float x2,float y2);
void DFS(int index);

int main(){
    flag = 0;
    memset(a,0,sizeof(a));
    //读入N和D还有每个点
    cin >> N >> D;
    x[0] = y[0] = 0;
    for(int i = 1;i < N + 1;i++)
        cin >> x[i] >> y[i];
    //构建邻接矩阵
    for(int i = 0;i < N;i++){
        for(int j = i+1;j < N + 1;j++){
            if(i == 0){
                if(sqrt(x[j]*x[j]+y[j]*y[j]) <= 7.5 + D)
                    a[i][j] = a[j][i] = 1;
            }
            else{
                if(checkdist(x[i],y[i],x[j],y[j]) == 1)
                    a[i][j] = a[j][i] = 1;
            }
        }
    }
    //判断每个点是否能跳出
    for(int i = 0;i < N + 1;i++){
        if(i == 0){
            if(7.5 + D >= 50)
                escaped[i] = 1;
        }
        else{
            if(abs(x[i]-50)<=D||abs(x[i]+50)<=D||abs(y[i]-50)<=D||abs(y[i]+50)<=D)
                escaped[i] = 1;
        }
    }
    //开始从原点开始尝试跳出
    DFS(0);
    //输出结果
    if(flag == 0)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
    return 0;
}

int checkdist(float x1,float y1,float x2,float y2){
    float temp = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    if(temp <= D)
        return 1;
    else
        return 0;
}

void DFS(int index){
    if(flag == 1)
        return;
    visited[index] = 1;
    if(escaped[index] == 1){
        flag = 1;
        return;
    }
    for(int i = 0;i < N+1;i++){
        if(a[index][i] != 0 && !visited[i])
            DFS(i);
    }
}

六度空间问题

链接：https://pintia.cn/problem-sets/1497448825169559552/problems/1510878544933298178
这道题是解决了一个很有名的命题——六度空间问题，牵扯到的知识点是计算一个点到另一个点的距离。我心想，如果一个一个点套用计算最短距离的函数，可能太慢了，有没有什么全局更新的方法呢？答案是有，这里我用到了通信网中学过的一个算法，轻松实现了计算所有点到一个固定结点的最短路径。
代码如下：

#include<iostream>
#include<cstdio>
#include <bits/stdc++.h>
#include<cmath>
#include<string.h>
#define Maxsize 1001
#define INIT  9999

using namespace std;

int N,M;
int a[Maxsize][Maxsize];
int vis[Maxsize][Maxsize];
int dis[Maxsize][Maxsize];
int min1 = 99999999;
int u = 0;

int check(int index1,int index2);
void dijkstra(int input);

int main(){
    //构建邻接矩阵
    cin >> N >> M;
    int index1,index2;
    //初始化
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                a[i][j] = 0;
            else
                a[i][j] = 99999999;
        }
    }
    //读入数据
    for(int i = 0;i < M;i++){
        cin >> index1 >> index2;
        a[index1-1][index2-1] = 1;
        a[index2-1][index1-1] = 1;
    }
    //计算每个结点的六度结点百分比
    for(int j = 0;j < N;j++){
        for (int i = 0; i < N; i++)
            dis[j][i] = a[j][i];
        vis[j][j] = 1;
        //Dijkstra最短路算法求最短路径
        dijkstra(j);
        //for (int i = 0; i < N; i++)
        //    cout << dis[j][i];
        //cout<<endl;
        double temp = 0;
        for(int i = 0;i < N;i++){
            if(dis[j][i] <= 6)
                temp++;
        }
        //输出结果
        temp = temp/N * 100;
        cout << (j+1) << ": " << fixed << setprecision(2) << temp << "%"<< endl;
    }
    return 0;
}

void dijkstra(int input)
{
    for (int i = 0; i < N - 1; i++)
    {
        min1 = 99999999;
        // 寻找权值最小的点u
        for (int j = 0; j < N; j++)
        {
            if (vis[input][j] == 0 && dis[input][j] < min1)
            {
                min1 = dis[input][j];
                u = j;
            }
        }

        vis[input][u] = 1;

        for (int v = 0; v < N; v++)
        {
            // 对于每个u可达的v来说
            if (a[u][v] < 99999999)
            {
                // 如果当前的dis[v]不满足三角形不等式，那么进行松弛操作
                if (dis[input][v] > dis[input][u] + a[u][v])
                {
                    dis[input][v] = dis[input][u] + a[u][v];
                }
            }
        }
    }
}

总结

好啦好啦，又到了本期的总结时间了，通过这次的八道题我收获到了：1）审题审题再审题，多说多少遍都不为过；2）如果发生了段错误的话，在链表类问题中就是出现了访问NULL结点的情况，在数组类问题中有可能是数组越界、数组开太大了或者递归太多导致栈爆了等问题；3）如果运行超时，在浙大的PTA中大概率是哪个循环没有跳出来，如果是LeetCode超时的话有可能就是时间复杂度太大了；4）思路很重要，想清楚思路还有数据存放的方式以及算法再动手。
欢迎对ECE/CS/AI感兴趣的小伙伴关注我，如果你对我的内容有什么建议的话，或者你也对算法和数据结构感兴趣的话，可以单独找我讨论，也欢迎在评论区留下你的声音。