每日一道 LeetCode (3):迴文數
前文合集
題目:迴文數
題目來源: https://leetcode-cn.com/problems/palindrome-number/
判斷一個整數是否是迴文數。迴文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。
示例 1:
輸入: 121 輸出: true
示例 2:
輸入: -121 輸出: false 解釋: 從左向右讀, 爲 -121 。 從右向左讀, 爲 121- 。因此它不是一個迴文數。
示例 3:
輸入: 10 輸出: false 解釋: 從右向左讀, 爲 01 。因此它不是一個迴文數。
進階:
你能不將整數轉爲字符串來解決這個問題嗎?
解題思路
在題目給出的示例中可以直觀的看到,負數由於負號的關係,肯定不是迴文數的,那麼我們第一件事情就是判斷輸入的數字不是負數。
然後根據數字的特性,還可以知道個位數字是 0
的整數,肯定也不會是迴文數,個位是 0
的數字如果是迴文數的話,那麼首位一定也要是 0
,這種數字除了 0
以外其餘的顯然都不會是一個迴文數。
這樣,我們的第一個極限值判斷就有了,所有的負數返回 false
,所有個位是 0
且不爲 0
的整數也要返回 false
。
接下來,不知道你們會不會想到上一篇文章中的整數反轉,將整個輸入的數字反轉後,得到的結果如果和輸入數字一樣,那麼這個肯定是迴文數,不過這麼搞的話,我們還需要判斷反轉後的數字是否溢出,有點麻煩。
那麼比較好的方案是啥,當然是直接反轉後面一半的數字,與前面一半的數字做比較,如果一樣的話,返回 true
,不一樣的返回 false
。
數字反轉的操作很簡單,輸入的數字 x 直接循環的取模就好,然後我們再對輸入的數字在循環的過程中除以 10 。
問題是我們如何判斷反轉的位數已經達到了一半?
這個問題可以這麼考慮,如果是偶數迴文數的情況,X 和 Y 相等的時候,反轉的位數就已經到一半了,如果是奇數迴文數的情況,那麼 X < Y 的時候,反轉的位數也到一半了,然後我們對去除 Y 的最後一位,和 X 進行比較,如果相等,那麼這個數字就是奇數位的迴文數。
寫代碼
經過上面的分析,代碼已經簡單到顯而易見了:
public boolean isPalindrome(int x) { // 先做極限情況判斷 if (x < 0 || (x % 10 == 0 && x != 0)) return false; int revertedNumber = 0; // 一直循環到 revertedNumber 大於或者等於 x while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } return revertedNumber == x || x == revertedNumber / 10; }
到這裏,不知道有沒有同學會想問,題目上如果沒有加那句「不將整數轉爲字符串」題幹,可以怎麼解答。
在 Java 中,如果沒有這個限制,那這個代碼不要簡單太多, Java 中的 StringBuilder 和 StringBuffer 都直接提供了 reverse()
方法:
public boolean isPalindrome_1(int x) { // 先做極限情況判斷 if (x < 0 || (x % 10 == 0 && x != 0)) return false; StringBuilder stringBuilder = new StringBuilder(String.valueOf(x)); return stringBuilder.toString().equals(stringBuilder.reverse().toString()); }
小結一下吧:如果以後遇到「整數反轉」的問題,基本思路就是循環取模,然後再乘以 10 加起來,需要注意的就是 int 類型有長度限制,注意超限和極限值判斷。今天的迴文數可以看做一種稍微特殊的「整數反轉」問題。