Byte runout 2019 spring recruit R & D part programming question summary

My name is Wang dachui. I'm the editor of a publishing house. I am responsible for proofreading the English manuscripts submitted. This job is very annoying because I have to correct countless spelling mistakes every day.
However, excellent people can always find the truth in ordinary work. I found a shortcut to finding spelling mistakes:

1. If three identical letters are connected together, it must be a spelling mistake. Just remove one: for example, hello - > hello
 2. If two pairs of identical letters (AABB type) are connected together, it must be a spelling mistake. Just remove one letter from the second pair: for example, hello - > hello
 3. The above rule gives priority to "left to right" matching, that is, if it is AABBCC, although both AABB and BBCC are misspelled, priority should be given to repairing AABB, and the result is AABCC

I'm a genius! I studied excavator and program design in Lanxiang. I wrote an automatic calibrator according to this principle, and the work efficiency took off from then on.
It won't be long before I become CEO, become chairman, marry Bai Fumei and reach the peak of my life. I'm a little excited to think about it!
......
Unexpectedly, I was fired. When I left, the boss said to me, "you should be conscientious, diligent, share your capital, and if you can do it,
Line by line. The person who does well in one field can do well in all fields. If not, do what you do, do what you do, do what you do. " Now I'm in a trance

Please listen to the question: please realize the automatic proofreading program of sledgehammer

Input format

The first line includes a number n, which indicates how many strings to be verified are included in this use case. 1<=N<=50

Followed by N lines, each line is a string to be verified. String length does not exceed 1000

Output format

N lines, each line includes a repaired string.

sample input

2
helloo
wooooooow

sample output

hello
woow

Solution: a typical check-in question, because the data scale determines that any method can pass. Three complexity O(n) methods are introduced here.

(1) Single linked list method

In the title, it is required to eliminate (delete) elements, which does not avoid moving elements after deletion. Using chain structure is a better choice.

int i,j,t,n,nex[10005]= {0};
    char c[10005]= {0};
    cin>>t;
    while(t--)
    {
        scanf("%s",c+1);/**< Read from subscript 1 */
        n=strlen(c+1);
        for(i=1; i<n; i++) /**< Construct static linked list*/
            nex[i]=i+1;
        nex[n]=0;/**< The tail node pointer is 0 */
        int c1=1,c2,c3,c4;/**< Four pointers are defined to handle the problem, with four adjacent characters in turn */
        while(c1)
        {
            c2=nex[c1],c3=nex[c2],c4=nex[c3];/**<Meet AAA or AABB deletion  */
            if(c2&&c[c1]==c[c2]&&( (c3&&c[c2]==c[c3]) || (c4&&c[c3]==c[c4])  ))
                nex[c2]=c4;/**< Note that when determining the conditions, be sure to ensure that the pointers c2, c3 and c4 are not 0, that is, they are not null pointers */
            else
                c1=c2;
        }
        c1=1;
        while(c1)
        {
            cout<<c[c1];
            c1=nex[c1];
        }
        cout<<endl;
    }
    return 0;

(2) Stack structure elimination

The problem of string elimination can be solved by stack structure. The string is stored on the stack. i is the current processing character. If the two elements at the top of the stack are AA, i is also A, or i and i+1 are BB, i does not need to be put on the stack. In other cases, i must be put on the stack.

The standard stack structure can only get one element at the top of the stack, which cannot solve the AA judgment. Therefore, the stack structure must be handwritten.

int i,j,t,n,top=0;
    char c[10005]= {0},st[1005];/**< Hand write a stack structure st, and top is the pointer to the top of the stack */
    cin>>t;
    while(t--)
    {
        scanf("%s",c+1);/**< Read from subscript 1 */
        n=strlen(c+1);
        top=0;
        for(i=1;i<=n;i++)
        {
            if(top>=2) /**< It can only be judged if there are more than 2 elements in the stack */
            {
                if(st[top-1]==st[top-2]&&(c[i]==st[top-1]||c[i]==c[i+1]))/**< Meet AAA or AABB equal conditions */
                  continue;
            }
            st[top++]=c[i];
        }
        for(i=0;i<top;i++)/**< Output all elements in the stack */
            cout<<st[i];
        cout<<endl;
    }
    return 0;

(3) Greedy algorithm

Think about it. When the left side of i is AA, there are three possibilities: AAA, AABB and AABC. The first two can be considered that i is deleted. Just continue to check i+1. When AABC appears???? In this case, it is determined that AAB is no longer needed (it is impossible to participate in elimination) next time. Check whether C and C are the same and continue to scan backward

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i=2,j,p1=1,p2=0,t;
    cin>>t;
    while(t--)
    {
        i=2,p1=1,p2=0;
        string s;
        cin>>s;
        while(i<s.size())
        {
            if(s[p1]!=s[p2]) /**< Find AA first */
            {
                p1++,p2++,i++;
                continue;
            } /**< If s[i] can form AAA or AABB, clear s[i] and continue to check backward */
            while(s[i]==s[p1]||s[i]==s[i+1])
                s[i++]=' ';/**< Clear with space characters */
            p2=i+1,p1=i+2,i+=3;/**< It must be AABC. Let p2 point to c next time */
        }
        for(i=0; i<s.size(); i++)
            if(s[i]!=' ')
                cout<<s[i];
        cout<<endl;
    }
    return 0;
}