【基础训练】算法笔记基础功能刷题记录

随便记一记，确实有将近一年没上手了，加之本身基础功就较差，总是不能找到最优解，或者漏掉一些极端情况。做的题目虽然都简单，但是想要补足自己在思维上的漏洞，毕竟自己测试很难涵盖所有情况。最近加班也比较忙，找了pat的题库随时打开就可以做一两道，没什么时间去系统的学习新的或者难的知识，就练练基本功复习一下吧。

目录

一、基础部分

1008 数组元素循环右移问题 (20 分)⭐

1042 Shuffling Machine (20 分)⭐

 PS、一些巧妙的题

1）用字符串按位拆分数字（牛客网 ky18）特殊乘法

二、入门练习

选择排序

插入排序

1025 PAT Ranking (25 分)⭐

 散列表

hash初步查询

*数据结构部分

1、栈

（1）常用操作

2、队列

优先队列 

优先级设置

结构体的优先级

---

一、基础部分

2022年1月9日

1011 A+B 和 C (15 分)

#include<iostream>//给定区间内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。 int main(){int n;scanf("%d",&n);long long  a[n][3];for(int i=0;i<n;i++){scanf("%lld %lld %lld",&a[i][0],&a[i][1],&a[i][2]);}for(int i=0;i<n;i++){if(a[i][0]+a[i][1]>a[i][2])printf("Case #%d: true\n",i+1);elseprintf("Case #%d: false\n",i+1);}return 0;}

以为是要多行输入然后多行输出所以没用while，没想到根本不重要...

想到了加法结果可能会溢出，但是还是忘了用long long 型，尴尬.jpg。后面补上才全部正确。

复习一下：https://blog.csdn.net/mmk27_word/article/details/84378346

#include<iostream>
int main(){int n,t=1;//n是数据的个数，t是当前循环次数scanf("%d",&n);while(n--){long long a,b,c;scanf("%lld%lld%lld",&a,&b,&c);if(a+b>c)printf("Case #%d: true\n",t++);//t++很巧妙elseprintf("Case #%d: false\n",t++);} return 0;
}

1016 部分A+B (15 分)

#include<iostream>int Find(int num,int x){//num是需要计算的数，x是要寻找的部分数 int temp=x,n=0;//n是出现了部分数的个数 while(num/10){if(num%10==x) n++;num=num/10;}if(num==x) n++;while(--n){temp=temp*10+x;}return temp;
}int main(){int num1,num2,x1,x2; scanf("%d%d%d%d",&num1,&x1,&num2,&x2);printf("%d\n",Find(num1,x1)+Find(num2,x2));
}

我的思路是计算输入的数除以十来判断，但是 这样子会最后一次的结果小于十不进while循环，要单独再判断if(num==x) n++; 用n来存储新的整数的位数，这样子其实是读题时思维的惯性，绕远了，看了下答案其实写的很简单，改进了一下：

#include<iostream>int Find(int num,int x){//num是需要计算的数，x是要寻找的部分数 int temp=0,n=0;//n是出现了部分数的个数 while(num){if(num%10==x) temp=temp*10+x;num=num/10;}return temp;
}int main(){int num1,num2,x1,x2,temp1,temp2; scanf("%d%d%d%d",&num1,&x1,&num2,&x2);printf("%d\n",Find(num1,x1)+Find(num2,x2));
}

最后的效果是一个while内直接完成了判断是否=x和计算结果temp，而且我第一遍做的时候用了因为循环次数实际上少一次，用了初值temp=x，反正又是又是饶了一个大圈子，还挺呆的...

再接再厉！！

1046 划拳 (15 分)

#include<iostream>int main(){int a1,a2,b1,b2;//a1是甲喊，a2是甲划，乙同理int n;//计算的次数int m1=0,m2=0;//甲、乙喝酒的次数 scanf("%d",&n);while(n--){scanf("%d%d%d%d",&a1,&a2,&b1,&b2);if(a2==a1+b1&&b2!=a1+b1)m2++;//甲猜中，乙喝酒if(a2!=a1+b1&&b2==a1+b1)m1++;//乙猜中，甲喝酒 } printf("%d %d",m1,m2);return 0; 
}

 这题我做的和答案差不太多，只不过我用了while，渐渐爱上了哈哈哈

1008 数组元素循环右移问题 (20 分)⭐

