【LeetCode】Palindrome Number(回文数)

这道题是LeetCode里的第9道题。

题目说的：

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

示例 1:
输入: 121

输出: true
示例 2:
输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:

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

这道题虽然简单，但是对于简单题，我们要做到用比较骚的方法去解题，就像这道题一样，大部分人想到的是转字符串，然后双指针 blablabla......，不错，我也是这样想的。然而进阶的要求是不使用字符串，我首先想到的是求位数，其实就是变相的使用与字符串类似的方法，具体我就不介绍了，大家懂的都懂，这里我想要说的是用一种更巧妙的方法来解这道题。

我所做的：

class Solution {

public:

    bool isPalindrome(int x) {

        if(x<0||x>2147447412)return false;

        int numSrc=x;

        int numDst=0;

        while(numSrc){

            numDst=numDst*10+numSrc%10;

            numSrc/=10;

        }

        return numDst==x;

    }

};

我得到的：

太慢了，上几行代码加个速：

static int x = []() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	return 0;

}();

我收获的：

我这道题之前的 if 条件是不包括 x>2147447412 的，后面官方加了个 2147483647 的实例，导致 int numDst 数据直接溢出，而且官方偷懒，可能只加了这一个实例，我加了这个条件后就通过了。我这个条件其实加了和没加一样，当 x=2147447399 时照样溢出，最好的解决办法是将 numDst 扩充为 long 型就一劳永逸了！

再上一个最快的解法：

static int x = []() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	return 0;

}();

class Solution {

public:

    bool isPalindrome(int x) {

        if (x < 0 || (x % 10 == 0 && x != 0)) {

            return false;

        }

        int reverseNumber = 0;

        while (x > reverseNumber) {

            reverseNumber = reverseNumber * 10 + x % 10;

            x /= 10;

        }

        return x == reverseNumber || x == reverseNumber / 10;

    }

};

这个方法是在我之上折半，最少缩短了一半的时间，而且还不用考虑数据溢出，节约内存，厉害！

static int x = []() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	return 0;

}();

class Solution {

public:

    bool isPalindrome(int x) {

        string s;

        ostringstream convert;

        convert << x;

        s = convert.str();

        return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin());

    }

};

巴特西