LeetCode 9. Palindrome Number (Java版; Easy)

以你之姓@ 2023-07-03 02:59 2阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 9. Palindrome Number (Java版; Easy) ##

#### 题目描述 ####

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
    
    Example 1:
    
    Input: 121
    Output: true
    Example 2:
    
    Input: -121
    Output: false
    Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
    Example 3:
    
    Input: 10
    Output: false
    Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
    Follow up:
    
    Coud you solve it without converting the integer to a string?

#### 第一次做; 最优解, 借鉴题解的思路, 核心:1)获取数字后半部分的反转; 结尾为0的数字中, 除了0之外都不是回文数字, 可以提前拿出来判断; 2) 理解 x==half与x==half\\10分别对应数字长度是偶数和奇数这两种情况 ####

class Solution { 
        public boolean isPalindrome(int x) { 
            if(x<0 || (x!=0 && x%10==0))
                return false;
            //获取x的后一半的反转, 比如12345,half就是543; 比如1234, half就是43
            int half = 0;
            //核心1:
            while(x>half){ 
                half = half*10 + x%10;
                x = x/10;
            }
            //核心2:
            //x==half对应这种情况, 1221, x=12, half=12
            //x==half/10对应这种情况, 12321, x=12, half=123
            return x==half || x==half/10;
        }
    }

#### 第一次做, 将数字转成字符串, 使用双指针, 分别从首尾相向移动; 时间复杂度O(N), 空间复杂度O(N) ####

class Solution { 
        public boolean isPalindrome(int x) { 
            if(x<0)
                return false;
            String s = String.valueOf(x);
            int left = 0, right = s.length()-1;
            while(left<right){ 
                if(s.charAt(left) != s.charAt(right))
                    return false;
                left++;
                right--;
            }
            return true;
        }
    }

#### [力扣官方题解][Link 1] 提取一个数字的一半, 加快了处理速度; 本题不需要考虑反转后溢出的问题, 因为不会出现溢出. 只要是int范围内的数, 反转后都不会溢出 ####

public class Solution { 
        public bool IsPalindrome(int x) { 
            // 特殊情况：
            // 如上所述，当 x < 0 时，x 不是回文数。
            // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
            // 则其第一位数字也应该是 0
            // 只有 0 满足这一属性
            if(x < 0 || (x % 10 == 0 && x != 0)) { 
                return false;
            }
    
            int revertedNumber = 0;
            while(x > revertedNumber) { 
                revertedNumber = revertedNumber * 10 + x % 10;
                x /= 10;
            }
    
            // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
            // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
            // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
            return x == revertedNumber || x == revertedNumber/10;
        }
    }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/palindrome-number/solution/hui-wen-shu-by-leetcode/