前言：

接近一个礼拜没更新了，因为上周周末我有两场计算机的算法比赛，我要复习，没时间更新博客。可事情总是不如人意，两场考试我都考的不好，都没做出来几道题，深深的打击了我，现在处于极度痛苦中。

这次说的这道题也没啥难的，唯一要注意的就是如何用选择排序选出一组序列中最小的两个数，而根据题目要求可以看出左右之分是根据这两个数的下标决定，而我排出来的是根据数字大小排的，所有在最后需要按照要求改一下。

第1关：赫夫曼树和赫夫曼编码

任务描述

本关任务：赫夫曼编码。请编写一个程序，先输入字符个数，再输入各个字符的权值（权值大小对应字符的出现频率），请以这些字符为叶子建立赫夫曼树，再求出其赫夫曼编码，并打印。

编程要求

根据提示，在右侧编辑器补充代码，将建立赫夫曼树、查找权重最小的结点下标和获取赫夫曼编码的函数补充完整。

测试说明

平台会对你编写的代码进行测试：

测试输入：

8    //8个权值5 29 7 8 14 23 3 11        //录入权值

预期输出：

01101011101111110000111010

开始你的任务吧，祝你成功！

源码：

/*
    哈夫曼编码(代码补充) 
*/
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
    int weight;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;    //动态数组，元素为HTNode 
typedef char** HuffmanCode;    //编码表，每一个元素都是一个编码，即char*方式存储的字符串 

void Init_weight(int **w, int n){
    while(!(*w=(int*)malloc((n+1)*sizeof(int))));
}

void Create_Weight(int n, int *w){
    int i, data;
    for(i = 1; i<=n; i++){
        scanf("%d", &data);
        w[i] = data;
    }
}    
    
    //初始化哈夫曼树 
void Init_HuffmanTree(HuffmanTree *HT,int *w, int n){
    int i;
    int m = 2*n-1;
    HTNode *p;
    while(!((*HT)=(HTNode*)malloc(sizeof(HTNode)*(m+1))));
    for(p = (*HT)+1, i=1; i<=n; i++, p++){
        p->weight = w[i];
        p->parent = 0;
        p->rchild = 0;
        p->lchild = 0;
    }
    for(; i<=m; i++, p++){
        p->lchild = 0;
        p->parent = 0;
        p->rchild = 0;
        p->weight = 0;
    }
}

//利用选择排序（循环一次得到最小的两个值） 
//在HT中选择parent为0，且权重最小的两个节点，返回他们的数组下标分别为s1和s2 
void Select(HuffmanTree HT, int i, int *s1, int *s2){
    //**************begin********************
    int flag1=0,flag2=0;
    for(int j=1;j<=i;j++){
        if(HT[j].parent==0){
            if(flag1==0){
                *s1=j;
                flag1++;
                continue;
            }
            if(flag2==0){
                *s2=j;
                flag2++;
                continue;
            }
            if(flag1==1&&flag2==1&&HT[*s1].weight>HT[*s2].weight){
                int x=*s1;*s1=*s2;*s2=x;
            }
            if(HT[j].weight<HT[*s1].weight){
                *s2=*s1;
                *s1=j;
                continue;
            }
            if(HT[j].weight<HT[*s2].weight){
                *s2=j;
                continue;
            }
        }
    }
    //这里就是根据下标大小来重新排一下
    if(*s1>*s2){
        int x=*s1;*s1=*s2;*s2=x;
    }
    
      //****************end******************
}

    //创建哈夫曼树
void Create_HuffmanTree(HuffmanTree HT,int n){
    //**************begin********************
    for(int i=n+1;i<=2*n-1;i++){
        int s1=0,s2=0;
        Select(HT,i-1,&s1,&s2);
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        HT[s1].parent=i;HT[s2].parent=i;
    }
      //****************end******************
}
    
    //初始化哈夫曼编码表 
void Init_HuffmanCode(HuffmanCode *HC,int n){
    while(!((*HC) = (HuffmanCode)malloc((n+1)*sizeof(char*))));
}
    
    //求哈夫曼编码
void GetHuffmanCode(HuffmanCode HC, HuffmanTree HT, int n){
    //**************begin********************
    char temp[n];
    temp[n-1]='\0';
    for(int i=1;i<=n;i++){
        int start=n-1,f=HT[i].parent,t=i;
        while(f!=0){
            start--;
            if(HT[f].lchild==t){
                temp[start]='0';
            }else{
                temp[start]='1';
            }
            t=f;f=HT[t].parent;
        }
        HC[i]=new char[n-start];
        strcpy(HC[i],&temp[start]);
    }
    
      //****************end******************
}
    
    //打印哈夫曼编码表
void PrintCode(HuffmanCode HC, int n){
    for(int i=1; i<=n; i++){
        printf("%s\n", HC[i]);
    } 
} 

