删除字符串中具有相同值的任何相邻字母对“>” [

Question

例如-

aa

ab ccdd d-> abd

aa

a cc c bbcc cd-> a cc d->广告

abba

->空刺我首先尝试了以下方法。调用splitString函数，直到无法进一步减小字符串为止（即我们提供的字符串的长度（a）=执行操作后获得的字符串的长度）。对于大约10 ^ 5的值，此代码给出

超出内存限制（MLE）

错误，但是对于小于10 ^ 5的值运行正常。

#include<bits/stdc++.h>
using namespace std;

void splitString(string str)
{
    int a=str.length();
    for(int i=0; i<str.length()-1; i++)
    {
        if(str[i]==str[i+1]){str[i]=1; str[i+1]=1;}
    }

    string alpha="";
    for (int i=0; i<str.length(); i++)
    {
        if(str[i] >= 'a' && str[i] <= 'z')
            alpha.push_back(str[i]);
    }

    int b=alpha.length();
    if(a==b)
    {cout <<b<<"\n"<<alpha; return;}
    else
    {splitString(alpha);}

}

int main()
{
    int n; string str; cin>>n>>str;

    splitString(str);

    return 0;
}

我放弃递归的第二种方法：但是，对于10 ^ 5左右的值，这会给出
Time Limit Exceeded（TLE）

错误，但对于较小的值则可以正常工作。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define size 100005

void foo(char *s){
    int len = strlen(s);
    int i, j;
    j = 0;
    for(i = 0; i < len; i++)
    {
        if(s[i] != '$')
        {
        s[j] = s[i]; j++;
        }
    }
    s[j] = '\0';
}
char* super_reduced_string(char* s){
    int len = strlen(s);
    int i;
    for(i = 1; i < len; i++){
        if(s[i] == s[i-1])
        {
            s[i] = s[i-1] = '$';
            foo(s);
            len = strlen(s);
            i = 0;
        }
    }
    return s;
}

int main() {
    int n; scanf("%d", &n);
    char s[size]={0};
    scanf("%s", s);
    char* result = super_reduced_string(s);

        printf("%d", strlen(result));
        printf("\n");
        printf("%s\n", result);
    return 0;
}

我如何
优化

这些解决方案？[Input1Input2Input3

例如-aaabccddd-> abd aaacccbbcccd-> accd-> ad abba->空刺，我首先尝试了以下方法。将调用splitString函数，直到无法进一步减少字符串为止（即...

Answer 1

您可以对当前算法进行一些改进，例如直接删除字符而不将'$'存储为填充符。例如进行一次就地配对移除通行证（例如您的第二版，但在第一对之后不停止），然后重复直到长度停止变化。 （循环而不是尾递归）。