題目地址:
回文數(shù)

1.題目描述

判斷一個整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

示例 1:

輸入: 121
輸出: true
示例 2:

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是一個回文數(shù)。
示例 3:

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個回文數(shù)。
進階:

你能不將整數(shù)轉(zhuǎn)為字符串來解決這個問題嗎？

2.題解

2.1.解題思路

看到那個正序和倒敘，入?yún)⑦€是整數(shù)，馬上想到可以將第七題改改拿過來直接用。
根據(jù)示例，負數(shù)不會是回文數(shù)，所以只有正數(shù)會是回文數(shù)（還有0）。

2.2.第一版代碼

直接將第七題的整數(shù)反轉(zhuǎn)的代碼拿來改一改，改完如下:

public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int reverse = reverse(x);
        if (reverse !=x) {
            return false;
        }

        return true;
    }

 //整數(shù)反轉(zhuǎn)的代碼
 public  int reverse(int x) {
        if (x / 10==0) {
            return x;
        }
        long result = 0;
        for (int i = 0; i < 10; i++) {
            result=result*10+x%10;
            if (result > Integer.MAX_VALUE) {
                return 0;
            }
            x = x / 10;
            if (x==0) {
                break;
            }
        }
        return new Long(result).intValue();
    }

第一版代碼的運行結(jié)果如下:

回文數(shù)第一版.png

內(nèi)存消耗還可以，但是耗時比單純的整數(shù)反轉(zhuǎn)多了很多。

2.2.第二版代碼

官方題解給的解題思路也是整數(shù)反轉(zhuǎn)，不過他們給的不是把整個數(shù)都反轉(zhuǎn)完，比較result和x是否相等，而是在反轉(zhuǎn)過半的時候進行判斷。
在對x做除法的過程中:

long result = 0;
result=result*10+x%10;
x = x / 10;

在這個過程中,result在不斷增大,x在不斷的減小,當result>=x時,代表來到了入?yún)的中間點。比如121，中間點是2，result=21,x=1的時候，代表遍歷過半，退出循環(huán)。

當x==result或x/10==result時，代表x是回文數(shù)。返回結(jié)果。循環(huán)結(jié)束條件是x<result，所以當x為長度為奇位數(shù)的時候，x==result/10也是符合條件的。

這樣會有一點小問題，尾數(shù)為0的，經(jīng)過while循環(huán)處理之后，反轉(zhuǎn)的數(shù)并不構(gòu)成回文數(shù)，需要排除這種情況。
下面是完整代碼:

public static boolean isPalindrome1(int x) {
        //小于0或者是10的倍數(shù)都不符合要求，0是回文數(shù)
        if (x < 0 || (x%10==0&&x!=0)) {
            return false;
        }
        long result = 0;

        //這里仍是整數(shù)反轉(zhuǎn)的循環(huán)，更改了循環(huán)退出條件，去掉了越界判斷
        while (x>result) {
            result=result*10+x%10;
            x = x / 10;
        }
        //循環(huán)退出的時候x<=result
        //由于處于中位的數(shù)字總是與自身相等，所以可以簡單的去掉
        return x==result||x==result/10;
    }

第二版的運行結(jié)果如下:

回文數(shù)第二版.png

emm,執(zhí)行耗時低了一點，內(nèi)存耗時多了一點。

2.3.其他用戶提供的一個思路

還有一位用戶提供了一個思路，地址在這里：
https://leetcode-cn.com/problems/palindrome-number/solution/ji-bai-liao-99de-javayong-hu-dai-ma-you-ya-by-reed/
這位是同時首尾是否相同，如果相同，去掉首尾，再判斷下面的數(shù)字，感興趣的可以去看一下。

3.總結(jié)

這道題官方預感到會有人將數(shù)字轉(zhuǎn)換為字符串，判斷字符串是否為回文串，這樣做當然也能做，不過開銷會大很多，所以給了個提示，是否可以不將數(shù)字轉(zhuǎn)換為字符串進行求解。如果先做第七題的話，會首先想到使用整數(shù)反轉(zhuǎn)的思路來著，方便快捷。

這道題同時也需要考慮邊界的問題，先將不符合的數(shù)提前返回。