第二題
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;
}
第四題
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/272529.html
標籤：其他
上一篇：堆疊的創建（基礎）
下一篇：【匯編語言】資料尋址