本文實例講述了Python3實現(xiàn)的回文數判斷及羅馬數字轉整數算法。分享給大家供大家參考，具體如下：

回文數

判斷一個整數是否是回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。

示例 1:
輸入: 121
輸出: true

示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是一個回文數。

示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個回文數。

進階:你能不將整數轉為字符串來解決這個問題嗎？

方法一：將整數轉換為字符串，反轉字符串，再與原字符串進行比較

class Solution:
  def isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    if x < 0:
      return False #如果x是負數，則肯定不是回文數。
    str_x_r = ''
    str_x = str(x)
    str_x_r += str_x[::-1] #反轉字符串，-1表示從右邊讀取
    if str_x_r == str_x:
      return True
    else:
      return False

方法二：將整數反轉

class Solution:
  def isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    if x < 0:
      return False
    tmp = x
    rev = 0
    while x != 0:
      pop = x % 10
      x //= 10
      rev = rev*10 + pop
    if tmp == rev:
      return True
    else:
      return False

注意：雖然題目中沒要求，還是應該考慮一下是否會溢出的問題，參考之前整數反轉的問題。

方法二的改進：將整數的后一半反轉，前一半與后一半進行比較，這樣就不用考慮是否會溢出。反轉的方法與方法二對整數反轉是一樣的，問題是如何知道反轉數字的位數已經達到原數數字的一半？方法是：

當剩下的數字小于或等于反轉的數字時，就意味著已經處理了一半位數的數字。

比如，1221，經反轉得x=12，rnum=12，二者相等；12321，經反轉后x=12,rnum=123，反轉的數字比剩下的數字多一位，此時說明已經反轉了一半加一的位數，比較的時候去掉多余的那一位即可。

class Solution:
  def isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    #如果是負數或 被10整除的非零數，肯定不是回文數
    if x<0 or (x%10 == 0 and x != 0):
      return False
    rnum = 0
    while x > rnum:
      rnum = rnum*10 + x%10
      x //= 10
    return x == rnum or x == rnum//10

羅馬數字轉整數

羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M。

例如， 羅馬數字 2 寫做 II ，即為兩個并列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。

通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等于大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規(guī)則只適用于以下六種情況：

• I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。

給定一個羅馬數字，將其轉換成整數。輸入確保在 1 到 3999 的范圍內。

示例 1:
輸入: “III”
輸出: 3

示例 2:
輸入: “IV”
輸出: 4

示例 3:
輸入: “IX”
輸出: 9

示例 4:
輸入: “LVIII”
輸出: 58
解釋: L = 50, V= 5, III = 3.

示例 5:
輸入: “MCMXCIV”
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

將七個字符放在字典中，可有效加快查詢速度，比使用if條件判斷語句快很多。

class Solution:
  def romanToInt(self, s):
    """
    :type s: str
    :rtype: int
    """
    #巧妙利用了字典
    roman_dict = {
      'I':1,
      'V':5,
      'X':10,
      'L':50,
      'C':100,
      'D':500,
      'M':1000,
      }
    result = 0
    for i in range(len(s)):
      if i < len(s)-1 and roman_dict[s[i]] < roman_dict[s[i+1]]:
        result -= roman_dict[s[i]]
      else:
        result += roman_dict[s[i]]
    return result

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數學運算技巧總結》、《Python數據結構與算法教程》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。

最新評論