LeetCode——回文数

比眉伴天荒 2022-12-18 08:58 138阅读 0赞

# **题目** #

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

**示例 1:**

输入: 121

输出: true

**示例 2:**

输入: -121

输出: false

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

**示例 3:**

输入: 10

输出: false

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

**进阶:**

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

# **题解** #

## **解题思路一** ##

看到这个题目第一个想法就是将数字转换为字符串，然后挨个检查字符串的每个字符判断字符串是否为回文数。但是该方法需要额外的非常量空间来存储转换而来的字符串。

### **代码实现** ###

public class IsPalindrome {
        public boolean isPalindrome(int x) {
            String val = String.valueOf(x);
            int i=0, j=val.length()-1;
            while (i<j){
                if (val.charAt(i)!=val.charAt(j)) {
                    return false;
                }
                ++i;
                --j;
            }
            return true;
        }
    }

### **复杂度分析** ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## **解题思路二** ##

如果不将数字转换为字符串，第二个想法就是反转数字本身，然后将反转后的数字与原始数字进行比较，如果相同，则为回文数，否则不是。

但是，反转数字时需要考虑溢出问题，如果反转后的数字超过了int.MAX，则会导致整数溢出问题。此时如果我们之反转数字的一半呢（后半部分）？如果该数字是回文数，则后半部分反转后应该与前半部分是一致的。比如 123321，后半部分进行反转后是123，前半部分也是123，因此得知123321是回文数。因此接下来的问题是如果反转数字呢？

首先，考虑一些特殊情况，所有负数不可能为回文数，例如-121不是回文，因为-不等于最后一位1，因此可以对所有负数返回false。

其次，除了0以外，所有个位数是0的数字不可能是回文，因为最高位不可能是0。所以对所有大于0且各位是0的数字返回false。

最后，对一般情况下的数据后半部分进行反转。例如，对于1221，执行1221%10=1得到最后一位数字1，执行1221/10=122，122%10=2得到倒数第二位数字2。同时如果我们将最后一位数字1\*10=10，再加上倒数第二位数字，10+2=12，就得到了我们想要的反转后的后半部分数字。同理可以得到更多位数的反转数字。

何时才算反转一半了呢？由于整个过程我们是不断的将原始数字除以10，然后将反转后的数字乘以10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经反转了一半的数字了。

### **代码实现** ###

public class IsPalindrome {
        public boolean isPalindrome(int x) {
            // 处理特殊情况
            // 当x<0是不满足
            // 如果数字的最后一位是0，为了满足回文数，则数字的第一位也应该是0，只有0满足
            if (x<0 || (x%10==0 && x!=0)) {
                return false;
            }
            int reverteNumber = 0;
            // 当原始数字小于翻转后的数字时，表示已经翻转了一半
            while (x > reverteNumber) {
                reverteNumber = reverteNumber * 10 + x % 10;
                x = x / 10;
            }
            return x == reverteNumber || x == reverteNumber / 10;
        }
    }

### **复杂度分析** ###

*  时间复杂度：O(logn)，对于每次迭代，都将原始数据除以10
 *  空间复杂度：O(1)