void Destory(HuffmanTree *HT, HuffmanCode *HC){
    free(*HC);
    free(*HT);
}
int main(){
    HuffmanTree HT;
    HuffmanCode HC;
    int *w, n; 
    
    scanf("%d", &n);
    
    //初始化权重数组 
    Init_weight(&w, n);
    
    
    //创建权值数组
    //n表示权值个数 
    Create_Weight(n, w);    
    
    
    //初始化哈夫曼树 
    Init_HuffmanTree(&HT, w, n);
 
    //创建哈夫曼树
    Create_HuffmanTree(HT, n);
    
    //初始化哈夫曼编码表 
    Init_HuffmanCode(&HC, n);
    
    //求哈夫曼编码
    GetHuffmanCode(HC, HT, n); 
    
    //打印哈夫曼编码表
    PrintCode(HC, n); 
    
    //释放空间
    Destory(&HT, &HC);
     
    
    return 0;
}

前言：

果然功夫不负有心人，在前几天的第一次考核中我拿到了榜一，只不过可惜的是我没有ak，而那道我没有写出来的题就是我下面要展示的。

签到题——爆发式

Description

因为媛泽一个小女生独自出国父母不放心，媛泽便多叫上几个学弟学妹和她一同前往飞往东京，其中就有嘉欢学姐，晴晴学姐，耀星学长。但是因为在买机票的时候有些失误，她没有和她们三挨在一起，但是飞机上媛泽感到非常寂寞，想要到她们仨任意一人的位置上去一起坐这次的长途飞机，飞机上位置看作一个1212*1212的矩阵，其中ZHQXJF分别表示媛泽，嘉欢，晴晴，耀星，日本人，其他乘客的位置，并且没有位置被空缺出来。在前往任意一个学弟或学妹的位置的时候会经过其它乘客，由于媛泽穿了漂亮的jk害怕飞机上的小日子过得还不错的日本人骚扰她，所以在前往学弟学妹的位置的过程中会尽力避开日本人和挨着日本人的乘客，聪明的你来帮帮媛泽躲开日本人并计算出可以到达的且离她最近的学弟或学妹与她的距离。

Input

输入1212*1212的字符矩阵来表示灰机的座位关系。

Output

如果媛泽能够避开日本人到达他们三之中任意一人的位置上时，输出最短距离，否则输出0。

Sample Input 1

ZFJFHFFFFFFF
FFFFFFFFFFFF
FFFFFFFFFFFF
FFFFFJFFFFFF
FJFFFFFFFFFF
FFFFFFFFFFFF
FFFFFFFFFFFF
FFFFFJFFFFFF
FJFFFFFFFFFF
FFFQFFFFFFFF
FFFFFFFFFFFF
FFXFFFFFFFFF

Sample Output 1

Hint

如果媛泽周围八个方向上已经有日本人了，则媛泽不会动身，如果耀星，嘉欢，晴请也都是这般情况，也视为不可达，以上情况则输出0.

解题思路：

很明显，这道题的解题思路依旧是运用BFS，我们需要一个结构体来存储我们的位置，和已经走过的步数，需要一个队列来存储我们现在的位置和相邻的位置，直到目的地址进入队列。
但这道题难的地方不是在写BFS的逻辑上面，而是在怎么判断相邻位置应不应该入队。由题意可知，入队的位置其周围的八个位置都不应该出现日本人”J”，但是有特例啊，比如在边缘的地方，他周围能坐人的地方都只有3个或5个，不可能这种地方也要判断8个方位吧，所以就要分区域了，不同区域的判断条件都不同，如下图：

按照这样划分的话，区域1需要判断3个方向，区域2需要判断5个方向，方向图如下：

这样下来判断语句就显得非常臃肿(一下是我在考核时写的)：

