Leetcode-009-回文数反转

Leecode-009- 回文数

题目描述

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

示例 1:

输入: 121
输出: true


示例 2:

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


示例 3:

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

方法一：字符串双指针

思路：由于特点很合适，所以转换成字符串去判断

class Solution {
    public boolean isPalindrome(int x) {
        // int转换成string
        String s = String.valueOf(x);

        // 双指针判断
        int left = 0;
        int right = s.length() - 1;

        while (left < right){
            // 判断首尾是否相等
            if (s.charAt(left) == s.charAt(right)){
                // 相等的话判断下一位
                left++;
                right--;
            }else {
                // 不相等直接退出
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度： O(n)
• 空间复杂度：O(n) 使用了一个字符串数组实现

方法二: 十进制反转

思路: 把数字进行十进制倒转,再判断和原先是否相同

class Solution2 {
    public boolean isPalindrome(int x) {
        if (x < 0){
            return false;
        }

        int ans = 0;
        // 保存反转前的结果
        int temp = x;

        // 对每一位进行反转
        while (x > 0){
            ans = ans * 10 + x % 10;
            x /= 10;
        }

        return ans == temp;
    }
}

• 时间复杂度：O(1) 因为数字长度有限,int最大是32位,所以遍历32位就行.
• 空间复杂度：O(1) 使用常数的额外空间

注意:这里有一个隐藏的问题细节

• 如果我们输入的是最大32位整数2147483647，这个数字本身是没有问题，是一个合法的32位最大整数，用int存储也没问题，但是如果将这个数字反转的话，其大小超过了32位最大整数，也就是会溢出

  

• 那么是否要改变类型位Long类型存储呢?

  • 其实是不用的,因为32位整数中最大的回文数字是2147447421,这个数字是比最大32位整数要小的
  • 也就是说超过2147447412大小的数字也就不是回文数字了，虽然最后结果溢出了,但是返回的结果仍然是对的.

方法三: 反转一半的数字

思路:我们不用反转整数的所有数字，只需要反转一半数字就可以了，这是利用了【回文】的对称性。。

• 反转操作和方法二相同

while (x > 0){
    ans = ans * 10 + x % 10;
    x /= 10;
}

• 不同的地方在于 while 的判断条件
  • 我们可以注意到的是(如果反转后的数字 大于 反转后得到的数字,那么说明已经过半了)
  • 上面的那个很好理解,你随便写一个数字看看就知道了

• 最后要判断奇偶数的情况
  • 如果是偶数的话, 两者应该相等
  • 如果是奇数的话,新得到的数字正好是原数字x的10倍.

x==ans || x==(ans/10)

• 还有要考虑的一点:

  • 对于10，20，100这样的数字，用上面的判断方式就有问题了

  

  • 所以我们要对这些数字进行特殊处理(如果某个数字 % 10 等于 0 , 并且它不是0开头,那么直接返回false就可以了.)

class Solution {
    public boolean isPalindrome(int x) {
        // 这些数字特殊处理一下，
        // 如果某个数字%10等于0，并且它不是0开头，那么直接返回false就可以了
        if (x < 0 || (x%10==0 && x!=0)){
            return false;
        }

        int ans = 0;
        // 如果原数字大于新数字，不断求解得到新数字
        while (x > ans){
            ans = ans*10 + x%10;
            x /= 10;
        }

        // 判断奇数偶数的情况
        return x == ans || x==(ans/10);
    }
}

打赏