解题思路

什么是回文数？

回文数就是正着读和反着读一模一样的数。比如：

• 1：反过来还是 1，是回文数
• 22：反过来还是 22，是回文数
• 99：反过来还是 99，是回文数
• 252：反过来还是 252，是回文数
• 1221：反过来还是 1221，是回文数

而像 98、110 这样的数就不是回文数：98 反过来是 89，110 反过来是 11（最前面的 0 不用写），都和原来的数不一样。

怎么判断一个数是不是回文数？

最直接的方法：把数反转过来，然后和原数比较。如果反转后和原来一模一样，就是回文数。

反转的方法用 while 循环，一位一位地把数字搬到新数 r 里：

• r = r * 10 + t % 10：取出 t 的最后一位，放到 r 的末尾
• t = t / 10：去掉 t 的最后一位

循环条件是 t > 0，也就是说把每一位都搬完为止。

比如 x = 121，模拟一下反转过程：

t = 121, r = 0
第 1 步：r = 0 * 10 + 121 % 10 = 1，t = 121 / 10 = 12
第 2 步：r = 1 * 10 + 12 % 10 = 12，t = 12 / 10 = 1
第 3 步：r = 12 * 10 + 1 % 10 = 121，t = 1 / 10 = 0
循环结束：r = 121，和原来的 x = 121 一样 → 121 是回文数

再比如 x = 98，同样模拟一下：

t = 98, r = 0
第 1 步：r = 0 * 10 + 98 % 10 = 8，t = 98 / 10 = 9
第 2 步：r = 8 * 10 + 9 % 10 = 89，t = 9 / 10 = 0
循环结束：r = 89，和原来的 98 不一样 → 98 不是回文数

用题目样例完整走一遍

题目给的 3 行 3 列二维数组：

1   22  98
34  121 110
100 210 323

按输入顺序（从上到下、从左到右）一个一个判断：

• 1：反转后还是 1，1 == 1 ✓ → 输出 1
• 22：反转后还是 22，22 == 22 ✓ → 输出 22
• 98：反转后是 89，89 ≠ 98 ✗ → 不输出
• 34：反转后是 43，43 ≠ 34 ✗ → 不输出
• 121：反转后还是 121，121 == 121 ✓ → 输出 121
• 110：反转后是 11，11 ≠ 110 ✗ → 不输出
• 100：反转后是 1，1 ≠ 100 ✗ → 不输出
• 210：反转后是 12，12 ≠ 210 ✗ → 不输出
• 323：反转后还是 323，323 == 323 ✓ → 输出 323

最终输出为：

1
22
121
323

和题目给的样例输出完全一致。

为什么输出顺序就是输入顺序？

因为我们是按双重循环的顺序读入的：外层循环 i 控制行（从上到下），内层循环 j 控制列（从左到右），一行一行、一列一列地读。每读到一个数，就立刻判断是不是回文数、是就立刻输出，所以输出顺序和输入顺序完全一样，根本不用把回文数存下来再排一次序。

参考代码

// 问题：【入门】找回文数
// 思路：读入二维数组的每个数，把数反转后和原数比较，相等就是回文数，按读入顺序输出
#include <iostream>

using namespace std;

int main()
{
    // n 表示行数，m 表示列数
    int n, m;
    cin >> n >> m;

    // 双重循环，一行一行地读入数组里的每个数
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int x;   // x 是当前读到的那个数
            cin >> x;

            // 判断 x 是不是回文数：把 x 倒过来得到 r，如果 r 和 x 一样，就是回文数
            int t = x;   // t 用来一位一位地拆 x，注意不能直接改动 x
            int r = 0;   // r 用来存放反转后的数
            while (t > 0)
            {
                r = r * 10 + t % 10;   // 取出 t 的最后一位，放到 r 的末尾
                t = t / 10;            // 去掉 t 的最后一位
            }

            // 反转后和原来一样，说明正着读反着读都一样，是回文数，输出它
            if (r == x)
            {
                cout << x << endl;
            }
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：双重循环一共读入 n × m 个数，每个数最多 4 位（最大 9999），反转循环最多执行 4 次，所以时间复杂度是 O(n × m)。题目保证 n、m ≤ 100，最多一万个数，跑得飞快。
• 空间复杂度：只用了几个 int 变量（n、m、x、t、r、i、j），没有使用数组，所以空间复杂度是 O(1)。