回文数
1、题目大意
题目描述
Froggy 分别给出 10 个数码的出现次数，你需要找到一个由这些数码组成的最小的数，满足：
1. 这个数是回文的。
2. 不能有前导 0。
注：假设这个数字长度是 L，那么这个数是回文的当且仅当对于任意的 i∈[1,L]，第 i 位的数码和第 L−i+1 位的数码相同。
快来帮帮 Froggy 吧！
输入描述:
一行 10 个自然数，分别表示数码0∼9的出现次数。
输出描述:
如果无解，只输出 “-1”。（不含引号）否则，输出一个数表示最小的解。
2、问题分析以及代码求解
回文数该类问题也遇到了很多，一般使用string类进行维护。
思路如下：1、首先考虑不能输出回文数而是输出-1的情况：
总共两种：第一是具有前导0；
第二有2种小情况：①0~9中某一个数的个数是奇数个，这时需要满足0~9所有数的个数为奇数个，否则无法生成回文数。
②0~9中有超过1种数的个数为奇数个，此时一定无法生成回文数。
2、其他情况均能生成回文数，根据回文数的特点，只需要维护前半部分的数据，后半部分数据通过逆序进行输出。
3、维护数据时，直接从0~9开始维护，即使有0的存在，仍按照0~9的顺序进行维护。
4、后续判断是否有前导0的存在，若有前导0的存在，暴力搜索是否还有其他数字参与维护回文数，若有，交换两者的位置即可。
5、输出时判断是否是前导0，若是输出-1；否则先正序输出，接着逆序输出。不过需要一个注意点：若0~9的总个数为奇数个的时候，需要定义一个变量维护个数为奇数的值，后续在输出时输出一次即可。
#include <bits/stdc++.h>
using namespace std;
int a[10],sum,is;
int dex = 11;
string s;
bool have0;
int main()
{
for (int i = 0;i < 10;i++){
scanf("%d",&a[i]);
sum += a[i];
if (a[i] % 2 == 1) is++,dex = min(dex,i);
}
if ((sum % 2 == 0 && is != 0) || (sum % 2 == 1 && is != 1)){
cout << -1;
return 0;
}
for (char i = 0;i <= 9;i++)
for (int j = 1;j <= a[i] / 2;j++) s += (i + '0');
if (s[0] == '0')
for (int i = 1;i < s.length();i++)
if (s[i] != '0'){
swap(s[0],s[i]);
break;
}
if (s[0] == '0') cout << -1;
else{
for (int i = 0;i < s.length();i++) cout << s[i];
if (sum % 2 == 1) cout << dex;
for (int i = s.length() - 1;i >= 0;i--) cout << s[i];
}
return 0;
}
3、芝士链接
贪心、模拟、思维4、洞见总结
遇到回文数该类题型时，一般采取string类维护数据，然后根据题目要求转变为对字符串操作。
投递百度等公司10个岗位 >
查看2道真题和解析