解题思路

回文数就是正着读和反着读都一样的数，比如 121、2442、37073。

题目要求统计 1 到 N 之间有多少个回文数。

判断一个数是不是回文数：把数字反转，如果和原数相等就是回文数。

参考代码

#include <iostream>
using namespace std;

bool isPal(int x) {
    int tmp = x, rev = 0;
    while (tmp > 0) {
        rev = rev * 10 + tmp % 10;
        tmp /= 10;
    }
    return rev == x;
}

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (isPal(i)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N log N)
• 空间复杂度：O(1)