Medium

题目描述

给定一个表示分数加减运算的字符串表达式，返回字符串格式的计算结果。

最终结果应该是一个不可约分的分数。如果最终结果是一个整数，请将其转换为分母为1的分数格式。因此在这种情况下，2应该转换为2/1。

示例 1：

输入：expression = "-1/2+1/2"
输出："0/1"

示例 2：

输入：expression = "-1/2+1/2+1/3"
输出："1/3"

示例 3：

输入：expression = "1/3-1/2"
输出："-1/6"

约束条件：

  • 输入字符串只包含 ‘0’ 到 ‘9’，’/’，’+’ 和 ‘-’。输出也是如此。
  • 每个分数（输入和输出）都有格式 ±分子/分母。如果第一个输入分数或输出是正数，则 ‘+’ 将被省略。
  • 输入只包含有效的不可约分分数，其中每个分数的分子和分母总是在 [1, 10] 范围内。如果分母是1，则表示此分数实际上是上述定义的分数格式的整数。
  • 给定分数的数量将在 [1, 10] 范围内。
  • 最终结果的分子和分母保证是有效的并且在32位int的范围内。

解题思路

这道题需要解析字符串表达式中的分数，并进行加减运算，最后返回最简分数。

解题思路：

  1. 字符串解析：遍历表达式字符串，提取每个分数的符号、分子和分母。需要注意第一个分数可能没有符号（默认为正）。

  2. 分数运算：对于两个分数 a/b 和 c/d，它们的加减运算为 (ad ± cb)/(b*d)。可以维护一个累加的分数结果。

  3. 最大公约数化简：每次运算后，使用最大公约数（GCD）将结果化简为最简分数。

  4. 符号处理：统一处理分数的符号，确保分母为正数，负号统一放在分子上。

算法步骤：

  • 初始化结果分数为 0/1
  • 遍历字符串，解析每个分数的符号、分子、分母
  • 将当前分数与结果分数进行加减运算
  • 使用GCD化简结果
  • 最后格式化输出

时间复杂度： O(n)，其中n是字符串长度，每个字符最多访问一次。 空间复杂度： O(1)，只使用常数额外空间。

代码实现

class Solution {
public:
    string fractionAddition(string expression) {
        int numerator = 0, denominator = 1;
        int i = 0;
        
        while (i < expression.length()) {
            // 解析符号
            int sign = 1;
            if (expression[i] == '+' || expression[i] == '-') {
                sign = expression[i] == '+' ? 1 : -1;
                i++;
            }
            
            // 解析分子
            int num = 0;
            while (i < expression.length() && isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            num *= sign;
            
            // 跳过 '/'
            i++;
            
            // 解析分母
            int den = 0;
            while (i < expression.length() && isdigit(expression[i])) {
                den = den * 10 + (expression[i] - '0');
                i++;
            }
            
            // 计算新的分子分母
            numerator = numerator * den + num * denominator;
            denominator = denominator * den;
            
            // 化简
            int g = gcd(abs(numerator), denominator);
            numerator /= g;
            denominator /= g;
        }
        
        return to_string(numerator) + "/" + to_string(denominator);
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def fractionAddition(self, expression: str) -> str:
        import math
        
        numerator, denominator = 0, 1
        i = 0
        
        while i < len(expression):
            # 解析符号
            sign = 1
            if expression[i] == '+' or expression[i] == '-':
                sign = 1 if expression[i] == '+' else -1
                i += 1
            
            # 解析分子
            num = 0
            while i < len(expression) and expression[i].isdigit():
                num = num * 10 + int(expression[i])
                i += 1
            num *= sign
            
            # 跳过 '/'
            i += 1
            
            # 解析分母
            den = 0
            while i < len(expression) and expression[i].isdigit():
                den = den * 10 + int(expression[i])
                i += 1
            
            # 计算新的分子分母
            numerator = numerator * den + num * denominator
            denominator = denominator * den
            
            # 化简
            g = math.gcd(abs(numerator), denominator)
            numerator //= g
            denominator //= g
        
        return f"{numerator}/{denominator}"

public class Solution {
    public string FractionAddition(string expression) {
        int numerator = 0, denominator = 1;
        int i = 0;
        
        while (i < expression.Length) {
            // 解析符号
            int sign = 1;
            if (expression[i] == '+' || expression[i] == '-') {
                sign = expression[i] == '+' ? 1 : -1;
                i++;
            }
            
            // 解析分子
            int num = 0;
            while (i < expression.Length && char.IsDigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            num *= sign;
            
            // 跳过 '/'
            i++;
            
            // 解析分母
            int den = 0;
            while (i < expression.Length && char.IsDigit(expression[i])) {
                den = den * 10 + (expression[i] - '0');
                i++;
            }
            
            // 计算新的分子分母
            numerator = numerator * den + num * denominator;
            denominator = denominator * den;
            
            // 化简
            int g = GCD(Math.Abs(numerator), denominator);
            numerator /= g;
            denominator /= g;
        }
        
        return numerator + "/" + denominator;
    }
    
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

var fractionAddition = function(expression) {
    let numerator = 0, denominator = 1;
    let i = 0;
    
    while (i < expression.length) {
        // 解析符号
        let sign = 1;
        if (expression[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为表达式字符串长度，需要遍历每个字符一次
空间复杂度O(1)只使用常数额外空间存储分子、分母等变量

相关题目