bool judge(path n){
    if(n.x<12&&n.y<12&&n.x>=0&&n.y>=0&&map[n.x][n.y]!='J'){
        if(n.x<11&&n.y<11&&n.x>=1&&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<11&&n.y<12&&n.x>=1&&n.y>=11&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'){
            return true;
        }else if(n.x<12&&n.y<11&&n.x>=11&&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<11&&n.y<1&&n.x>=1&&n.y>=0&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x<1&&n.y<11&&n.x>=0&n.y>=1&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'){
            return true;
        }else if(n.x==0&&n.y==11&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'){
            return true;
        }else if(n.x==11&&n.y==11&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'){
            return true;
        }else if(n.x==11&&n.y==0&&map[n.x][n.y+1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
            return true;
        }else if(n.x==0&&n.y==0&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'){
            return true;
        }
    }
    return false;
}

就问你这看的难不难受！
于是最后系统判我超时了，非常难受！
回到寝室后，我又继续想这道题该怎么写，于是我想到了一个好办法：将该矩阵扩展到14x14，外面的一圈用”F”填充，中央的才是我们的飞机座位表，这样我们原本处于边缘的位置就不再是边缘了，而且其新填的位置都不是日本人，这样我们的判断条件对于12x12矩阵中的每一个元素都是适用的。还有最重要的一点就是走过的路不能重复走，得写一个布尔类型的矩阵，这个当时我忘了，所以铁定超时！

新的判断条件：

remap[n.x][n.y]==false&&n.x<13&&n.y<13&&n.x>=1&&n.y>=1&&map[n.x][n.y]!='J'&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'

源码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
bool remap[14][14];
char map[14][14];
struct path{
    int x;
    int y;
    char vul;
    int count;
};
queue<path> q;
int M[4][2]={0,1,1,0,0,-1,-1,0};
int go(path s){
    path now,n;
    remap[s.x][s.y]=true;
    q.push(s);
    while (!q.empty())
    {
        now=q.front();
        if(now.vul=='H'||now.vul=='X'||now.vul=='Q'){
            return now.count;
        }
        for(int i=0;i<4;i++){
            n.x=M[i][0]+now.x;
            n.y=M[i][1]+now.y;
            if(remap[n.x][n.y]==false&&n.x<13&&n.y<13&&n.x>=1&&n.y>=1&&map[n.x][n.y]!='J'&&map[n.x][n.y+1]!='J'&&map[n.x+1][n.y+1]!='J'&&map[n.x+1][n.y]!='J'&&map[n.x+1][n.y-1]!='J'&&map[n.x][n.y-1]!='J'&&map[n.x-1][n.y-1]!='J'&&map[n.x-1][n.y]!='J'&&map[n.x-1][n.y+1]!='J'){
                n.vul=map[n.x][n.y];
                n.count=now.count+1;
                q.push(n);
                remap[n.x][n.y]=true;
            }
        }
        q.pop();
    }
    return 0;
}
int main(){
    path s;
    memset(map,'F',sizeof(map));
    memset(remap,false,sizeof(remap));
    for(int i=1;i<13;i++){
        for(int j=1;j<13;j++){
            cin>>map[i][j];
            if(map[i][j]=='Z'){
                s.x=i;
                s.y=j;
                s.vul='Z';
                s.count=0;
            }
        }
    }
    cout<<go(s);
    return 0;
}

头歌数据结构实验五——二叉树及其应用

2021-11-15

头歌

前言：

这个实验总共有五关，都是基础知识，总共也才花了我一个小时(狗头保命)，除了第四五关的非递归比较难想，其他的都是小case，这里就不过多解释了。

第一关：实现二叉树的创建

BiTreeNode* CreatBiTree(char* s, int &i, int len)
// 利用先序遍历创建二叉树
// 参数：先序遍历字符串s，字符串初始下标i=0，字符串长度len。
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    BiTreeNode* root=new BiTreeNode;
    if(s[i]=='#'){
        root=NULL;
        i++;
    }else{
        root->data=s[i];
        i++;
        root->left=CreatBiTree(s,i,len);
        root->right=CreatBiTree(s,i,len);
    }
    return root;

    /********** End **********/
}

void InOrder(BiTreeNode* root)
// 二叉树的中序遍历
// 参数：二叉树根节点root
// 输出：中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root!=NULL){
        InOrder(root->left);
        printf("%c",root->data);
        InOrder(root->right);
    }
    
    /********** End **********/

}

第二关：计算二叉树的深度和节点个数

int GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数：二叉树根节点root
// 返回：二叉树的深度
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else{
        return 1+(GetTreeDepth(root->left)>=GetTreeDepth(root->right)?GetTreeDepth(root->left):GetTreeDepth(root->right));
    }
    /********** End **********/
}

int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数：二叉树根节点root
// 返回：二叉树的总节点个数
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else{
        return 1+GetNodeNumber(root->right)+GetNodeNumber(root->left);
    }
    /********** End **********/
}

int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数：二叉树根节点root
// 返回：二叉树的叶子节点个数
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return 0;
    }else if(!root->left&&!root->right){
        return 1;
    }else{
        return GetLeafNodeNumber(root->left)+GetLeafNodeNumber(root->right);
    }
    /********** End **********/
}

第三关：递归实现二叉树左右子树交换

BiTreeNode* BiTreeChange(BiTreeNode* root)
// 实现二叉树左右子树的交换（递归法）
// 参数：二叉树根节点root
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(!root){
        return NULL;
    }else{
        BiTreeChange(root->left);
        BiTreeChange(root->right);
        BiTreeNode* tmp=root->left;
        root->left=root->right;
        root->right=tmp;
    }
    
    /********** End **********/
}


