解题思路

一个数本身不是回文数，但如果它在 2 进制或者 16 进制下是回文数，就称它为半个回文数，把符合条件的数都找出来。

思路：写一个通用的判断回文的函数，判断一个数在任意进制下是不是回文。

1. 把一个数在某种进制下的每一位拆出来存进数组：
   • 不断取这个数除以进制的余数，就是最低位
   • 再把这个数除以进制，去掉这一位，继续取
2. 拆完之后，把数组的首尾对应位置两两比较
   • 只要有一对不一样，就不是回文
   • 全部一样，就是回文
3. 对每个数分别判断：
   • 十进制回文吗？
   • 二进制回文吗？
   • 十六进制回文吗？
4. 如果十进制不是回文，而且二进制或十六进制是回文，就输出这个数

为什么要判断三种进制？ 题目要求本身不是回文（十进制），但在 2 进制或 16 进制下是回文才算半个回文数。

举例：

• 417 十进制不是回文；转成 16 进制是 1A1，正反一样，是回文，所以算半个回文数
• 121 本身就是回文，直接排除

参考代码

#include <iostream>
using namespace std;

// 判断 x 在 base 进制下是不是回文数
bool isPal(long long x, int base) {
    int d[40], len = 0;  // d 存这个数在 base 进制下的每一位
    // 一位一位拆出来
    while (x > 0) {
        d[len++] = x % base;  // 取出最低位
        x /= base;            // 去掉最低位
    }
    // 首尾对应位置比较
    for (int i = 0; i < len / 2; i++) {
        if (d[i] != d[len - 1 - i]) return false;  // 有一对不一样就不是回文
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        bool pal10 = isPal(x, 10);  // 十进制下是不是回文
        bool pal2 = isPal(x, 2);    // 二进制下是不是回文
        bool pal16 = isPal(x, 16);  // 十六进制下是不是回文
        // 本身不是回文数，但在二进制或十六进制下是回文，就是半个回文数
        if (!pal10 && (pal2 || pal16)) {
            cout << x << endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(n × 位数)，每个数要拆三种进制各一次
• 空间复杂度：O(1)，只用了固定大小的数组和几个变量