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

回文數(shù)

判斷一個(gè)整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

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

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

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

進(jìn)階:你能不將整數(shù)轉(zhuǎn)為字符串來(lái)解決這個(gè)問題嗎？

方法一：將整數(shù)轉(zhuǎn)換為字符串，反轉(zhuǎn)字符串，再與原字符串進(jìn)行比較

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

方法二：將整數(shù)反轉(zhuǎn)

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

注意：雖然題目中沒要求，還是應(yīng)該考慮一下是否會(huì)溢出的問題，參考之前整數(shù)反轉(zhuǎn)的問題。

方法二的改進(jìn)：將整數(shù)的后一半反轉(zhuǎn)，前一半與后一半進(jìn)行比較，這樣就不用考慮是否會(huì)溢出。反轉(zhuǎn)的方法與方法二對(duì)整數(shù)反轉(zhuǎn)是一樣的，問題是如何知道反轉(zhuǎn)數(shù)字的位數(shù)已經(jīng)達(dá)到原數(shù)數(shù)字的一半？方法是：

當(dāng)剩下的數(shù)字小于或等于反轉(zhuǎn)的數(shù)字時(shí)，就意味著已經(jīng)處理了一半位數(shù)的數(shù)字。

比如，1221，經(jīng)反轉(zhuǎn)得x=12，rnum=12，二者相等；12321，經(jīng)反轉(zhuǎn)后x=12,rnum=123，反轉(zhuǎn)的數(shù)字比剩下的數(shù)字多一位，此時(shí)說(shuō)明已經(jīng)反轉(zhuǎn)了一半加一的位數(shù)，比較的時(shí)候去掉多余的那一位即可。

class Solution:
  def isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    #如果是負(fù)數(shù)或 被10整除的非零數(shù)，肯定不是回文數(shù)
    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

羅馬數(shù)字轉(zhuǎn)整數(shù)

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

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

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

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

給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1 到 3999 的范圍內(nèi)。

示例 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.

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

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

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

最新評(píng)論