void PreOrder(BiTreeNode* root)
// 二叉树的前序遍历
// 参数：二叉树根节点root
// 输出：二叉树的前序遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root){
        printf("%c",root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
    
    /********** End **********/
}

第四关：非递归实现二叉树左右子树交换

BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换（栈实现）
// 参数：二叉树根节点root
// 返回：二叉树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    stack<BiTreeNode*> s;
    BiTreeNode *p=root;
    if(root==NULL){
        return NULL;
    }
    s.push(root);
    while(!s.empty()){
        BiTreeNode *temp=p->left;
        p->left=p->right;
        p->right=temp;
        if(p->left!=NULL){
            s.push(p->left);
        }
        if(p->right!=NULL){
            s.push(p->right);
        }
        p=s.top();
        s.pop();
    }
    return root;
    /********** End **********/
}
void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数：二叉树根节点root
// 输出：二叉树的后序遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root!=NULL){
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%c",root->data);
    }
    /********** End **********/
}

第五关：层次遍历二叉树

void HierarchyOrder(BiTreeNode* root)
// 二叉树的层次遍历（队列实现）
// 参数：二叉树根节点root
// 输出：二叉树的层次遍历，中间没有空格，末尾不换行。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    queue<BiTreeNode*> q;
    BiTreeNode *now;
    q.push(root);
    while(!q.empty()){
        now=q.front();
        if(now!=NULL){
            printf("%c",now->data);
        }
        if(now->left!=NULL){
            q.push(now->left);
        }
        if(now->right!=NULL){
            q.push(now->right);
        }
        q.pop();
    }
    /********** End **********/
}

有序链表的异地合并

2021-11-14

日常

前言：

现在是凌晨，今天下午ACM就考核了，我要临时抱一下佛退，赶紧复习一下归并排序，但在题库里面找来找去，没找到非常合适的，只找到这个题，就当作练练手吧。

题目描述：

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1结尾无空行

输出样例:

1 2 3 4 5 6 8 10



结尾无空行

思路：

由于是异地合并，所有我们需要三个指针a.b.c，一个指向A当前所比较的数，一个指向B当前所比较的数，还要一个指向C现在的尾部，这样我们就是通过尾插法对C进行添加数据了。每次我们只需要比较a和b中哪个小，然后将其数据复制到一个新的节点上，再将这个节点插到c的后面就行了，而a或b中较小的也要向后移一下。当其中一链表比完了后，只需要把另一个链表全接上去就行了，就这么简单。

源码：

#include<iostream>
using namespace std;
typedef struct Lnode{
    int data;
    Lnode* next;
}Lnode,*Linklist;
//尾插法创建链表
void Create(Linklist &l){
    l=new Lnode;
    l->next=NULL;
    Lnode* r=l;
    int d;
    cin>>d;
    while(d!=-1){
        Lnode* p=new Lnode;
        p->data=d;
        p->next=r->next;
        r->next=p;
        r=p;
        cin>>d;
    }
}
//合并函数
void merge(Linklist &a,Linklist &b,Linklist &c){
    c=new Lnode;
    c->next=NULL;
    Lnode* r=c;
    Lnode* m=a->next;
    Lnode* n=b->next;
    while(m&&n){
        if(m->data>=n->data){
            Lnode* p=new Lnode;
            p->data=n->data;
            p->next=r->next;
            r->next=p;
            r=p;
            n=n->next;
        }else{
            Lnode* p=new Lnode;
            p->data=m->data;
            p->next=r->next;
            r->next=p;
            r=p;
            m=m->next;
        }
    }
    while(m){
        Lnode* p=new Lnode;
        p->data=m->data;
        p->next=r->next;
        r->next=p;
        r=p;
        m=m->next;
    }
    while(n){
        Lnode* p=new Lnode;
        p->data=n->data;
        p->next=r->next;
        r->next=p;
        r=p;
        n=n->next;
    }
}
int main(){
    Linklist a,b,c;
    Create(a);
    Create(b);
    merge(a,b,c);
    if(!c->next){
        cout<<"NULL";
    }else{
        Lnode* p=c->next;
        while(p){
            if(p->next){
                cout<<p->data<<' ';
                p=p->next;
            }else{
                cout<<p->data;
                p=p->next;
            }
            
        }
    }
    return 0;
}

头歌 JAVA 实训四——接口

2021-11-10

头歌

第一关：接口练习

任务描述

本关任务：定义一个Animal接口，并按要求实现接口。

要求：

Animal接口包含三个方法：  public void Speak(); //说话  public void Walk(); //行走方式  public String toString();//返回动物名称
定义Centipede（蜈蚣）类，实现Animal接口。例如： void Speak()；方法显示“不发声” void Walk(); 方法显示“不知道有多少条腿走路” String toString(); 方法返回“蜈蚣”
定义Dog（狗）类，实现Animal接口。
定义People（人）类，实现Animal接口。
定义Chinese（中国人）类，继承People（人）类。
定义Britisher（英国人）类，继承People（人）类。

