回文数 良心的详细注释

一道考细节的编程题。很有蓝桥杯那味了。

题意

给定数位$0-90-9$的出现次数，要求用它构造不含有前导0的最小的回文数，如果无法构造回文数，输出-1.

思路

1. 如果有两个及以上的数位都出现了奇数次，则无法构造回文串
2. 如果$00$出现2次以上，而且其他只有一个数位出现过且只出现了一次，则无法规避前导0，所以也无法构造（样例4）
3. 下面开始构造：所有的数位次数累加，得到最终的字符串长度$nn$，如果有数位出现次数为奇数，那么必然要放一个它在最中间
4. 因为不能有前导0，所以如果有多个0的话，从1找到9，找到最小的数，首尾各贴一个
5. 然后从小的数位到大的数位，首尾同时铺过去就完事了。

PS. 另需特判0出现多次而没有其他数字的情况，此时无法构造，对应12行。

solution

写了手纯C

#include <stdio.h>
int a[20];
char s[105];
int main() {
    int odd = 0, sum = 0, odp, valid = 0, vak;
    for (int i = 0; i < 10; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
        if (a[i] & 1) ++odd, odp = i;
        if (a[i] && i > 0) ++valid, vak = i;
    }
    if (valid == 0 && a[0]>1) return puts("-1"), 0;
    if (odd > 1 || (valid == 1 && a[vak] == 1 && a[0])) return puts("-1"), 0;
    if (odd) s[sum / 2] = '0' + odp, --a[odp];
    if (sum > 1) {
        int p = 1, L = 0, R = sum - 1;
        while (!a[p] && p < 10) ++p;
        s[L++] = '0' + p, s[R--] = '0' + p, a[p] -= 2;
        p = 0;
        while (p < 10) {
            for (int i = 0; i < a[p] / 2; ++i)
                s[L++] = '0' + p, s[R--] = '0' + p;
            ++p;
        }
    }
    s[sum] = 0, puts(s);
    return 0;
}

详细注释

#include <stdio.h>
int a[20];
char s[105];
int main() {
    int odd = 0;  //有多少个奇数
    int odp;      //出现此时为奇数的那个数位
    int sum = 0;  //所有数位出现次数之和，如果可以构造，也就是回文数的长度
    int valid = 0;  //出现次数不为0的数位有多少个
    int vak;  //出现次数不为0的那个数位（用来特判第二点，也就是样例4）
    for (int i = 0; i < 10; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
        if (a[i] & 1) ++odd, odp = i;
        if (a[i] && i > 0) ++valid, vak = i;
    }
    if (valid == 0 && a[0]>1) return puts("-1"), 0;
    if (odd > 1 || (valid == 1 && a[vak] == 1 && a[0]))
        return puts("-1"), 0;                   //无法构造
    if (odd) s[sum / 2] = '0' + odp, --a[odp];  //贴在中间，直接减掉省了很多事
    if (sum > 1) {  //如果只有一个数位且出现一次，这样会越界
        int p = 1, L = 0, R = sum - 1;  // p用来遍历数位 LR就是回文数的左右游标
        while (!a[p] && p < 10) ++p;  //找到最小的非零且会出现的数位
        s[L++] = '0' + p, s[R--] = '0' + p, a[p] -= 2;  //左右各贴一个
        p = 0;                                          //游标重置
        while (p < 10) {  //从小到大，由外而内铺过去
            for (int i = 0; i < a[p] / 2; ++i)
                s[L++] = '0' + p, s[R--] = '0' + p;
            ++p;
        }
    }
    s[sum] = 0, puts(s);  //封口 输出
    return 0;
}