题解 | #回文数#

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int array[10];//记录0~9的个数
    int num=0;//记录出现次数为奇数的个数
    int sum = 0;//记录总位数
    for(int i=0;i<10;i++)
    {
        cin>>array[i];
        sum+=array[i];
        if(array[i]%2==1)
            num++;
    }
    int* huiwen = new int[sum/2+1];
    if(num>1)
    {
        cout<<-1;
        return 0;
    }
    else if(num==0)//全为偶数
    {
        int i=1;
        while(array[i]==0)//确定回文数第一位的位置i
            i++;
        array[i]-=2;
        huiwen[0]=i;
        for(int i=1;i<sum/2;i++)//把剩下sum/2-1位确定下来
        {
            for(int j=0;j<10;j++)
            {
                if(array[j]!=0)
                {
                    array[j]-=2;
                    huiwen[i] = j;
                    break;
                }
            }
        }
        for(int i=0;i<sum/2;i++)
            cout<<huiwen[i];
        for(int i=sum/2-1;i>=0;i--)
            cout<<huiwen[i];
    }
    else if(num==1)//有一个奇数次数的数，huiwen数组的最中间一位应该放该数
    {
        if(sum-array[0]==1)
        {
            cout<<-1;
            return 0;
        }
        int i=1;
        while(array[i]==0)//确定回文数第一位的位置i
            i++;
        array[i]-=2;
        huiwen[0]=i;
        for(int i=0;i<10;i++)//确定回文数最中间位置的数
        {
            if(array[i]%2==1)
            {
                array[i]--;
                huiwen[sum/2]=i;
                break;
            }
        }
        for(int i=1;i<sum/2;i++)//把剩下sum/2-1位确定下来
        {
            for(int j=0;j<10;j++)
            {
                if(array[j]!=0)
                {
                    array[j]-=2;
                    huiwen[i] = j;
                    break;
                }
            }
        }
        for(int i=0;i<sum/2+1;i++)
            cout<<huiwen[i];
        for(int i=sum/2-1;i>=0;i--)
            cout<<huiwen[i];
    }
    return 0;
}

个人习惯，对于回文数我都会只定义一个一半长度的数组（因为回文数的对称性），这样每次打印回文数都先正向遍历一遍，再反向遍历一遍。注意：这里要根据回文数长度分奇偶来讨论！ 本题要注意第一位是非常特殊的。0不能放第一位（除非只有1个零）。且代码中定义了num以记录0~9中出现次数为奇数的个数，如果**num>1或者只有几位0和一位其他数时（即sum-array[0]==1）**一定不能组成回文数。本题主要就是根据num来分类讨论。 代码中另开辟了array数组，array[i]表示i数字在回文数中出现的次数。同时本题最关键的思想就是：要使组成的回文数最小，则优先使用array中靠前的索引。