最后设计一个类来测试你的所有的程序，通过该例充分理解接口、继承、多态。

提示：

这个题需要注意的一点就是题目的要求写的不完整，我们需要知道实现的类(如：Dog,People)要把所有方法都重写一遍，且内容需要自己根据蜈蚣的提示写出来，而toString函数是每个类都需要重写的，这点我觉得题目给的提示不够，很离谱。

源码：

Animal.java

package step2;
//定义Animal接口
public interface Animal {
    public void Speak();
    public void Walk();
    public String toString();
}

Centipede.java

package step2;
//完成Centipede类
public class Centipede implements Animal {

    public void Speak() {
        System.out.print("不发声");
    }

    public void Walk() {
        System.out.print("不知道有多少条腿在走路");
    }
    public String toString() {
        return "蜈蚣";
    }
}

Dog.java

package step2;
//完成Dog类
public class Dog implements Animal{
    public void Speak() {
        System.out.print("发声");
    }
    public void Walk() {
        System.out.print("四条腿走路");
    }
    public String toString() {
        return "狗";
    }
}

People.java

package step2;
//完成People类
public class People implements Animal{
    public void Speak() {
        System.out.print("发声");
    }
    public void Walk() {
        System.out.print("两条腿走路");
    }
    public String toString() {
        return "人";
    }
}

Chinese.java

package step2;
//完成Chinese类
public class Chinese extends People{
    public String toString() {
        return "中国人";
    }
}

Britisher.java

package step2;
//完成Britisher类
public class Britisher extends People{
    public String toString() {
        return "英国人";
    }
}

第二关：定义一个MyList接口，并使用数组的方法来实现接口

任务描述

要求：

MyList接口包含六个方法：  void add(Object obj)：往列表尾部添加对象  Object get(int index)：从列表中获取索引为i的对象  void clear()：清空所有的对象  boolean isEmpty()：判断列表中是否有对象  int size()：获取列表中对象的个数  int capacity()：所分配的空间大小
MyObjectArray类实现MyList接口，内部以数组的方式实现，要求：  构造函数MyObjectArray(int incSize)：参数incSize为数组初始化大小和空间的增量。若用户调用incSize非法，则设为默认值5。  当调用add()方法往试图往MyObjectArray中增加对象时，如果内部数组已满，则增加数组大小，增量为incSize。  调用clear()方法可以清空所有通过add()方法加入的对象。  调用get(int index)方法时，如果传入的参数非法，则返回null对象，否则返回对应的对象。
MyDoubleArray类也实现ReList接口，内部依旧通过数组实现，要求：  构造函数MyDoubleArray(int initSize)：参数initSize表示数组的初始化大小。若用户调用initSize非法，则设为默认值10。  当调用add()方法往MyDoubleArray列表里面增加对象时，如果其内部数组已满，则将数组的长度变为当前长度的2倍。  其他方法和MyObjectArray一致

最后设计一个类来测试你的MyObjectArray和MyDoubleArray类，看看这两个类是否能在不破坏使用者代码的情况下相互替换。 ####提示：增加数组长度的方法：使用java.util.Arrays.copyOf()方法，用法请查阅Java API文档。

提示：

这关有两个需要注意的地方：
1.MyDoubleArray类的数组类型依然得是Object类型，不能是Double类型，不然还得报错，但这就是这道出的不好的地方，你只需要对前面一个类的代码修改几下就行了，两个类的区别不大，完全就是重复操作，没意思。
2.clear函数需要把数组的长度重置。

源码：

MyList.java

package step1;
//在此写接口MyList

public interface MyList {
    public void add(Object obj);
    public Object get(int index);
    public void clear();
    public boolean isEmpty();
    public int size();
    public int capacity();
}

MyObjectArray.java

package step1;
import java.util.Arrays;
//在此写MyObjectArray类
public class MyObjectArray implements MyList {
    
    private  Object[] list; 
    private int size,incSize;
    
    public MyObjectArray(int incSize) {
        if(incSize<=0) {
            this.incSize=5;
        }else {
            this.incSize=incSize;
        }
        list=new Object[this.incSize];
        size=0;
    }
    
    @Override
    public void add(Object obj) {
        // TODO 自动生成的方法存根
        if(size==list.length) {
            list=Arrays.copyOf(list, list.length+this.incSize);
        }
        list[size++]=obj;    
    }
    
    @Override
    public Object get(int index) {
        // TODO 自动生成的方法存根
        if(index>=0&&index<size) {
            return list[index];
        }else{
            return null;
        }
    }

    @Override
    public void clear() {
        // TODO 自动生成的方法存根
        list=new Object[5];
        size=0;
    }

