2021年4月4日 腾讯笔试编程题第二题
描述：
给出一个有0-9的数字组成的字符串，相邻的两个数字和为10时可以被消去。
问最后字符的长度时多少？
例如 213792，第一步可以消成2192，第二步消解为22.所以长度为2
输入：
第一行输入一个 n表示长度
第二行输入一个字符串
输出：
输出一个整数
简单的bfs即可，在储存的时候保存前后点的位置。如果原字符串两个相邻的数之和为10，则进行一次bfs消除，在这次消除的过程中记录相应的点的前置点和后置点的位置，并且判断两端是否可以继续消除。
AC代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e6+10;int n,ans=0;struct node{int f,t,x;//f前置点的位置，t后置点的位置，x数字}a[maxn];string s;void bfs(int x){queue<pair<int,int> >q;q.push(make_pair(x,x+1));//将相邻的点放入q中while(!q.empty()){int l=q.front().first;int r=q.front().second;q.pop();a[l].x=0;//将值标记为0 表示已经被消过了a[r].x=0;a[l].t=a[r].t;//将对应的位置进行修改a[r].f=a[l].f;if(a[a[l].f].x==0){//若前置点的值为0，意思时前置点被消了，那么该点的前置点为前置点的前置点。a[l].f=a[a[l].f].f;}if(a[a[l].f].x+a[a[r].t].x==10){ //两端的值和为10q.push(make_pair(a[l].f,a[r].t));//压入队列}}}int main(){cin>>n;cin>>s;for(int i=1;i<=n;i++){a[i].x=(int)(s[i-1]-'0');a[i].f=i-1;//保存位置a[i].t=i+1;}for(int i=1;i<n;i++){if(a[i].x+a[i+1].x==10){//如若相邻的点之和为10 进行bfs消除bfs(i);//for(int k=1;k<=n;k++){//cout<<a[k].x<<" "<<a[k].f<<" "<<a[k].t<<endl;//}//cout<<endl;}}for(int i=1;i<=n;i++){ans+=(a[i].x!=0);//记录有多少个点不为0}cout<<ans<<endl;}上面是我犯傻做的，吃力不讨好！！！！！！！
更好的方法是使用栈，类似于判断括号合法一样的，最后输出多少个不合法的括号。
当栈了没有数字，则压入当前数字。
当栈里面有数字，则判断栈顶与当前数字之和能否消去，能消去则栈出栈；
反之则把当前数字入栈。
代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e6+10;int n;string s;stack<char>st;int main(){cin>>n;cin>>s;for(int i=0;i<s.size();i++){if(!st.empty()){char x=st.top();if((x-'0')+(s[i]-'0')==10){st.pop();}else{st.push(s[i]);}}else{st.push(s[i]);}} cout<<st.size();}第四题