[LeetCode] 9. Palindrome Number
Problem: Determine whether an integer is a palindrome. Do this without extra space.
一開始我看到題目有一點傻眼,這算是簡單的題目嗎?不能使用額外的儲存空間?直到後來回歸到「回文」的本質,一切才豁然開朗,所謂的回文不就是從前面看過去和從後面看過來都一樣嗎⋯⋯
其實解決這個問題還是需要儲存一些輔助的變數,這是無可避免的,例如,前述的程式碼中就有用到儲存字串陣列與其 index 的空間。而將數字轉成字串是為了方便指定一前一後位置的數值。這樣的做法會將負數判斷為不是回文,畢竟沒有一個數字會是前後都是負號的。

如圖一(a)所示,首先從前面 index 為 0 和後面 index 為 5–0–1 = 4 的數值比對,兩相對照之下: 1 == 1,比對結果一致,若不一致則可以直接回傳 false。接著比對的數值由前面一位往後移動 1 位,並且,由後面一位往前移動 1 位,如圖一(b)所示,兩相對照之下: 2 == 2,比對結果一致,若不一致則可以直接回傳 false。最後,比對的數值由前往後和由後往前皆移至 index 為 2 的數值,同一個數值當然會是一致的,因此,12321 是一個回文的數字。
原先我是判斷前後的 index 指到同一位數時就回傳比對結果,但是,當輸入的數字長度為偶數位時,將會發生 IndexOutOfBoundsException 的問題。如圖二(a)所示,當 index 移至 2 與 6–2–1 = 3,因為 2 != 3,此時程式會繼續執行下去,如圖二(b)所示, index 交錯而過,最終導致 index 位移至超出字串陣列的範圍。

於是我將移動 index 的判斷改為,移動不可超過陣列長度的一半,
while (i < (number.length() +1) / 2) { ... }另外一種方法是藉由之前的題目 Reverse Integer 的做法,將數字反轉之後再比對反轉前與反轉後的數字是否一致,此方法依然需要額外的變數儲存原始的數字和反轉後的數字,程式碼如下。
讓我覺得意外巧妙的是如此簡單的幾行程式,便能將負數判斷為不是回文,因為負數不會等於 reverseX 的預設值 0,但輸入 0 卻能正確回傳 true。
值得注意的是,我移除掉處理溢位相關的程式碼,因為我發現一個沒有溢位的回文數字,反轉之後也絕對不會發生溢位!若輸入的不是回文數字,再反轉後發生溢位,那就發生吧,這不會影響結果。