    @Override
    public boolean isEmpty() {
        // TODO 自动生成的方法存根
        if(size==0) {
            return true;
        }else {
            return false;
        }
    }

    @Override
    public int size() {
        // TODO 自动生成的方法存根
        return size;
    }

    @Override
    public int capacity() {
        // TODO 自动生成的方法存根
        return list.length;
    }
}

MyDoubleArray.java

package step1;
import java.util.Arrays;
//在此写MyDoubleArray类
public class MyDoubleArray implements MyList {

    private  Object[] list; 
    private int size;
    
    public MyDoubleArray(int initSize) {
        if(initSize<=0) {
            initSize=10;
        }
        list=new Object[initSize];
        size=0;
    }
    @Override
    public void add(Object obj) {
        // TODO 自动生成的方法存根
        if(size==list.length) {
            list=Arrays.copyOf(list, list.length*2);
        }
        list[size++]= obj;
    }

    @Override
    public Object get(int index) {
        // TODO 自动生成的方法存根
        if(index>=0&&index<size) {
            return list[index];
        }else{
            return null;
        }
    }

    @Override
    public void clear() {
        // TODO 自动生成的方法存根
        list=new Object[10];
        size=0;
    }

    @Override
    public boolean isEmpty() {
        // TODO 自动生成的方法存根
        if(size==0) {
            return true;
        }else {
            return false;
        }
    }

    @Override
    public int size() {
        // TODO 自动生成的方法存根
        return size;
    }

    @Override
    public int capacity() {
        // TODO 自动生成的方法存根
        return list.length;
    }

}

归并排序

2021-11-08

ACM

琪露诺的排序

前言：

依旧是OJ上的门槛题，当作复习用。这题主要考察的是排序里面的归并排序。

Description

笨蛋琪露诺喜欢用冰块搭积木。这天她用她的能力制造了N根冰柱作为材料，但这些冰柱显得参差不齐，不过好在她知道这些冰柱的高度。患有强迫症的小妖精琪露诺决定将这N根冰柱从小到大排列，不幸的是，琪露诺是个笨蛋，她只能将相邻的两根冰柱调换位置。现在她想知道她最少需要进行几次调换才能使这些冰柱变得有序。

Input

输入共两行。
第一行N(0<N<=500000)，代表冰柱的个数。
第二行N个数，代表每根冰柱的高度hi(0<hi<2^32)

Output

一个整数，代表琪露诺最少的调换次数。

Sample Input 1

4
4 3 2 1

Sample Output 1

思路：

为什么前面说这题一定要用归并排序呢，因为如果你不这样，用别的方法，比如冒泡排序什么什么的，你会发现超时了，因为他们的时间复杂度都是O(n2),而归并排序的时间复杂度只有O(N*log2N) 且非常稳定。这题的解法只需要在归并排序的基础代码上改一些就行了，这里先解释归并排序是怎么实现的。

归并排序分为两步：

1.分

(1)我们会得到一个长为N的数组，起始位置为low，末位置为high。
(2)判断low是否对于high。
(3)是则退出。
(4)否则令mid为low和high的中点，递归调用“分”函数，mid分别作为两个函数的末位置和起始位置。
(5)即为继续第一步

2.并

每次分完之后都会并一次，顺序自定义，由于分是递归调用的，所以先合并的是两个长度为1的数组，而后就是两长度为2的数组合并，直到数组对半合并

归并排序

改进：

为了完成这道题目的要求仅仅这样还是不行的，我们需要一点小改动，我们需要改进的地方只有计算逆序对的方法，有上面概念可知，在并这个过程这，两个数组都是有序的，所以当第一个序列的第x个数比第二个序列的第y个数大时，就产生了N-x+1个逆序对，这在排序过程中就可以进行统计。

源码：

