字符串消除-庞果网题目

详细描述：每次从字符串选择两个相邻可消除字符，要求是这两个字符都是当前最多和次多的。例如abbcabca，a和b各有三个，而c只有两个。就先消除ab，转成c。只转一个字符，然后重新统计整个字符串cbcabca，c有三个，而a和b都是两个，但是先搜到cb，所以转cb为a。

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

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

 

#include <cstdio>  
#include <cstdio>  
#include <string>  
#include <cstring>  
#include <ctime>  
#include <cstdlib>  
  
using namespace std;  
  
int max(int a,int b,int c)  
{  
    int max = 0;  
    if(a>b)  
    {  
        max = a;  
    }  
    else  
    {  
        max = b;  
    }  
    if(max<c)  
    {  
        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<strlen(s)-1;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<strlen(s)-1;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<strlen(s);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 提示：自动阅卷起始唯一标识，请勿删除或增加。  

int main()  

{     

    return 0;  

}   

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

补充：软件开发 , C++ ,