2021年4月4日腾讯笔试

第二题

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){ //两端的值和为10
			q.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;
}

第四题