#51 - Coding 面試 - LeetCode #9 Palindrome Number

原文網址 https://leetcode.com/problems/palindrome-number/

這一題跟之前講的有一題 palindrome string 有點異巧同工之妙,但不同的是這題指的是數字,而不是字串.如果你把數字當成字母來看待的話,則也能用之前相同的解法.這在演算法來說算是一種 reduction 的技巧.然後,數字和字串的特性畢竟不同,所以若把數字轉成字串來處理是可以的,但就浪費了一些數字的特質.

其實要把數字反轉,最簡單的方法就是用十來取餘數,也就是說 2 取十的餘數是 2 , 12 取十的餘數是 2 , 102 數十的餘數是 2.因此,對十取餘數之後,我們就能得到個位數的值,然後再對商再取一次餘數,用這個方法一直做到商變成 0,這樣子就可以把原來的數字一個一個取了出來.

剩下的就是將取出來的數字排好,第一個取出來的放最前面,最後取出來的放最後面,這裡不需要 "儲存" 的觀念來做,其實只要在每取出一次餘數時,把之前取出來的數字乘十就行了,這樣就等於先取出來的會被 "進位",然後再加上最新取出來的餘數.

最後,還要記得處理正負號.這只需要在一開始的時候判斷是正號或負號,若是負號的話,就一律不符合答案,若是正號的話,就檢查反轉前和反轉後的數字是不是一樣的,這樣就完成了.

參考的程式碼如下:



Share:

0 意見:

張貼留言