#include<iostream>int main(){int n,m;//数组内有n个，右移m位 scanf("%d%d",&n,&m);int a[n]={0};for(int i=0;i<n;i++){ if((i+m)<n)scanf("%d",&a[i+m]);else scanf("%d",&a[(i+m)%n]); 	
//		for(int i=0;i<n;i++)
//		printf("%d %d\n",i,a[i]);	}for(int i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d",a[n-1]);}

刚开始很呆的想了半天先全部输入进数组a再用b存储后m位，再进行移位，后来想到输入时直接移位就行了。

感觉我这个做法也算是比较巧妙，比答案简单点，而且涵盖了m》n时的情况，不错不错！

1042 Shuffling Machine (20 分)⭐

#include<iostream>
const int N=54;int main(){int a[N+1],b[N+1],c[N+1];//a存储原本的1-54，用/13的结果来判断前面的字符，b存储输入的变化规律数 ,c存储变化后的结果 char D[5]={'S','H','C','D','J'};for(int i=1;i<=N;i++)a[i]=i;int k;//循环次数 scanf("%d",&k);for(int i=1;i<=N;i++)scanf("%d",&b[i]);int key; for(int i=1;i<=N;i++){key=b[i];int m=1;while(k>m++){key=b[key];}	c[key]=a[i];
//		printf("%d %d %d\n",i,key,c[key]);}for(int i=1;i<N;i++)printf("%c%d ",D[(c[i]-1)/13],(c[i]-1)%13+1);printf("%c%d",D[(c[N]-1)/13],(c[N]-1)%13+1);
}

这道题真是做的有点头疼，我以为关键在找位置，结果被确定字符难住了。

我一开始是想到，通过用一个关键字key，直接寻找原本的数a经过k次变化之后的最终数组下标，最后再一次性赋值。这样子是想避免反复给数组们赋值，尽可能简单一点（虽然不一定起到了效果，但是还是想试试不同的方法）。

我看了答案给出的方法，是用两个数组来回倒，循环k次。

但是一直没想好怎么处理前面的字符，最后看了眼答案的方法，用另一个数组的余数来找字符，豁然开朗。

写完之后发现两个问题：

1）求后面的数取余时，13%13=0，但是我需要13；

2）同上，找字符时也是，第13位会找到下一个组的字符，但是我需要在当前组；

试了半天也不行，最后还是参考了答案给的方法，在被除数上-1，解决了字符的问题，再给结果+1，又解决了后面数字的问题；

很巧妙！学到了！

---

2022年1月10日

1036 跟奥巴马一起编程 (15 分)

#include<iostream>int main(){int t;char c;scanf("%d %c",&t,&c);for(int i=0;i<((t+1)/2);i++){if(i==0||i==(t+1)/2-1){for(int k=0;k<t;k++){printf("%c",c);}printf("\n");}else{printf("%c",c);for(int k=0;k<(t-2);k++)printf(" ");printf("%c",c);printf("\n");}}return 0;
}

 这个题主要是感觉做四舍五入稍微麻烦，别的都很常规。我是直接用（t+1）/2来算了，反正效果是一样的，感觉比较投机取巧但是也没什么问题，比答案简单点

答案做法

1022 D进制的A+B (20 分)

#include<iostream>int main(){int a,b,x;int num[100]={0};int k=0;scanf("%d%d%d",&a,&b,&x);a=a+b;while(a/x){num[k]=a%x;a=a/x;
//        printf("%d %d\n",k,num[k]);k++;}num[k]=a;for(int i=k;i>=0;i--){printf("%d",num[i]);}return 0;
}

常规题，我做的循环的地方稍微有点瑕疵，答案会更简单点。

 PS、一些巧妙的题

1）用字符串按位拆分数字（牛客网 ky18）特殊乘法

我的思路：

处理数字，按位拆分，等于0的位直接丢弃不用计算，拆分过程中数字被倒置了不过不影响计算。

写了一大堆啰里啰唆，反面教材。

#include<iostream>int main(){int a[10]={0};int b[10]={0};int x,y;int sum=0;//总和 scanf("%d%d",&x,&y);int i=0;//处理x 只保留非0数 存在a中 while(x){if(x%10){a[i]=x%10;i++;}x=x/10;}i=0;//处理y 只保留非0数 存在b中 while(y){if(y%10){b[i]=y%10;i++;}y=y/10;}for(int i=0;i<10;i++){for(int j=0;j<10;j++){if(a[i]!=0&&b[j]!=0){sum+=a[i]*b[j];} }}printf("%d",sum);
}

 看到评论区一个精妙的答案，值得学习

