LeetCode题集-9

产品出库设备

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

01、反转字符串法

此题我第一反应就是直接把整数转为字符串，然后通过字符串Reverse方法，反转字符串，最后再比较整数字符串和反转后字符串是否相等即可得出结果。代码实现如下：
//反转字符串法public static bool IsPalindrome1(int x){    var strX = x.ToString();    //反转字符串    var reversedStr = new string(strX.Reverse().ToArray());    //比较入参和反转后字符串是否相等    return strX == reversedStr;}02、反转字符数组法

此方法和反转字符串一脉相通，只是实现选用了不同的方法，此法是把整数字符串转为字符数组，然后再深拷贝一份用于反转的字符数组，通过Array.Reverse方法进行反转，最后通过SequenceEqual比较两个字符数组值是否相等。
其中有以下两个点容易出错：
其一因为字符数组是引用类型必须使用深拷贝，而不能像字符串那样直接赋值，深拷贝有很多种办法ToArray是比较简洁的方式；
其二因为本题要求是比较两个字符数组的值是否相等，因此不能直接使用==比较；
具体实现代码如下：
//反转字符数组法public static bool IsPalindrome2(int x){    //x转为字符数组    var strXChars = x.ToString().ToCharArray();    //深拷贝一份字符数组用于反转    var reversedChars = strXChars.ToArray();    //反转字符数组    Array.Reverse(reversedChars);    //比较入参和反转后字符串是否相等    return strXChars.SequenceEqual(reversedChars);}03、双指针法

前面两个方法本质上都是在使用转为字符串的方法处理，我们进阶一下尝试不用转字符串的方式来处理。
虽然不用转字符串的方式，但是我们可以借鉴其思想，比如前面题目处理回文子串思想。我们是否可以像字符串一样，从整数的两端由外向内逐一比较两端的数字，如果都相等则结果为回文数。
在不转成字符串的情况下，怎么拿到整数的首尾数字呢？尾数字可以通过取余的方式获取，那么首数字要怎么获取呢？
比如12345，如果我们想要取到首数字1，那么就可以通过12345/10000=1获取，那么10000要怎么获取呢？我们可以对整数进行循环取整，假设除数div=1，取1次整则div乘10，最终得到10000。
然后我们就可以通过x/div取整获取左边数字，通过x%10取余获取右边数字，然后比较左右是否相等，如果相等则把左右两边已比较过的数字去掉，对剩下的整数继续比较，直至所有数字完成比较。
具体实现代码如下：
//双指针public static bool IsPalindrome3(int x){    //负数肯定不是回文数    if (x < 0)    {        return false;    }    //定义除数变量，用于从前截取数字    var div = 1;    //通过循环对x取整，然后在乘10    //求得可以获取x第1位数字对应的除数    //比如12345，则除数为10000    while (x / div >= 10)    {        div *= 10;    }    while (x > 0)    {        //获取左边数字        var left = x / div;        //获取右边数字        var right = x % 10;        //比较左右数字是否相等        if (left != right)        {            //不相等则直接返回            return false;        }        //去掉左边数字        x = x % div;        //去掉右边数字        x = x / 10;        //因为去掉两个数字        //所以除数需除100        div /= 100;    }    //为回文数字    return true;}04、反转全部数字法

双指针法可能逻辑上比较复杂些，那么我们是否可以像字符串一样把整个整数反转过来呢？
其实反转整个数字其实也很简单，可以借鉴上一个方法中，取整取余的方式，把整个整数反转过来，然后直接比较反转后的整数和原整数是否相等即可。
其中需要注意的是一个32位整数反转后可能会导致溢出，因此反转结果我们需要使用64位整数存储。具体实现代码如下：
//反转全部数字public static bool IsPalindrome4(int x){    //负数肯定不是回文数    if (x < 0)    {        return false;    }    //把入参赋值给临时变量    int temp = x;    //反转结果    long reversed = 0;    //从后往前循环处理整数中的每一个数字    while (x != 0)    {        //获取x的个位数字        int digit = temp % 10;        //移除x的个位数字        temp = temp / 10;        //把x的个位数字拼接到反转结果的个位上        reversed = reversed * 10 + digit;    }    //直接比较入参和反转后的整数是否相等    return x == reversed;}05、反转一半数字

其实并不需要反转完所有数字我们才能知道是否是回文数，只需要反转完一半我们即可以知道是否为回文数。
比如输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。
此方法关键点是判断何时结束，以及是回文数的条件是啥。
对于反转一半数字，我们必须考虑到整数的长度是奇数还是偶数，如下图：

由此可以得出当x > revertedNumber时可以结束比较，而满足回文数的条件分奇偶两种情况x == revertedNumber 或 x == revertedNumber / 10。
具体代码实现如下：
//反转一半数字public static bool IsPalindrome5(int x){    //特殊情况：    //当 x < 0 时，x 不是回文数。    //同样地，如果数字的最后一位是 0，为了使该数字为回文，    //则其第一位数字也应该是 0，只有 0 满足这一属性    if (x < 0 || (x % 10 == 0 && x != 0))    {        return false;    }    var revertedNumber = 0;    while (x > revertedNumber)    {        //获取x的个位数字        var digit = x % 10;        //把x的个位数字拼接到反转结果的个位上        revertedNumber = revertedNumber * 10 + digit;        //移除x的个位数字        x /= 10;    }    //当数字长度为奇数时，例如，当输入为 12321 时，    //在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，    //因此可得 x == revertedNumber/10    //而当数字长度为偶数时，则 x == revertedNumber。    return x == revertedNumber || x == revertedNumber / 10;}注：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner