LeetCode每日一练（回文数）

叁歲伎倆 2022-09-03 00:25 146阅读 0赞

题目如下：

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

![在这里插入图片描述][c18c785a8c724482b5c5d948bb2badd2.png]

判断一个数是否为回文数，首先想到的办法就是将其转为字符串，再通过反转字符串来判断是否相同，比如：  
![在这里插入图片描述][39797719e0754c308bad6ec624ea334c.png]

反转后字符串不相同，则不是回文数。  
![在这里插入图片描述][344b3fcf784e4b6b9922a4e5a5eff7b2.png]

反转后数字相同，则是回文数。由此得代码如下：

public class Solution { 
    
        public static void main(String[] args) { 
            System.out.println(isPalindrome(121));
        }
    
        public static boolean isPalindrome(int x) { 
            // 将数字转为字符串
            String str = String.valueOf(x);
            // 将其反转
            String newStr = new StringBuilder(str).reverse().toString();
            return str.equals(newStr);
        }
    }

提交到LeetCode：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]

题目的最后还提出了一个进阶要求：

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

不借助字符串该如何实现呢？其实也非常简单，通过计算直接反转数字即可，以1234举例，首先我们需要获得该数字的个位数4，如何获取呢？求余10即可：  
![在这里插入图片描述][0f50fa73dc0247e38ebf8ee2773e9b03.png]

接下来获取十位数3，先让1234除以10，这样就得到数字123，再让123求余10即可得到3：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]

以此类推，就能够得到数字中的每一位：  
![在这里插入图片描述][5bfb0ccd359e48c281549b260ebcba57.png]

再让每一位分别乘以对应的进位即可，那既然是要反转，我们就要反着来，将4看成千位，3看成百位，2看成十位，1看成个位：  
![在这里插入图片描述][07814c18b65f41288eae2220b8cbe76d.png]

由此得到反转后的数字：`4 * 1000 + 3 * 100 + 2 * 10 + 1 = 4321`。

代码如下：

public class Solution { 
    
        public static void main(String[] args) { 
            System.out.println(isPalindrome(121));
        }
    
        public static boolean isPalindrome(int x) { 
            int num = x;
            int result = 0;
            // 将数字反转
            while (x > 0) { 
                result *= 10;
                result += x % 10;   // 求得每一位
                x /= 10;            
            }
            return num == result;
        }
    }

但这个程序还有一个小漏洞，就是越界问题，当某个数字反转后大于了int的最大值，那么程序就会出错：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 2]

此时result因为超过了int能表示的最大值，已经变成了一个负值，它永远不可能与输入的值相等，所以程序就无法准确判断输入的值是否为回文数了。

为了解决这一问题，我们可以不反转所有的数字，而是反转其中的一半，因为回文数的性质，使得我们只需要知道其中的一半相同，那么它就一定是回文数。

我们需要分两种情况讨论一下，首先是奇数长度的数字，以12321举例：  
![在这里插入图片描述][4f88c9f07917447c8f64107c70b134bc.png]

我们得到反转后一半长度的数字：  
![在这里插入图片描述][e8891d110a2f45c8a8548cf577d98805.png]

将它与反转前一半长度的数字比较，发现均为12，表明12321就是一个回文数。

若是偶数长度的数字，以1221举例：  
![在这里插入图片描述][276d3c69a7e34f228d96fa82b18820c2.png]

仍然得到反转后一半长度的数字：  
![在这里插入图片描述][00f920c498554b3181655288959b2d33.png]

将其与反转前一半长度的数字比较即可。

那么关键在于如何进行数字的切割和获取呢？我们将奇数长度和偶数长度的数字放在一起讨论一下：  
![在这里插入图片描述][7cfcfc3cc4fc435595687878731ae82b.png]

首先让其求余10即可得到最后一位数：  
![在这里插入图片描述][d474a0296d574fd789476f05ad08c6e4.png]

接着让原来的数除以10即可舍去最后一位：  
![在这里插入图片描述][49cdb9f22323440fa48259e7e72302f7.png]

