回文数判断

Posted on Edited on In

题目描述
回文数是指正着读和倒着读都一样的整数。例如，121是回文数，而123不是回文数。本问题要求判断一个整数是否为回文数。

输入格式
输入共 1 行，包含一个整数 x。

输出格式
输出共 1 行，如果 x 是回文数，输出 “true”；否则输出 “false”。

数据范围
-2^31 ≤ x ≤ 2^31 - 1

输入样例1：

1
121

输出样例1：

1
true

输入样例2：

1
-121

输出样例2：

1
false

输入样例3：

1
10

输出样例3：

1
false

注意事项

  • 负数不是回文数，因为负号在倒过来之后会变成数字的一部分，改变了数字的意义。
  • 可以通过将整数转换为字符串来判断是否为回文数，也可以通过数学方法直接反转整数来判断。
  • 在反转整数时，需要注意避免整数溢出的问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
using namespace std;

// 方法一：将整数转换为字符串进行判断
bool isPalindromeString(int x)
{
    if (x < 0)
    {
        return false; // 负数不是回文数
    }
    
    string s = to_string(x);
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right)
    {
        if (s[left] != s[right])
        {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

// 方法二：数学方法，反转整数后比较
bool isPalindromeMath(int x)
{
    // 特殊情况：
    // 1. 负数不是回文数
    // 2. 如果数字的最后一位是0，那么只有当数字本身是0时才是回文数
    if (x < 0 || (x % 10 == 0 && x != 0))
    {
        return false;
    }
    
    int reversedNumber = 0;
    
    // 只反转一半数字，避免整数溢出
    while (x > reversedNumber)
    {
        reversedNumber = reversedNumber * 10 + x % 10;
        x /= 10;
    }
    
    // 当数字长度为奇数时，通过reversedNumber/10去除中间位
    return x == reversedNumber || x == reversedNumber / 10;
}

int main()
{
    int x;
    cin >> x;
    
    // 使用数学方法判断回文数（更高效）
    bool result = isPalindromeMath(x);
    
    // 如果要使用字符串方法，可以取消下面这行的注释，并注释掉上面这行
    // bool result = isPalindromeString(x);
    
    if (result)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(logx)，其中 x 是输入的整数，logx 是 x 的位数。
  • 空间复杂度：O(1)（数学方法）或 O(logx)（字符串方法，用于存储字符串）。

代码解释

  • 判断回文数有两种常见的方法：将整数转换为字符串进行判断，或者使用数学方法直接反转整数进行比较。
  • 字符串方法的思想很简单：将整数转换为字符串后，从两端向中间比较字符是否相同。
  • 数学方法的思想是：通过取模和除法运算，将整数的后半部分反转，然后与前半部分进行比较。这种方法可以避免整数溢出的问题，因为我们只反转一半数字。
  • 对于数学方法，我们需要处理一些特殊情况：负数不是回文数；如果数字的最后一位是0，那么只有当数字本身是0时才是回文数。
  • 当数字长度为奇数时，反转后的数字会比原数字多一位，这时需要通过除以10来去除中间位。