#include<iostream>
#include<cstdio>
using namespace std;int main()
{string str1, str2;while(cin >> str1 >> str2){int sum = 0;for(int i = 0; i < str1.length(); ++i){for(int j = 0; j < str2.length(); ++j){sum += (str1[i]-'0')*(str2[j]-'0');}}cout << sum << endl;}return 0;
}

二、入门练习

选择排序

#include<iostream>
//选择排序 自己分析
int main(){int n;//待排序数列长度scanf("%d",&n);int a[n];//待排序数列for(int i=0;i<n;i++)scanf("%d",&a[i]);int min,temp;//min最小值的下表，temp用于交换for(int i=0;i<n;i++){min=i;//对于有n个数字的数列a，从头开始排序前i位，每次找到（i,n-1)中的最小值，用min记录(每趟先令min=i，与后面的数字进行对比)for(int j=i;j<n;j++){if(a[min]>a[j])min=j;}
//    	printf("%d %d %d\n",i,min,a[min]);temp=a[i];a[i]=a[min];a[min]=temp;
//      for(int i=0;i<n;i++){
//    		printf("%d ",a[i]);
//		}
//		printf("\n");}for(int i=0;i<n;i++){printf("%d",a[i]);}return 0;
}

其实核心代码就五六行，为了把每一趟选择的情况展现出来，我又加了一些其他的，所以显得有点啰嗦。

插入排序

#include<iostream>
//插入排序 自己分析int main(){int n;scanf("%d",&n);int a[n];for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=1;i<n;i++){//插入排序，每趟在前i-1位中找到第i位的插入位置int j=i-1;int temp=a[i];while(a[j]>temp){a[j+1]=a[j];j--;}a[j+1]=temp;} for(int i=0;i<n;i++)printf("%d ",a[i]);return 0;
} 

写到这里不禁有一丝惋惜，如果准备初试的时候有时间这样子挨个敲一遍就好了，理解清晰而且能记住，唉。

---

2022年1月13日

1025 PAT Ranking (25 分)⭐

 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//pat a 1026struct Student{char id[15];//准考证号 int score;//分数 int room;//考场 int rank;//考场内排名
