小伙伴们大家好，今天给大家带来几道算法题。
第一题
题意如图所示。先来讲比较简单的如何用队列实现栈。
算法思想
准备两个队列，一个队列用于接受新元素，一个队列用于备用。比如我们定义两个队列a，b。a起初用来存储新元素，b用来备用。我们输入元素1，2，3，4。如果此时我们想得到栈顶，那么就把1，2，3依次放入b，a中此时剩余4，返回即可，并出队列。此时，b用来接受新的元素，当要返回栈顶时，只需将b队列元素除了最后一个均放到a，再出队列返回即可，此时a将用来接受新元素。重复操作。
代码展示
#include<iostream>
#include<queue>
using namespace std;
int main(){queue<int>q1,q2;//两个队列 一个为入队列 一个队列用于备用int flag;//0：退出 1：入栈 2：出栈 int x,y;int Push[2]={1,0};//用于记录哪个队列为入队列 默认为q1 cout<<"请选择操作"<<endl;cin>>flag;while(flag){if(flag==1){cin>>x;if(Push[0]==1){q1.push(x);}else{q2.push(x);}}else{if(Push[1]==0){//将q1元素送入q2但是栈顶不用直接输出即可 if(q1.empty()){cout<<"栈中无元素"<<endl;cout<<"请选择操作"<<endl;cin>>flag;continue;}while(q1.size()>1){y=q1.front();q2.push(y);q1.pop();}cout<<q1.front()<<endl;q1.pop();Push[1]=1;//q2担任入队列 Push[0]=0;}else{//将q2元素送入q1但是栈顶不用直接输出即可 if(q2.empty()){cout<<"栈中无元素"<<endl;cout<<"请选择操作"<<endl;cin>>flag;continue;}while(q2.size()>1){y=q2.front();q1.push(y);q2.pop();}cout<<q2.front()<<endl;q2.pop();Push[0]=1;Push[1]=0;}}cout<<"请选择操作"<<endl;cin>>flag; }
}大家返回栈顶时要注意队列是否为空。
算法思想
接下来讲如何使用栈实现队列。我们依然准备两个栈，一个栈用于接受新元素，一个栈用于备用。 当向栈中输入元素时，查看备用栈是否为空，为空则将输入栈的元素全部依次放入备用栈。这时栈顶就是队列首元素，可以直接返回。当输入元素后发现备用栈不为空，则不进行操作。当备用栈出元素后，变为空栈，则可以将入栈中的元素放入备用栈。
代码展示
#include<iostream>
#include<stack>
using namespace std;
void elementgo(stack<int>&s1,stack<int>&s2){if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}}
}
int main(){stack<int>s1,s2;//用栈实现队列elementgo(s1,s2);//当s2无元素时将s1中元素全部倒入s2，此时s2栈顶就是队列首部元素//s2中有元素时不做处理//s1每进入一个元素调用函数 s2每出一个元素调用函数int flag;//代表执行的操作 0：退出 1：队列加入元素 2：返回队列首元素 int x;cin>>flag;while(1){if(!flag){break;} else if(flag==1){cin>>x;s1.push(x);elementgo(s1,s2);}else{if(!s2.empty()){cout<<"队列首元素为:"<<s2.top()<<endl;s2.pop();elementgo(s1,s2);}else{cout<<"队列为空"<<endl;} }cin>>flag;}
} 第二题
可以把数组值看成一个个格子，看有多少雨滴可以落在上面，这和它的左右有关。
算法思想
首先，一个位置能不能接雨水可以是0也可以不是0。我们考虑第i个位置，那么rain【i】 的值可以由下式得到：rain【i】=max（0，min（max（arr【0~i-1】），max（arr【i+1~n-1】））-arr【i】）。i位置能接多少雨水取决于其左右最大值里的最小值，最后接完水肯定是一个长方形，高就是这个最小值，大家可以想一下。在此基础上减去i位置高度就是i位置可以接多少水。这个值可能为负数，因此我们需要和0作比较，取最大值。
求0~i-1位置最大值、求i+1~n-1位置最大值我们可以使用两个辅助数组。
代码展示
#include<iostream>
using namespace std;
int getrain(int *arr,int n){int sum=0;if(n<=2){return 0;}int max[n];int MAX=max[0]=arr[0];//max【i】代表0~i位置最大值 for(int i=1;i<n;i++){if(arr[i]>MAX){max[i]=arr[i];MAX=arr[i];}else{max[i]=MAX;}}int maxx[n];//maxx[i]代表i位置到n-1位置最大值maxx[n-1]=MAX=arr[n-1];for(int i=n-2;i>=0;i--){if(arr[i]>MAX){maxx[i]=arr[i];MAX=arr[i];}else{maxx[i]=MAX;}} int x;//rain[i]=max(min(max(arr[0]~arr[i-1]),max(arr[i+1]]~arr[n-1]))-arr[i],0);for(int i=1;i<=n-2;i++){x=max[i-1]<maxx[i+1]?max[i-1]:maxx[i+1];x=x-arr[i];sum+=x>0?x:0;}return sum;
}
int main(){int n=6;int arr[6]={3,1,2,5,2,4};int rainsum=getrain(arr,n);cout<<rainsum;
}大家一定不要忘了减去i位置高度。
第三题
算法思想
整个数组的最大值max肯定会取到，要不落在左边，要不落在右边。要求绝对值最大值肯定是要让另一部分最大值尽量小。
如果数组最大值落在左数组，那么绝对值的最大值就是max-arr【n-1】。大家肯定很疑惑，现在为大家解答。如果右数组仅有一个元素，那么肯定符合。如果右侧有多个元素，且n-1位置最大，那么也符合。如果右侧有多个元素，并且n-1位置并不是最大值，那么我们新得到的绝对值肯定比max-arr【n-1】小。所以当数组最大值落在数组左侧时，最大值为max-arr【n-1】。同样，当数组最大值落在数组右侧时，最大值为max-arr【0】。最后返回二者最大值即可。
代码展示
#include<iostream>
using namespace std;
int getmax(int *arr,int n){int Max=0;for(int i=1;i<n;i++){if(arr[Max]<arr[i]){Max=i;}}return max(arr[Max]-arr[n-1],arr[Max]-arr[0]);
}
int main(){int arr[6]={1,3,7,2,4,0}; int max=getmax(arr,6);cout<<max;
}第四题
算法思想
这个题很简单。先把str加倍，比如str原来为12345，那么变成1234512345，我们可以发现只要是str的连接词那么都会出现在新的str中。这个问题就转化为字符串匹配问题了。我们就可以使用KMP算法了！！
不会KMP的小伙们看我之前的讲解：KMP算法-CSDN博客
代码展示
#include<iostream>
using namespace std;
int* getnext(string str){int *next=new int[str.length()];next[0]=-1;next[1]=0;int cnt=0,i=2;while(i<str.length()){if(str[i-1]==str[cnt]){next[i++]=++cnt;}else if(next[cnt]!=-1){cnt=next[cnt];}else{next[i++]=0;}}return next;
}
int KMP(string a,string b,int *next){int i=0,j=0;while(i<a.length()&&j<b.length()){if(a[i]==b[j]){i++;j++;}else if(next[j]!=-1){j=next[j];}else{i++;}}if(j==b.length()){return i-j;}return -1;
}
bool strtrue(string a,string b){if(a.length()!=b.length()){return 0;}a=a+a;//重复//如果是b是a的拼接词的话那么b一定是a的字串，使用KMP算法int *next=getnext(b);int location=KMP(a,b,next);return location!=-1?1:0;
}
int main(){string str="abcd";string s="cdab";int flag=strtrue(str,s);string a=flag?"是旋转词":"不是旋转词";cout<<a;
}第五题
算法思想
我们可以先统计出奇数的个数count1，是偶数但不是4的倍数数字的个数count2，4的倍数数字的个数count3。我们可以分情况讨论：
如果count2为0，那么只需要数字情况如下排列即可：奇4奇4奇4......，count1个奇数就需要count1-1个4的倍数。（奇数为0时都可以，奇数为1时仅需要1个）
现在我们讨论count2不为0的情况。我们分为有无奇数。
如果没有奇数，如果count2==1仅需要1个4的倍数，如果count2>1，那么有无4的倍数均可。
如果有奇数，那么无论多少个count2，都需要1个4的倍数配对。并且奇数安排如下：4奇4奇......
仅需要count1-1个4。因为第一个4是配对count2的，我们可以接着用。最终需要count1个4的倍数。
代码展示
#include<iostream>
using namespace std;
bool iffour(int *arr,int n){int count1=0,count2=0,count3=0;//奇数个数 2的倍数但不是4的1倍数个数 4的倍数个数（包含4） for(int i=0;i<n;i++){if(arr[i]&1){ count1++;}if((!(arr[i]&1))&&(arr[i]&3)){count2++;}if(!(arr[i]&3)){count3++;}}//cout<<count1<<" "<<count2<<" "<<count3<<endl;if(!count2){//奇4奇4......if(!count1){return 1;}else if(count1==1){return count3>1?1:0;}else if(count1>1){return count3>=count1-1?1:0;} }else{if(count1==0){if(count2==1){return count3>=1?1:0;}else{return 1;}}else{return count3>=count1?1:0;}}
}
int main(){int arr[6]={1,2,2,4,2,6};int flag=iffour(arr,6);cout<<flag;
}第六题
这里没有具体的题，只是想给大家分享一个思想：动态规划下的空间压缩。将二维数组压缩为一维数组。如果一个二维数组i，j位置和它的左侧元素和上方元素有关。那么第一行和第一列肯定是需要我们初始化的，我们肯定是知道的。那么填第二行时，第二行第二个元素（第一个元素已知）其可以根据左侧和上侧推导得来，我们可以将原先第一行第一个位置元素覆盖，第二行第三个元素左侧元素为现在第一行的第一个元素，其上方元素可以直接拿出，因此也可以推导出，并覆盖第一行第三个位置，同理第一行的其它元素。这样最终第一行就变成了二维数组的第二行元素。
如果是对角线型，跟其对角线有关，大家记得用临时变量存储要覆盖的位置元素。然后更新临时变量即可。
本次分享到此结束，大家多多支持！！