题目

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

示例 1：

1
2
输入：x = 121
输出：true

示例 2：

1
2
3
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

1
2
3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

  • -231 <= x <= 231 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

基础解法

使用索引的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <string>
using namespace std;
class Solution {
public:
    bool isPalindrome(int x) {
        // 特定值是回文数
        if (x >= 0 && x < 10) { return true; }
        
        // 小于10的肯定不是回文数
        if (x < 0) { return false; }
        
        // 先将x转换为字符串
        string str = to_string(x);
        for (int i = 0; i < str.length(); i++)
        {
            if (str[i] != str[str.length() - i - 1])
            {
                return false;
            }
        }
        return true;
    }
};

直接从两边开始比较就好了

使用指针的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
using namespace std;
class Solution {
public:
    bool isPalindrome(int x) {
        // 0-9是回文数而小于0的肯定不是回文数
        if (x < 0 || (x >= 0 && x < 10)) { return x >= 0; }
        
        // 先将x转换为字符串
        string str = to_string(x);
        int left = 0, right = str.length() - 1;
        while (left < right)
        {
            if (str[left] != str[right])
            {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
};

这种解法要比上一种解法快不少,因为经过的判断不是很多

进阶解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
using namespace std;
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            x = x / 10;
        }
        if (x == y || x == y / 10) { return true; }
        else { return false; }
    }
};

这种方法是取数字的一半,最后比较这两个一半是否相等,如果感觉不好理解的话可以看下面的表

reversedHalf x
输入12321的情况
0 12321
1 1232
12 123
123 12
输入11的情况
0 11
1 1