972. 相等的有理数

Hard

题目描述

给定两个字符串 s 和 t，每个字符串都表示一个非负有理数，当且仅当它们表示相同的数字时返回 true。字符串可以使用括号来表示有理数的循环部分。

有理数最多可以用三个部分表示：<整数部分>，<非循环部分> 和 <循环部分>。数字将用以下三种方式之一表示：

<整数部分>
- 例如：12、0 和 123
<整数部分><.><非循环部分>
- 例如：0.5、1.、2.12 和 123.0001
<整数部分><.><非循环部分><(><循环部分><)>
- 例如：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。

约束条件：

每个部分只包含数字
<整数部分> 没有前导零（除了零本身）
1 <= <整数部分>.length <= 4
0 <= <非循环部分>.length <= 4
1 <= <循环部分>.length <= 4

解题思路

这道题要求判断两个有理数字符串是否表示相同的数值。核心思路有两种：

方法一：字符串规范化比较 将两个有理数字符串都转换为统一的标准格式，然后比较是否相同。具体步骤：

解析字符串，提取整数部分、非循环小数部分和循环小数部分
将循环小数展开到足够长的位数（考虑到约束条件，展开到合适长度即可）
去除尾部的0，规范化表示
比较两个规范化后的字符串

方法二：分数转换比较（推荐） 将有理数转换为分数形式进行比较。对于形如 a.b(c) 的循环小数：

设整数部分为 integer
非循环部分为 non_repeat
循环部分为 repeat
则该数可表示为：integer + (non_repeat + repeat/(10^len(repeat) - 1)) / 10^len(non_repeat)

通过分数运算得到最简分数形式，然后比较两个分数是否相等。

这种方法更精确，避免了浮点数精度问题，是最优解法。

代码实现

class Solution {
public:
    bool isRationalEqual(string s, string t) {
        return convertToFraction(s) == convertToFraction(t);
    }
    
private:
    pair<long long, long long> convertToFraction(string s) {
        // 解析字符串
        int dotPos = s.find('.');
        int leftParenPos = s.find('(');
        
        // 整数部分
        long long integerPart = 0;
        if (dotPos != string::npos) {
            integerPart = stoll(s.substr(0, dotPos));
        } else if (leftParenPos != string::npos) {
            integerPart = stoll(s.substr(0, leftParenPos));
        } else {
            integerPart = stoll(s);
            return {integerPart, 1};
        }
        
        // 非循环小数部分
        string nonRepeat = "";
        if (dotPos != string::npos) {
            if (leftParenPos != string::npos) {
                nonRepeat = s.substr(dotPos + 1, leftParenPos - dotPos - 1);
            } else {
                nonRepeat = s.substr(dotPos + 1);
            }
        }
        
        // 循环部分
        string repeat = "";
        if (leftParenPos != string::npos) {
            int rightParenPos = s.find(')', leftParenPos);
            repeat = s.substr(leftParenPos + 1, rightParenPos - leftParenPos - 1);
        }
        
        // 转换为分数
        long long numerator = integerPart;
        long long denominator = 1;
        
        // 添加非循环部分
        if (!nonRepeat.empty()) {
            long long nonRepeatValue = stoll(nonRepeat);
            long long nonRepeatDenom = 1;
            for (int i = 0; i < nonRepeat.length(); i++) {
                nonRepeatDenom *= 10;
            }
            numerator = numerator * nonRepeatDenom + nonRepeatValue;
            denominator = nonRepeatDenom;
        }
        
        // 添加循环部分
        if (!repeat.empty()) {
            long long repeatValue = stoll(repeat);
            long long repeatDenom = 1;
            for (int i = 0; i < repeat.length(); i++) {
                repeatDenom *= 10;
            }
            repeatDenom -= 1;
            
            long long power = 1;
            for (int i = 0; i < nonRepeat.length(); i++) {
                power *= 10;
            }
            
            numerator = numerator * repeatDenom + repeatValue;
            denominator = denominator * repeatDenom;
        }
        
        // 化简分数
        long long g = gcd(numerator, denominator);
        return {numerator / g, denominator / g};
    }
    
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        return self.convertToFraction(s) == self.convertToFraction(t)
    
    def convertToFraction(self, s):
        from math import gcd
        
        # 解析字符串
        dot_pos = s.find('.')
        left_paren_pos = s.find('(')
        
        # 整数部分
        if dot_pos != -1:
            integer_part = int(s[:dot_pos])
        elif left_paren_pos != -1:
            integer_part = int(s[:left_paren_pos])
        else:
            integer_part = int(s)
            return (integer_part, 1)
        
        # 非循环小数部分
        non_repeat = ""
        if dot_pos != -1:
            if left_paren_pos != -1:
                non_repeat = s[dot_pos + 1:left_paren_pos]
            else:
                non_repeat = s[dot_pos + 1:]
        
        # 循环部分
        repeat = ""
        if left_paren_pos != -1:
            right_paren_pos = s.find(')', left_paren_pos)
            repeat = s[left_paren_pos + 1:right_paren_pos]
        
        # 转换为分数
        numerator = integer_part
        denominator = 1
        
        # 添加非循环部分
        if non_repeat:
            non_repeat_value = int(non_repeat)
            non_repeat_denom = 10 ** len(non_repeat)
            numerator = numerator * non_repeat_denom + non_repeat_value
            denominator = non_repeat_denom
        
        # 添加循环部分
        if repeat:
            repeat_value = int(repeat)
            repeat_denom = 10 ** len(repeat) - 1
            power = 10 ** len(non_repeat)
            
            numerator = numerator * repeat_denom + repeat_value
            denominator = denominator * repeat_denom
        
        # 化简分数
        g = gcd(numerator, denominator)
        return (numerator // g, denominator // g)

public class Solution {
    public bool IsRationalEqual(string s, string t) {
        return ConvertToFraction(s).Equals(ConvertToFraction(t));
    }
    
    private (long, long) ConvertToFraction(string s) {
        // 解析字符串
        int dotPos = s.IndexOf('.');
        int leftParenPos = s.IndexOf('(');
        
        // 整数部分
        long integerPart = 0;
        if (dotPos != -1) {
            integerPart = long.Parse(s.Substring(0, dotPos));
        } else if (leftParenPos != -1) {
            integerPart = long.Parse(s.Substring(0, leftParenPos));
        } else {
            integerPart = long.Parse(s);
            return (integerPart, 1);
        }
        
        // 非循环小数部分
        string nonRepeat = "";
        if (dotPos != -1) {
            if (leftParenPos != -1) {
                nonRepeat = s.Substring(dotPos + 1, leftParenPos - dotPos - 1);
            } else {
                nonRepeat = s.Substring(dotPos + 1);
            }
        }
        
        // 循环部分
        string repeat = "";
        if (leftParenPos != -1) {
            int rightParenPos = s.IndexOf(')', leftParenPos);
            repeat = s.Substring(leftParenPos + 1, rightParenPos - leftParenPos - 1);
        }
        
        // 转换为分数
        long numerator = integerPart;
        long denominator = 1;
        
        // 添加非循环部分
        if (!string.IsNullOrEmpty(nonRepeat)) {
            long nonRepeatValue = long.Parse(nonRepeat);
            long nonRepeatDenom = (long)Math.Pow(10, nonRepeat.Length);
            numerator = numerator * nonRepeatDenom + nonRepeatValue;
            denominator = nonRepeatDenom;
        }
        
        // 添加循环部分
        if (!string.IsNullOrEmpty(repeat)) {
            long repeatValue = long.Parse(repeat);
            long repeatDenom = (long)Math.Pow(10, repeat.Length) - 1;
            
            numerator = numerator * repeatDenom + repeatValue;
            denominator = denominator * repeatDenom;
        }
        
        // 化简分数
        long g = GCD(numerator, denominator);
        return (numerator / g, denominator / g);
    }
    
    private long GCD(long a, long b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

var isRationalEqual = function(s, t) {
    function parseRational(str) {
        let integer = '';
        let nonRepeating = '';
        let repeating = '';
        
        let i = 0;
        // Parse integer part
        while (i < str.length && str[i] !== '.') {
            integer += str[i];
            i++;
        }
        
        if (i < str.length && str[i] === '.') {
            i++; // skip '.'
            // Parse non-repeating part
            while (i < str.length && str[i] !== '(') {
                nonRepeating += str[i];
                i++;
            }
            
            if (i < str.length && str[i] === '(') {
                i++; // skip '('
                // Parse repeating part
                while (i < str.length && str[i] !== ')') {
                    repeating += str[i];
                    i++;
                }
            }
        }
        
        return { integer, nonRepeating, repeating };
    }
    
    function toDecimal(parts) {
        let { integer, nonRepeating, repeating } = parts;
        
        if (!integer) integer = '0';
        if (!nonRepeating) nonRepeating = '';
        if (!repeating) repeating = '';
        
        // Handle case where repeating part is all 9s
        if (repeating && repeating.match(/^9+$/)) {
            // Convert 0.9999... to 1.0
            let carry = 1;
            let newNonRepeating = nonRepeating;
            
            // Add 1 to the last digit of non-repeating part
            if (newNonRepeating === '') {
                carry = 1;
                newNonRepeating = '';
            } else {
                let digits = newNonRepeating.split('').map(Number);
                for (let i = digits.length - 1; i >= 0 && carry; i--) {
                    digits[i] += carry;
                    if (digits[i] === 10) {
                        digits[i] = 0;
                    } else {
                        carry = 0;
                    }
                }
                newNonRepeating = digits.join('');
            }
            
            if (carry) {
                integer = (BigInt(integer) + BigInt(1)).toString();
            }
            
            return { integer, nonRepeating: newNonRepeating, repeating: '' };
        }
        
        return { integer, nonRepeating, repeating };
    }
    
    function normalize(parts) {
        let { integer, nonRepeating, repeating } = toDecimal(parts);
        
        // Remove trailing zeros from non-repeating part when there's no repeating part
        if (!repeating) {
            nonRepeating = nonRepeating.replace(/0+$/, '');
        }
        
        // Remove leading zeros from repeating part and handle cycles
        if (repeating) {
            // Find the shortest cycle
            for (let len = 1; len <= repeating.length; len++) {
                let cycle = repeating.substring(0, len);
                let valid = true;
                for (let i = len; i < repeating.length; i += len) {
                    if (repeating.substring(i, i + len) !== cycle.substring(0, Math.min(len, repeating.length - i))) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    repeating = cycle;
                    break;
                }
            }
        }
        
        return integer + '.' + nonRepeating + (repeating ? '(' + repeating + ')' : '');
    }
    
    let partsS = parseRational(s);
    let partsT = parseRational(t);
    
    return normalize(partsS) === normalize(partsT);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(1)	由于字符串长度有限制（最大长度为常数），所有操作都是常数时间
空间复杂度	O(1)	只使用了常数额外空间来存储解析结果和分数

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析