#include<iostream>
using namespace std;
long long int sum=0;
//并函数
void merge(long long int a[],long long int b[],int low,int mid,int high){
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high){
        if(a[i]<=a[j]){
            b[k++]=a[i++];
        }else{
            b[k++]=a[j++];
            sum+=mid-i+1;
        }
    }
    while(i<=mid){
        b[k++]=a[i++];
    }
    while(j<=high){
        b[k++]=a[j++];
    }
    for(int i=low;i<=high;i++){
        a[i]=b[i];
    }
}
//分函数
void msort(long long int a[],long long int b[],int low,int high){
    if(low==high){
        b[low]=a[low];
    }else{
        int mid=(low+high)/2;
        msort(a,b,low,mid);
        msort(a,b,mid+1,high);
        merge(a,b,low,mid,high);
    }
}
int  main(){
    int n;
    cin>>n;
    long long int a[n],b[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    msort(a,b,0,n-1);
    cout<<sum;
    return 0;
}

取数组合——判断素数

2021-11-07

ACM

前言：

马上ACM要考核了，我也开始复习我在OJ上做过的门槛题，看到了这个挺难的题，说实话，当时我没写出来这道题，我还是去社区搜了一下才找到解法的，要用到DFS，属于数据结构图论里面的算法，确实比较难。

Description

组长特别想让小学妹进组，但是现在在所有新生中有一些是假扮的小学妹，为了知道那些是真正的小学妹，组长想到了一个好办法：
已知n个整数b1,b2,…,bn,他们分别代表所有的新生,以及一个整数k（k＜n）。
从n个整数中任选k个整数相加，可分别得到一系列的和。
例如当n=4，k＝3，4个整数分别为3，7，12，19时，可得全部的组合与它们的和为：
3＋7＋12=22，3＋7＋19＝29，7＋12＋19＝38，3＋12＋19＝34。
只有当他们的和是素数的时候，他们的真实身份才会显现，你的任务就是算出一共有几组满足条件的组合。
例如上例，只有一种组合为素数：3＋7＋19＝29。

Input

第一行两个整数：n , k 。（1<=n<=20，k＜n）
第二行n个整数：x1,x2，…,xn 。（1<=xi<=5000000）

Output

一个整数（满足条件的方案数）。

Sample Input 1

4 3
3 7 12 19

Sample Output 1

思路：

由于N和K都是不确定的，所以我们没法写出具体多少个循环来算，只能用递归。每递归一次，参数K就减小1，当K等于0时，判断sum的值是否为素数，是的话答案加1。思路其实就是这样，看起来简单，但理清并写出来确实有点难，但我相信聪明的你看完我的源码后能自己写出来。

源码：

#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int count=0;//输出的答案
//判断n是否是素数，应该都写过很多次了，就不解释了
int judge(int n){
    int m=sqrt(n);
    for(int i=2;i<=m;i++){
        if(n%i==0){
            return 0;//否
        }
    }
    return 1;//是
}
//递归体，使用了DFS的思路
void opera(int *num,int n/*总数*/,int k/*取K个数*/,int sum/*所求和*/,int s/*开始处*/){
    if(k==0){//即已经取出了k个数并求和
        if(judge(sum)){
            count++;
            return ;
        }
    }
    else{
        int i;
        for(i=s;i<n;++i){//从开始依次处取数
            opera(num,n,k-1,sum+num[i],i+1);
        }
    }
}
//主函数
int main(){
    int n,k;
    cin>>n>>k;
    int num[n];
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    opera(num,n,k,0,0);
    cout<<count<<endl;
    return 0;
}

字符串的减法A-B

2021-11-06

日常

A-B

前言：

前几天是半期考试，没错我这个学校有半期考试。因为我学的比较烂，所以复习花了好多时间，没有时间更新博客，以后我尽量做到日更，谢谢大家的支持。

题目描述：

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。

输入格式：

输入在2行中先后给出字符串A和B。两字符串的长度都不超过104，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。

输出格式：

在一行中打印出A−B的结果字符串。

输入样例：

I love GPLT!  It's a fun game!
aeiou
结尾无空行！

输出样例：

I lv GPLT!  It's  fn gm!
结尾无空行！

思路：

这题的解法非常多，最简单的就是暴力写法了，对主串A的每一个字符做循环遍历模式串B中的字符，看是否相等，相等就不输出。但暴力解法的时间复杂度为N*N，而N的值可能很大，而这题的时间限制是在140ms内跑完，很有因为可能超时而不过，所以我们需要换一个办法。
这里我用的是空间换时间的思想，我们另外开辟一个Boolean类型的一维数组，大小为52，我们可以用这个数组来存储B中出现过的字符，比如B=”aB”，则只有boo[0]和bool[26]为true，其他的都为false。这样我们对于A中的字符只需要遍历一遍就可以知道是不是需要输出，true表示不输出，false表示输出，所以代码的空间复杂度只有N了。
但后面我发现串B中可能不止有字母，可能还要一些特殊字符，比如’!’,’ ‘,’?’，所以还需要一个字符数组来存储出现过的特殊字符，但由于特殊字符是比较少的，所以对这个数组进行遍历花不了多少时间，而且我们可以将这种情况放在判断语句的最后，这样下来，代码的时间复杂度在串很长时依然接近N，这样这道题就写出来了。

源码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//判断A的特殊字符是否在B中存在
bool judge(char a,char b[],int c){
    for(int i=0;i<c;i++){
        if(a==b[i]){
            return false;
        }
    }
    return true;
}
int main(){
    string a,b;//a为主串，b为模式串
    char special[100];//由于存储b中出现过的特殊字符
    int flag=0;
    bool word[52];//存储b中出现过的字母，成表
    memset(word,false,sizeof(word));//将表全置空，也就是false
    getline(cin,a);
    getline(cin,b);
    //对表进行初始化
    for(int i=0;i<b.length();i++){
        if(b[i]>='a'&&b[i]<='z'){
            word[b[i]-'a']=true;
        }else if(b[i]>='A'&&b[i]<='Z'){
            word[b[i]-'A'+26]=true;
        }else{
            special[flag]=b[i];
            flag++;
        }
    }
    //对a进行遍历，并对表进行随机查找
    for(int i=0;i<a.length();i++){
        if(a[i]>='a'&&a[i]<='z'){
            if(!word[a[i]-'a']){
                cout<<a[i];
            }
        }else if(a[i]>='A'&&a[i]<='Z'){
            if(!word[a[i]-'A'+26]){
                cout<<a[i];
            }
        }else{
            if(judge(a[i],special,flag)){//判断是否是b中的特殊字符
                cout<<a[i];
            }
        }
    }
    return 0;
}

分类与标签功能已开启

2021-11-01

通知

头歌数据结构实训四——串

2021-11-01

头歌

前言：

花了20分钟作业写的三道题，没什么难度可言，这里就不详细解答了，只给出要求填写的函数代码(其中的乱码是中文，可以是编译格式问题导致的，不影响代码)。

第一关：求子串

void SubStr(SString t, SString s,int i,int len)
//从s的第i个字符开始截取长度为len的子串存入t中。
//其中1≦i≦串s的长度, 0≦len≦ 串s的长度-i+1。
//若i和len超出取值范围，则输出"error"；否则输出子串t。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int j=0;
    if(i<1||i>s[0]||len<0||len>s[0]-i+1){
        printf("error\n"); 
    }else if(len==0){
        printf("");
    }else{
        for(j=i;j<i+len;j++){
            t[j-i]=s[j];
        }
        t[j+1]='\0';
        printf("%s",t);
    }
    /********** End **********/
}

