算法

模拟/栈

题目描述

对于一个仅有ST组成的字符串，不断删除其中最左侧的“ST”子串，直到无法删除。

解题思路

考虑使用一个链表进行相应操作。

代码

#include<iostream>
#include<string>
using namespace std;
const int maxn=200010;
struct At{
    char c;
    At* next;
    At* last;
}   c[maxn];
int main(){
    string s;
    cin>>s;
    //
    int size=s.size();
    c[0]={s[0],&c[1],NULL};
    for(int i=1;i<size-1;i++){
        c[i]={s[i],&c[i+1],&c[i-1]};
    }
    c[size-1]={s[size-1],NULL,&c[size-2]};
    //
    int t=maxn;
    At* x=&c[0];
    while(t--){
        int update=0;
        for(At* i=x;i->next!=NULL;i=i->next){
            if(i->c=='S'&&i->next->c=='T'){
                if(i->last!=NULL){
                    x=i->last;
                    x->next=i->next->next;
                    if(i->next->next!=NULL)
                        i->next->next->last=x;
                }
                else{
                    x=i->next->next;
                    if(i->next->next!=NULL)
                        i->next->next->last=NULL;
                }
                size-=2;
                update=1;
                break;
            }
        }
        if(!update||size==0||x==NULL)
            break;
    }
    cout<<size<<endl;
    return 0;
}

题目总结

使用栈将更加简单且易于实现。

题目原文

Problem Statement

东东有一个字符串X，该串包含偶数个字符，一半是 S 字符，一半是 T 字符
东东可以对该字符串执行 1010000 次操作：如果存在 ST 是该串的子串，则删除掉最左边的 ST。
即 TSTTSS⇒TTSS、SSSTTT⇒SSTT⇒ST⇒空

Input

(2 ≦ |X| ≦ 200,000)

Output

输出最终串的长度

Sample Input 1

TSTTSS

Sample Output 1

4