题解 | #构造字符串#

对于前后字母不一样可以轻松判断，主要是对于前后字母大小一样情况下的讨论 例ACDBCB 第一个肯定取A 原字符数组就变为CDBCB 第二个肯定取B 原字符数组就变为CDCBC 这时候前后都为C，就需要我们去判断第二个字母的字典序了。 前面第二个字母为D，后面第二个字母为B，那我们就应该取最后一个了。 对于一些极端的字符数组，例如AAAAABAAA就需要连续判断到第四个字符，所以需要使用递归解决这种情况 第一次写题解，如果有疏漏，请指出，感谢

#include<stdio.h>
int max(int a, int b, char S[2010], char T[2010])//值传递，防止对原数据造成影响
{
    a++;        
    b--;     //由于对a，b进行更新，判断前面第二个字母与后面第二个字母的字典序
    if (S[a] > S[b])
    {
        return 1;  //如果前面第二个字母的 字典序 大于 后面第二个字母的字典序，返回1
    }
    else if (S[a] < S[b])
    {
        return 0; //如果前面第二个字母的 字典序 小于 后面第二个字母的字典序，返回0
    }
    else
    {
        return max(a, b, S, T);   //如果前面第二个字母与后面第二个字母相同，递归函数，判断第三个字母的字典序
    }
}
int main()
{
    int x;
    int a, b;            //a表示取到S数组前面第几个字母了，b表示取到S数组后面第几个字母了
    char S[2010], T[2010];   //创建两字符数组
    scanf("%d", &x);      //接收x
    scanf("%s", S);       //接收S数组
    a = 0, b = x - 1;    //对a b进行初始化，a为最小下标，b为最大下标
    for (int i = 0; i < x; i++)  //对整个字符串进行遍历，确保每一个字母都被分配
    {
        if (S[a] > S[b])      //由于只有大写字母，直接利用asc码进行比较，asc码小则字典序小   
        {
            T[i] = S[b];     //将字典序小的赋给T
            b--;            //对b进行更新，表示最后一位字母已经被删除
        }
        else if (S[a] < S[b]) 
        {
            T[i] = S[a];     //同理
            a++;
        }
        else                 //处理前面的字母等于后面字母的特殊情况
        {
            if ( max(a, b, S, T))   //调用函数 根据 返回值 判断取那个更好（转到代码第二行）
            {
                T[i] = S[b];         //如果返回真，则说明取前面的字母更好
                b--;                 //对b进行更新
            }
            else
            {
                T[i] = S[a];         //如果返回假，则说明取后面的字母好
                a++;
            }
        }
    }
    for (int i = 0; i < x; i++)   //因为定义的一个大的字符数组，防止输出没用的字符，使用循环一个个输出
    {
        printf("%c", T[i]);       //输出单个字符
    }
    return 0;
}