第二关：串的模式匹配之简单算法

int StrIndex_BF(SString s, SString t, int pos)
//´ÓÖ÷´®sµÄµÚpos¸ö×Ö·û¿ªÊ¼²éÕÒ×Ó´®t¡£
//ÈôÕÒµ½£¬Ôò·µ»Ø×Ó´®tÔÚÖ÷´®sÖÐµÚÒ»´Î³öÏÖµÄÎ»ÖÃ£¬·ñÔò·µ»Ø0¡£
{
    // ÇëÔÚÕâÀï²¹³ä´úÂë£¬Íê³É±¾¹ØÈÎÎñ
    /********** Begin *********/
    int m=s[0];int n=t[0];
    char tmp=s[1];
    for(int i=1;i<=m-n;i++){
        for(int j=0;j<n;j++){
            if(s[i+j]!=t[j+1]){
                break;
            }else{
                if(j==n-1){
                    return i;
                }
            }
        }
    }
    return 0;
    /********** End **********/
}

第三关：串的模式匹配之KMP算法

void GetNext(SString t, int next[])
//ÇóÄ£Ê½´®TµÄnextÖµ²¢´æÈënextÊý×éÖÐ
{
    // ÇëÔÚÕâÀï²¹³ä´úÂë£¬Íê³É±¾¹ØÈÎÎñ
    /********** Begin *********/
    int j=1;int i=0;next[1]=0;
    while(j<=t[0]){
        if(i==0||t[j]==t[i]){
            i++;j++;
            next[j]=i;
        }else{
            i=next[i];
        }
    }
    /********** End   *********/
}

前言：

第1关：赫夫曼树和赫夫曼编码

任务描述

相关知识

数据结构

建立赫夫曼树

求赫夫曼编码

Select()函数

编程要求

测试说明

源码：

前言：

签到题——爆发式

Description

Input

Output

Sample Input 1

Sample Output 1

Hint

解题思路：

源码：

前言：

第一关：实现二叉树的创建

第二关：计算二叉树的深度和节点个数

第三关：递归实现二叉树左右子树交换

第四关：非递归实现二叉树左右子树交换

第五关：层次遍历二叉树

前言：

题目描述：

输入格式:

输出格式:

输入样例:

输出样例:

思路：

源码：

第一关：接口练习

任务描述

要求：

提示：

源码：

Animal.java

Centipede.java

Dog.java

People.java

Chinese.java

Britisher.java

第二关：定义一个MyList接口，并使用数组的方法来实现接口

任务描述

提示：

源码：

MyList.java

MyObjectArray.java

MyDoubleArray.java

琪露诺的排序

前言：

Description

Input

Output

Sample Input 1

Sample Output 1

思路：

归并排序分为两步：

1.分

2.并

改进：

源码：

前言：

Description

Input

Output

Sample Input 1

Sample Output 1

思路：

源码：

A-B

前言：

题目描述：

输入格式：

输出格式：

输入样例：