7/7 演算法題詳解：Palindromic Decimal Numbers 判斷迴文數

02-03

本視頻來自於北美CS刷題神器BitTiger Pro。

今天我們來討論一下迴文數。首先我們需要理解一下什麼是迴文，迴文是指一個從前往後讀和從後往前讀都一模一樣的字元串。比方說，「redivider」就是一個迴文，而「divider」就不是了，同理可知，7，121，2147447412等就可以說是迴文數。

我們今天的目的就是通過完成一個程序，實現輸入一個數字後判斷該數字是否可以被視為迴文數字。比方說輸入是100，就需要返回false，輸入1441，就需要返回true。那如果是負數呢？一般需要返回false，因為數字前面有一個負號，而尾部沒有。但在面試的時候如果你遇到了這個題目，請立即與你的面試官確認和討論這種情況，這是一個加分項。

解法一：

當你了解了迴文以後，你就可以很自然地想到一個方法，先把這個整數轉換為字元串，然後通過字元比較得到這個判斷結果，字元串判斷是否為迴文可以參見另外一篇文章【Test palindromicity判斷一個字元串是否為迴文】，假設傳入的數字的長度是n。那麼這個方法的時間複雜度是O(n)，因為你需要訪問所有的字元，空間複雜度是O(n)，因為整數需要先轉換成字元串。

解法二：

我們能提升一下這個演算法嗎？我們不能提升時間複雜度上的性能，因為我們需要比對所有的內容才能得出結論，那我們就從空間複雜度下手。考慮到我們在轉化成字元串後進行判斷的優勢就是我們可以隨意訪問任何位置的內容用以判斷最左邊的內容和最右邊的是否相同，其實我們對整數也可作相同的事情。

我們知道一個整數的最低位=A % 10（取余操作），最高位=A/10n-1整除操作。比如給出一個整數，151751，那麼最高位是151751/105=1，最低位是151751%10=1。現在我們可以設計出我們新的演算法了。我們比較它們的最高位和最低位，如果一致，就處理掉這兩位，然後繼續循環匹配，如果不一致，就直接返回false。比方說下圖就是步驟舉例。

這個方法的時間複雜度是O(n)，但空間複雜度降低到了O(1)。

下圖就是我們代碼實現：

第一步我們需要判斷是否小於0，是的話就需要返回false。第二步，計算數字是幾位的並初始化掩碼（mask）。第三步就是循環判斷最高位和最低位是否相等，如果不相等，返回false，否則繼續，注意數字最高位和最低位的去除方法以及掩碼的處理。

思考題

還有一種方法可以判斷，就是通過反轉整個數字，然後判斷兩個數字是否一致來實現。你可以自己動手試試看，然後分析一下時間複雜度和空間複雜度。

本視頻來自於北美CS刷題神器BitTiger Pro。

每月更新的BitTiger Pro是一個覆蓋了CS和數據科學方向最新高頻面試題的精講視頻庫。訂閱後，你可以在Code Evaluation System親自練習這道題。