Python3实现回文数判断与罗马数字转整数算法详解

本文通过Python3代码实例，详细讲解如何判断一个整数是否为回文数，以及如何将罗马数字转换为整数的算法实现。内容包含多种解题思路及代码示例，供读者参考学习。

回文数判定算法

回文数判定

核心任务是判断给定的整数是否为回文数。所谓回文数，即该整数从左向右读取的顺序与从右向左读取的顺序完全一致。

示例 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 左侧时，表示大数减小数的结果 4。同理，数字 9 表示为 IX。该特殊规则仅适用于以下六种情况：

• 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程序设计有所帮助。