TNotes.leetcode

Appearance

⏰0972. 相等的有理数【困难】

0972. 相等的有理数【困难】 ​

1. 📝 题目描述 ​

给定两个字符串 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：

txt
输入：s = "0.(52)", t = "0.5(25)"
输出：true

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

示例 2：

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

示例 3：

txt
输入：s = "0.9(9)", t = "1."
输出：true

解释：
"0.9(9)" 代表 0.999999999... 永远重复，等于 1。
  有关说明，请参阅此链接：
  https://baike.baidu.com/item/0.999%E2%80%A6/5615429?fr=aladdin
"1." 表示数字 1，其格式正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = ""。

提示：

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

2. 🎯 s.1 - 字符串解析 + 分数比较 ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isRationalEqual = function (s, t) {
  // 将有理数字符串转换为分数 [分子, 分母]
  const toFraction = (str) => {
    const parts = str.split('.')
    const intPart = parts[0] || '0'
    const decPart = parts[1] || ''

    // 查找循环部分
    const repeatStart = decPart.indexOf('(')
    let nonRepeat = ''
    let repeat = ''

    if (repeatStart !== -1) {
      nonRepeat = decPart.substring(0, repeatStart)
      repeat = decPart.substring(repeatStart + 1, decPart.length - 1)
    } else {
      nonRepeat = decPart
    }

    // 构建分子和分母
    // 对于 0.1(6): 整数部分 0, 非循环 1, 循环 6
    // 分子 = 016 - 01 = 16 - 1 = 15
    // 分母 = 990 (循环部分1位,非循环1位)
    let numerator = BigInt(intPart + nonRepeat + repeat || '0')
    let denominator = BigInt(1)

    if (repeat) {
      // 有循环部分
      const nonRepeatNum = BigInt(intPart + nonRepeat || '0')
      numerator = numerator - nonRepeatNum
      // 分母: 循环部分长度个9 + 非循环部分长度个0
      denominator = BigInt(
        '9'.repeat(repeat.length) + '0'.repeat(nonRepeat.length),
      )
    } else {
      // 无循环部分，纯小数
      numerator = BigInt(intPart + nonRepeat || '0')
      denominator = BigInt('1' + '0'.repeat(nonRepeat.length))
    }

    // 化简分数
    const g = gcd(numerator, denominator)
    return [numerator / g, denominator / g]
  }

  // 最大公约数
  const gcd = (a, b) => {
    a = a < 0n ? -a : a
    b = b < 0n ? -b : b
    while (b !== 0n) {
      const temp = b
      b = a % b
      a = temp
    }
    return a
  }

  const [n1, d1] = toFraction(s)
  const [n2, d2] = toFraction(t)

  // 比较两个分数是否相等: n1/d1 = n2/d2 => n1*d2 = n2*d1
  return n1 * d2 === n2 * d1
}

// Tdahuyou 提交于 2026.01.24 07:51
// 执行用时分布 0ms 击败 100.00%
// 消耗内存分布 54.34MB 击败 100.00%
  • 时间复杂度：O(1)，由于字符串长度受限且固定，所有操作都是常数时间
  • 空间复杂度：O(1)，只使用常数级别的额外空间

算法思路：

  • 字符串解析：将有理数字符串分解为整数部分、非循环小数部分和循环小数部分
  • 分数转换：将有理数转换为分数形式 [分子, 分母]，对于循环小数使用公式：分子 = (完整数字 - 非循环数字)，分母 = (循环部分长度个9 + 非循环部分长度个0)
  • 分数化简：使用最大公约数(GCD)将分数化为最简形式
  • 相等判断：比较两个分数是否相等，通过交叉相乘判断 n1 * d2 === n2 * d1
  • BigInt 处理：由于数字可能很大，使用 BigInt 类型避免精度问题
  • 特殊情况：正确处理无小数部分、无循环部分等边界情况