今天是一个特殊的日子

2021年12月2日

我们用纯数字来表示就是

20211202

它是一个无论是从头读起还是从尾读起都是一样的数字，这样的数字我们称其为回文数。

类似的有

123321 3468643 101

为了纪念今天，引申出一道来自leetcode的简单的算法题 Leetcode 9.回文数。

题目是这样描述的

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

第一种解法

根据题意，我们用string num来表示整数x，我们只需要对比num[i]与num[num.size()-i-1]是否相同即可,贴上代码。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPalindrome(int x) {
        string num=to_string(x);
        for(int i=0;i<num.size()/2;i++)
        {
            if(num[i]!=num[num.size()-i-1])
                return false;
        }
        return true;
    }
};

第二种解法

下面描述另一种解法。

如果x确实是一个回文数，那么将其倒转后也与原数相等，我们只需要判断x与倒转后的结果是否相等即可。

需要特别强调一点的是,虽然形参x是以int类型定义，但倒转过后长度有可能会超出int的长度，所以我们应该使用long rev来承接倒转后的数据。（PS：由于LeetCode的C++编译器极其严格，在做题时我不得不添加一个if来判断rev是否超出长度，这当然也是另外的做法，毕竟条条大路通罗马）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPalindrome(int x) {
        int num=x;
        int rev=0;
        long i;
        if(x<0)
            return false;
        while(num)
        {
            i=rev*10+num%10;
            if(i<INT_MAX)
                rev=i;
            else
                return false;
            num/=10;
        }
        if(x==rev)
            return true;
        return false;
    }
};

非常简单，但这样的解法肯定不是最优解。如果您有更好的解决方法，欢迎在下方评论区回复。

PS ：

关于倒转数据还有更优雅的函数来直接代替文中第二种解法的代码示例中巨大的while段，但似乎Leetcode没有这样的函数。
第一个 reverse(iterator begin,iterator begin)，来自algorithm库，适合容器使用。
第二个 strrev(string str),来自string.h库,适合string类型的变量使用。