leetcode - [9] Palindrome Number

2020/04/22

题目描述

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: 100
Output: false
Explanation: Reads 001 from right to left. Therefore it is not a palindrome.

Update at 2020_0626

过了两个月,再来做这道题,一开始我的想法是这样的:

首先,负数肯定不是回文,直接返回false

然后,将x完全反转,最后与原数进行比较。

这就有一个问题,因为x在遍历过程中发生了变化,所以你需要一个额外的变量存储x最初的值。

class Solution {
    public boolean isPalindrome(int x) {
        
        if (x < 0) return false;
        int t = x;
        
        int ans = 0;
        while (x > 0){
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        
        return ans == t;
    }
}

我们来梳理下之前学过的一种解法:

可以将其称之为左右对比法

来看两张示意图:

可以看到,分为两种情况。

第一种,x的位数为奇数,那么等到遍历结束后,需要比较right / 10 是否等于x

第二种,x的位数为偶数,最后只需要比较right是否等于x即可。

另外,还有一种特殊的情况,如果x10的倍数。

也会满足right / 10 == x

所以需要额外排除掉。

再来看下完整实现:

class Solution {
    public boolean isPalindrome(int x) {
        
        if (x == 0) return true;
        if (x < 0 || x % 10 == 0) return false;
        int right = 0;
        
        while (x > right){
            right = right * 10 + x % 10;
            x /= 10;
        }
        
        return x == right || x == right / 10;
    }
}

解法1

Thanks @cbmbbz

public boolean isPalindrome(int x) {
    if (x == 0) return true;
    // Be careful x = 100
    if (x < 0 || x % 10 == 0) return false;
    int right = 0;
    while (x > right){
        right = right * 10 + x % 10;
        x /= 10;
    }
    // Be careful x = 22 or x = 121
    return (x == right) || (right / 10 == x);
}

首先,0符合回文的标准。

然后,有两类整数肯定不属于回文:

负数和能被10整除的数。

接着,计算该整数从右到左的部分,这里又分为两种情况:

第一种:位数为偶数的整数,如22。 最终结果为: x = 2, right = 2

第二种:位数为奇数的整数,如121。 最终结果为: x = 1, right = 12right / 10 = 12 / 10 = 1

Enjoy it!


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory