[LeetCode] 9. Palindrome Number

亞爾
亞爾
Jul 30, 2017 · 3 min read

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

值得注意的是,我移除掉處理溢位相關的程式碼,因為我發現一個沒有溢位的回文數字,反轉之後也絕對不會發生溢位!若輸入的不是回文數字,再反轉後發生溢位,那就發生吧,這不會影響結果。

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade