字符串消除 -电脑资料

   

    解决方法：贪心法

    详细描述：每次从字符串选择两个相邻可消除字符，要求是这两个字符都是当前最多和次多的，

字符串消除

。例如abbcabca，a和b各有三个，而c只有两个。就先消除ab，转成c。只转一个字符，然后重新统计整个字符串cbcabca，c有三个，而a和b都是两个，但是先搜到cb，所以转cb为a。

    原理证明：要求最终生成的字符串最短，肯定是被消除的次数最多，而且最终生成的字符串肯定只有一种字符。要达到最终消除次数最多，每次消除当前最多的字符，最好同时消除次多的字符，避免出现多个相同字符连续的情况，即可。假设不消除最多的，那么可能出现生成生成更多的最多字符，从而最终不能消除。

    具体实现（已提交通过）：

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    int max(int a,int b,int c)

    {

    int max = 0;

    if(a>b)

    {

    max = a;

    }

    else

    {

    max = b;

    }

    if(max

    {

    max = c;

    }

    return max;

    }

    char clearCh(char a,char b)

    {

    if(a==b)

    {

    return a;

    }

    if((a == 'a' && b == 'b') || (a == 'b' && b == 'a'))

    {

    return 'c';

    }

    if((a == 'b' && b == 'c') || (a == 'c' && b == 'b'))

    {

    return 'a';

    }

    if((a == 'a' && b == 'c') || (a == 'c' && b == 'a'))

    {

    return 'b';

    }

    return a;

    }

    void clearFirst(const char *s,char *p,char a,char b)

    {

    int i=0;

    int clearFlag = 0;

    for(i=0;i

    {

    if((s[i]==a && s[i+1]==b)||(s[i]==b && s[i+1]==a))

    {

    strncpy(p,s,i);

    *(p+i) = clearCh(a,b);

    strncpy(p+i+1,s+i+2,strlen(s)-i-2);

    clearFlag = 1;

    break;

    }

    }

    if(clearFlag == 0)

    {

    for(i=0;i

    {

    if((s[i]==a && s[i+1]!=a)||(s[i]!=a && s[i+1]==a))

    {

    strncpy(p,s,i);

    *(p+i) = clearCh(s[i],s[i+1]);

    strncpy(p+i+1,s+i+2,strlen(s)-i-2);

    clearFlag = 1;

    break;

    }

    }

    }

    //printf("%s\n",p);

    }

    int minLength(const char *s)

    {

    int a=0,b=0,c=0,i=0,minLen=0;

    for(i=0;i

    {

    if(s[i] == 'a')

    {

    a++;

    }

    if(s[i] == 'b')

    {

    b++;

    }

    if(s[i] == 'c')

    {

    c++;

    }

    }

    if(a == 0 && b == 0)

    {

    minLen = c;

    }

    else if(b == 0 && c == 0)

    {

    minLen = a;

    }

    else if(a == 0 && c == 0)

    {

    minLen = b;

    }

    else

    {

    char *p = new char[strlen(s)];

    if(p==NULL)

    {

    return -1;

    }

    memset(p,0,sizeof(char)*(strlen(s)));

    if(a>=b && b>=c)

    {

    clearFirst(s,p,'a','b');

    }

    else if(a>=c && c>=b)

    {

    clearFirst(s,p,'a','c');

    }

    else if(b>=a && a>=c)

    {

    clearFirst(s,p,'b','a');

    }

    else if(b>=c && c>=a)

    {

    clearFirst(s,p,'b','c');

    }

    else if(c>=b && b>=a)

    {

    clearFirst(s,p,'c','b');

    }

    else if(c>=a && a>=b)

    {

    clearFirst(s,p,'c','a');

    }

    minLen = minLength(p);

    delete(p);

    }

    return minLen;

    }

    //start 提示：自动阅卷起始唯一标识，请勿删除或增加，

电脑资料

《字符串消除》(https://www.unjs.com)。

    int main()

    {

    return 0;

    }

    //end //提示：自动阅卷结束唯一标识，请勿删除或增加。