//	int roomrank;//考场内排名 
}stu[30010];bool cmp(Student a, Student b){if(a.score!=b.score) return a.score>b.score;else return strcmp(a.id,b.id)<0;
}int main(){int n,num=0;scanf("%d",&n);for(int i=0;i<n;i++){int k,j=0;scanf("%d",&k);//k是考场内人数
//		num+=k;//num是总人数 while((j++)<k){scanf("%s %d",stu[num].id,&stu[num].score);stu[num].room=(i+1); num++;}sort(stu+num-k,stu+num,cmp);//对单个考场排序，该考场内有k人 stu[num-k]. rank=1;//令第一名考生的排名为1 for(int j=num-k+1;j<num;j++){if(stu[j].score==stu[j-1].score)//如果第j名考生与j-1名考生的分数相同stu[j].rank =stu[j-1].rank;//其排名也相同 else//当前计算到了该考场的第j+1个人（因为实际上for是从第2个人开始的) stu[j].rank=j+1-(num-k);//num-k是该考场的第一个人所占的人数，即（j+1）-（num-k）为当前人前面的人数} }printf("%d\n",num);sort(stu,stu+num,cmp);int r=1; //r用于表示总排名。for(int i=0;i<num;i++){if(i>0&&stu[i].score!=stu[i-1].score){//从第二个考生起，若当前考生与前一个考生成绩不同 r=i+1;// r=当前人数（相反，若成绩相同，则r不变化，同分同成绩） }printf("%s %d %d %d\n",stu[i].id,r,stu[i].room,stu[i].rank); } }

 这个题做了比较久，虽然思路一开始就有了，但是很多细节自己不确定，所以反反复复的看答案借鉴，感觉还是做过的题太少了，基础功不踏实。

这里我觉得有一个技巧点和两个巧妙的地方：

• 运用了 sort()、strcmp()函数

sort()函数

需要加上头文件

#include<algorithm>

using namespace std

参数： sort（首元素地址，尾元素地址的下一个地址，比较函数（非必填））；

不写比较函数时默认递增

我个人理解，比如说首地址是a，尾元素的下一个地址是a+6，那实际上可以视为a之后包括a在内的6个数进行排序。

对于比较函数

bool cmp(char a, char b){  //char类型就是按照字符集排序

        return a > b;

}

a > b 时 从大到小排序

a < b 时 从小到大排序（可以参考里面这个大于小于号理解）

如果时对结构体数组进行排序的话

struct node {

        int x , y ;

}ssd [ 10 ];

bool cmp(node a, node b){ // 对数组ssd按照x从大到小排序

        return a.x > b.x;

}

两个比较巧妙的地方：

（先说明一下，k是当前考场的 总人数，num是所有人，j循环范围：num-k+1 <= j  < num，即循环k次，实际上j代表的是当前人在总人数中的次序）

1、考场内排名计算时，排序后若当前人分数！=前一人分数，则当前人排名=当前循环人次序-该考场第一人次序

stu[j].rank=j+1-(num-k);//num-k是该考场的第一个人所占的人数，即（j+1）-（num-k）为当前人前面的人数

2、所有人排名计算时，int r=1； 用 i 在所有人中进行循环

        当前人与前一人分数相同时，r不变 ，即还是前一人的排名；

        当前人与前一人分数不同，r = i + 1，即排名=已计算排名人数+1；

所以还是感觉自己思路不够清晰，特别是在计算数字的时候，很难找到如此便捷简单的方法，这个题还是比较典型的。

---

2022年1月17日

最近很忙在加班加班加班.....然后又赶上年终和考核，中间跨了几天没学习，愧疚.jpg

 散列表

散列表用于判读在N个数中，某M个数是否都存在。

核心思想（我觉得）应该是用空间换时间。

大体思想使用数字本身作为数组下表，计算是否存在（用true和false）和计算出现次数（++

）都是建立在这个思想的基础上。

时间复杂度是O ( MN )

当这个m、n越来越大时，这个方法就不简便了，为此就需要一些特殊方式-散列函数来处理，如

直接定址法   直接用数字对应下标，H(key）=key，或线性变换 H(key）=a*key+b

平方取中法   用key的平方 的中位数作为hash值

除留余数法   H(key）= key%mod   最常用的方法

产生相同的key时便会发生冲突，就要有解决冲突的方法

线性探查法，就直接+1，下一位，还冲突就继续

平方探查法，H( key ）+ 1^2 ；H( key ）+ 2^2…… 超出时再取模 

链地址法 ，将所有H（key）相同的key链接成一条单链表，可以通过遍历该单链表直接寻找。

hash初步查询

喜提过年+加班半个月...

#include <iostream> 
#include<cstdio>
//n个字符串（恰好由3位大写字母组成），再给出m个查询字符串，问每个查询字符串在n个字符串中出现的次数 
const int max=100;
char s[max][5],temp[5];
int hashTable[26*26*26+10];int hashFunc(char s[],int len){ //将s转化为整数 int id=0;for(int i=0;i<len;i++){id=id*26+(s[i]-'A');} return id;
} int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",s[i]);//%s 代表字符串或者char型数组，这里s[i]本身就代表了数组的首地址，不用再加& int id=hashFunc(s[i],3);//将字符串s[i]转化为整数 hashTable[id]++;//该字符串出现的次数加1 }for(int i=0;i<m;i++) {scanf("%s",temp);int id=hashFunc(temp,3);//转化为整数 printf("%d\n",hashTable[id]);//查找这个id对应的字符串出现的次数 }return 0;
}

*数据结构部分

1、栈

后进先出

栈顶指针：始终指向栈最上方元素的标记。通常记为TOP

当用数组实现栈时，栈顶指针是一个int型变量；

当用链表实现栈时，则是一个int*型的指针；

栈空时 TOP为-1

头文件 #include <stack>

using namespace std;

stack <typename> name;

（1）常用操作

清栈（clear）

void clear(){

        TOP=-1;

}

获取栈内元素 （size） top始终指向栈顶，而数组下标从0开始

int size（）{

        return TOP+1;

}

判空（empty）

bool empty(){

        if (TOP==-1) return true;

        else return false;

}

进栈（push）

void push（int x）{

 st[ ++TOP] =x;

}

出栈（pop） 使用前需要判断栈是否为空

void （pop）{

        TOP--;

}

取栈顶元素（top)  使用前需要判断栈是否为空

void （top){

        return st[top];

}

#include<stack>
#include<iostream>
using namespace std;
int main(){stack<int> st;if(st.empty()){			//判空 cout<<"空"<<endl;}for(int i=0;i<5;i++){st.push(i);			//入栈 }if(st.empty()){cout<<"空"<<endl;}cout<<st.size()<<endl;	//获取栈内元素个数 for(int i=0;i<3;i++){st.pop();} cout<<st.top();			//获取栈顶元素 return 0;
}

2、队列

头文件

#include <queue>

using namespce std;

优先队列 

队首元素一定是优先级最高的，再加入时优先队列底层的数据结构堆（heap）会随时调整结构，使得队首元素永远是优先级最大的

优先队列没有front（）和back（）函数，只能通过top（）函数来访问队首元素（也称为堆顶元素）

priority_queue <typename> name; 

#include<iostream>
#include<queue>
using namespace std;int main(){priority_queue<int> q;if(q.empty())	cout<<"empty"<<endl; 	//判空 else	cout<<"no empty"<<endl; q.push(3);q.push(2);	q.push(5);q.push(1);				//入栈后保持队首优先级 cout<<q.top()<<endl;	//获取队首元素 cout<<q.size()<<endl;	//个数 q.pop();				//出队 cout<<q.top()<<endl;if(q.empty())	cout<<"empty"<<endl;else	cout<<"no empty"<<endl; 	return 0;
} 

优先级设置

	priority_queue<int> q1;priority_queue<int,vector<int>,less<int>> q2;

这两种定义方式是等价的

其中，第二种定义方式内多了两个参数，

vector<int> 填写的是承载底层数据结构堆（heap）的容器，如果第一个参数是double或者char，此处只需要填写 vector<double> 或 vector<char>

less<int> 则是对第一个参数的比较类，less<int>表示数字越大越优先，greater<int>表示数字越小越优先

注：char类型按照字典序排序

#include<iostream>
#include<queue>
using namespace std;int main(){
//	priority_queue<int> q1;priority_queue<int,vector<int>,greater<int> > q2;q2.push(3);q2.push(2);q2.push(1);q2.push(5);cout<<q2.top()<<endl;return 0;
} 

结构体的优先级

#include<iostream>
#include<queue>
#include<string>
using namespace std;struct fruit{string name;int price;friend bool operator < (fruit f1,fruit f2){ 	// 重载<return f1.price < f2.price;	//用>最便宜的排在最前面,用<最贵的排在最前面 ，和cmp刚好相反 }
}f1,f2,f3;int main(){priority_queue<fruit> q;
//	priority_queue<int,vector<int>,greater<int> > q2;f1.name="桃子";f1.price=3;f2.name="苹果";f2.price=1;f3.name="梨";f3.price=2;q.push(f1);q.push(f2);q.push(f3);cout<<q.top().name<<" "<<q.top().price<<endl; 		return 0;
} 

3、链表

结点：

struct node {

        typename data; //数据域

        node* next；//指针域

}；

头结点 head

malloc函数   c语言   需要头文件stdlib.h  

基本用法：

typename *p=(typename)malloc(sizeof (typename));  // 申请一个大小为sizeof (typename)的空间，返回指向这块空间的地址，转化为node*类型的指针，赋值给*p

注：申请较大的动态数据容易失败

new运算符  c++ 

typename *p = new typename；

注：申请较大的动态数据容易失败

内存泄漏：使用malloc或new开辟出来的内存空间在使用过后没有释放，导致其在 程序结束之前始终占据该内存空间，使得内存消耗过快以至于最后无内存可分配。

如何释放———>  free 函数   delete运算符

头文件stdlib.h         free(p);  ————》 对应malloc

delete(p) ————》对应new         

（1） 创建

#include<iostream>
#include<stdlib.h>
using namespace std;struct node{int data;node *next;	
};//创建链表 
node* create(int Array[]){node *p,*pre,*head;	//pre-当前节点的前驱，head-头结点head = new node;	//创建头结点 head->next=NULL; 	//头结点指针域为nullpre=head;			//pre指向headfor(int i=0;i<5;i++){p=new node;		//新节点p->data=Array[i];p->next=NULL;	//p的指针域为nullpre->next=p;	//前驱节点pre的指针域为p pre=p; 			//pre指向p，作为下一个新节点的前驱节点 } return head;		 }int main(){int Array[5]={5,3,2,6,3};node *L=create(Array);	//新建链表。返回的head赋给LL=L->next;				//从第一个节点才开始有数据域while(L!=NULL){cout<<L->data<<" ";L=L->next;} return 0;
}