相等的有理数

标签: 数学 字符串

难度: Hard

给定两个字符串 s 和 t ，每个字符串代表一个非负有理数，只有当它们表示相同的数字时才返回 true 。字符串中可以使用括号来表示有理数的重复部分。

有理数 最多可以用三个部分来表示：整数部分 <IntegerPart>、小数非重复部分 <NonRepeatingPart> 和小数重复部分 <(><RepeatingPart><)>。数字可以用以下三种方法之一来表示：

  • <IntegerPart> 
    • 例： 0 ,12 和 123 
  • <IntegerPart><.><NonRepeatingPart>
    • 例： 0.5 , 1. , 2.12 和 123.0001
  • <IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> 
    • 例： 0.1(6) ， 1.(9)， 123.00(1212)

十进制展开的重复部分通常在一对圆括号内表示。例如：

  • 1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)

示例 1：

输入：s = "0.(52)", t = "0.5(25)"
输出：true
解释：因为 "0.(52)" 代表 0.52525252...，而 "0.5(25)" 代表 0.52525252525.....，则这两个字符串表示相同的数字。

示例 2：

输入：s = "0.1666(6)", t = "0.166(66)"
输出：true

示例 3：

输入：s = "0.9(9)", t = "1."
输出：true
解释："0.9(9)" 代表 0.999999999... 永远重复，等于 1 。[有关说明，请参阅此链接]
"1." 表示数字 1，其格式正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = "" 。

提示：

  • 每个部分仅由数字组成。
  • 整数部分 <IntegerPart> 不会以零开头。（零本身除外）
  • 1 <= <IntegerPart>.length <= 4
  • 0 <= <NonRepeatingPart>.length <= 4
  • 1 <= <RepeatingPart>.length <= 4
​​​​​

Submission

运行时间: 30 ms

内存: 16.1 MB

from fractions import *
class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        def f(num: str):
            ret = Fraction()
            if '.' in num:
                a = num.find('.')
                i = num[:a]
                if '(' in num:
                    b = num.find('(')
                else:
                    b = len(num)
                n = num[a + 1:b]
                r = num[b + 1:-1]
            else:
                i, n, r = num, '', ''
            ret += int(i)
            if n:
                ret += Fraction(int(n), 10**len(n))
            if r:
                ret += Fraction(int(r), (10**len(r) - 1) * 10**len(n))
            return ret
        return f(s) == f(t)

Explain

题解的思路是将给定的有理数字符串转换为精确的数学表示形式，使用 Python 的分数模块。这种转换处理了整数部分、非重复小数部分和重复小数部分。首先，根据小数点划分整数和小数部分。如果存在括号，则进一步将非重复和重复小数部分区分开来。对于非重复小数部分，直接将其转换为相应的分数。对于重复小数部分，根据无限循环小数的数学性质转换为分数。最后，比较两个数的分数表示是否相等。

时间复杂度: O(log(max(a, b)))

空间复杂度: O(1)

from fractions import *
class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        def f(num: str):
            ret = Fraction() # 初始化分数为0
            if '.' in num: # 如果字符串中有小数点
                a = num.find('.') # 找到小数点的位置
                i = num[:a] # 截取整数部分
                if '(' in num: # 如果有循环部分
                    b = num.find('(') # 找到循环开始的位置
                else: # 如果没有循环部分
                    b = len(num) # 小数部分直到字符串结束
                n = num[a + 1:b] # 截取非重复小数部分
                r = num[b + 1:-1] # 截取重复小数部分，去掉括号
            else: # 如果没有小数点
                i, n, r = num, '', '' # 只有整数部分
            ret += int(i) # 将整数部分加到结果中
            if n: # 如果有非重复小数部分
                ret += Fraction(int(n), 10**len(n)) # 将非重复部分转换为分数并加到结果中
            if r: # 如果有重复小数部分
                ret += Fraction(int(r), (10**len(r) - 1) * 10**len(n)) # 将重复部分转换为分数并加到结果中
            return ret # 返回计算的分数表示
        return f(s) == f(t) # 比较两个数的分数表示是否相等

Explore

为确保有理数字符串的准确转换，尤其是在处理较长的小数部分和重复小数部分时，首先需要确保输入字符串的格式正确无误。Python的`int`和`Fraction`类在处理大数字时具有很好的性能，因为Python的整数和分数操作是任意精度的。此外，`Fraction`类会自动化简分数，从而减少计算复杂度和提高精度。在实际应用中，还应考虑增加错误处理机制来应对格式错误或异常数据输入的情况，如进行输入验证和格式化检查。

题解中的方法没有直接包含错误处理逻辑来应对格式错误如缺失括号或包含多余字符的情况。因此，为提高代码的健壮性，应该在处理之前添加输入验证。这包括检查字符串是否包含非法字符、是否有匹配的括号以及小数点的位置是否合理。如果发现任何格式错误，应该抛出异常或返回错误消息，避免进行错误的数学计算。

这个分数公式的使用是基于无限循环小数转换为分数的数学原理。考虑一个有理数的重复小数部分`r`和非重复小数部分`n`。假设`r`是重复序列，例如对于0.00123(456)，`r`是456。将这个无限重复序列表示为分数时，我们可以将其视为几何级数的求和。级数的每一项都是重复序列的一个副本，后一项比前一项小10的`r`的长度次方。因此，这个级数可以表示为`r / (10^len(r) - 1)`，乘以`10^len(n)`是为了将小数点移动到正确的位置。所以，完整的分数表示是`Fraction(int(r), (10**len(r) - 1) * 10**len(n))`，它精确地表示了无限循环小数部分的值。