再求余10得到最后一位：  
![在这里插入图片描述][b03da79296d64881b064f248d50c080c.png]

再让原来的数除以10舍去最后一位：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]

到这里就应该停止操作了，因为偶数长度情况的数已经获取到了一半长度的数字，对于偶数情况，直接比较新生成的数字是否与原数字相等即可；而对于奇数长度情况，虽然获取到了一半长度的数字，但原数字中的长度为3，所以我们应该再获取一次：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]

由此可得，循环的终止条件为当原来的数小于或者等于新生成的数，而对于奇数情况，我们需要去除最后一位数再与原数字比较，所以让新生成的数字除以10再比较。

综上所述，得到代码：

public class Solution { 
    
        public static void main(String[] args) { 
            System.out.println(isPalindrome(12321));
        }
    
        public static boolean isPalindrome(int x) { 
            // 负数一定不是回文数
            if (x < 0 || (x % 10 == 0 && x != 0)) { 
                // 若是数字的最后一位是0，则如果是回文数，那该数的第一位一定为0，满足情况的数字只有0
                // 所以若是最后一位为0，但该数又不是0，则直接返回false
                return false;
            }
            int newNum = 0;
            // 当原数字小于或等于新生成的数字时停止循环
            while (x > newNum) { 
                newNum *= 10;
                newNum += x % 10;
                x /= 10;
            }
            // 比较新生成的数字是否与原数字相等
            return x == newNum || x == newNum / 10;
        }
    }

提交到LeetCode：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 5]

[c18c785a8c724482b5c5d948bb2badd2.png]: /images/20220829/525c1ea3aa3f40e2be582844df5623f5.png
[39797719e0754c308bad6ec624ea334c.png]: /images/20220829/b3eda27508704f88ac15b81e2163b730.png
[344b3fcf784e4b6b9922a4e5a5eff7b2.png]: /images/20220829/a30f1c4febad4395a68531181e74eb18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]: /images/20220829/c43ea82f90074b938437417ac7cd600a.png
[0f50fa73dc0247e38ebf8ee2773e9b03.png]: /images/20220829/45e3c7424e4d42ea9bf1eaa5300e7082.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]: /images/20220829/92904055ac2742b7bd01026eba8428a9.png
[5bfb0ccd359e48c281549b260ebcba57.png]: /images/20220829/d335d086bf8248bfb5ff0e3617009f6e.png
[07814c18b65f41288eae2220b8cbe76d.png]: /images/20220829/afa59e1eaa9d455588af6b2d8180fab1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 2]: /images/20220829/92cf0458505e4149ad1af34dcd601260.png
[4f88c9f07917447c8f64107c70b134bc.png]: /images/20220829/6233ab11dc3e4cc4b45d7aff0bfe3347.png
[e8891d110a2f45c8a8548cf577d98805.png]: /images/20220829/f2e1e02ee4ed4df2b867132c369911e7.png
[276d3c69a7e34f228d96fa82b18820c2.png]: /images/20220829/c85ac27beff24360bb0c209676b4665d.png
[00f920c498554b3181655288959b2d33.png]: /images/20220829/6be307fa8a884eae90182b29ac934648.png
[7cfcfc3cc4fc435595687878731ae82b.png]: /images/20220829/3ef9a99e457e40d8a6e9f656df6a543e.png
[d474a0296d574fd789476f05ad08c6e4.png]: /images/20220829/2fd7f700c64f4814940549efcd5b224c.png
[49cdb9f22323440fa48259e7e72302f7.png]: /images/20220829/0a5a26fc0b6e4ca2bfcb3a1cb9307119.png
[b03da79296d64881b064f248d50c080c.png]: /images/20220829/dac2e624923348079c1da50a5035e172.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]: /images/20220829/22993bf13c004776b4dc7cf0f9fa88c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]: /images/20220829/33fd5449312c4733980a813db40232b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 5]: /images/20220829/d2c638db507e49bda929c2a1dc251355.png