LeetCode题练习与总结：分数加减运算--592

一、题目描述

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 

这个结果应该是不可约分的分数，即 最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 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 位整数范围内的有效整数。

二、解题思路

1. 首先定义一个分数类（Fraction），包含分子（numerator）和分母（denominator）两个属性，并实现分数的加法和通分方法。

2. 解析输入的字符串表达式，将其分解为多个分数。

3. 遍历分解出的分数，将它们依次相加。

4. 在相加的过程中，需要通分，使得两个分数具有相同的分母。

5. 相加完成后，对结果进行化简，得到最简分数。

6. 将最简分数转换为字符串形式并返回。

三、具体代码

class Solution {
    public String fractionAddition(String expression) {
        // 解析表达式，得到分数列表
        List<Fraction> fractions = parseExpression(expression);
        // 初始化结果分数为0/1
        Fraction result = new Fraction(0, 1);
        // 遍历分数列表，依次相加
        for (Fraction fraction : fractions) {
            result = result.add(fraction);
        }
        // 返回最简分数的字符串形式
        return result.toString();
    }

    private List<Fraction> parseExpression(String expression) {
        List<Fraction> fractions = new ArrayList<>();
        int start = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                if (i > 0) {
                    fractions.add(new Fraction(expression.substring(start, i)));
                }
                start = i;
            }
        }
        fractions.add(new Fraction(expression.substring(start)));
        return fractions;
    }

    class Fraction {
        int numerator;
        int denominator;

        public Fraction(int numerator, int denominator) {
            this.numerator = numerator;
            this.denominator = denominator;
        }

        public Fraction(String fraction) {
            int sign = 1;
            int i = 0;
            if (fraction.charAt(0) == '-') {
                sign = -1;
                i = 1;
            } else if (fraction.charAt(0) == '+') {
                i = 1;
            }
            int slashIndex = fraction.indexOf('/');
            this.numerator = sign * Integer.parseInt(fraction.substring(i, slashIndex));
            this.denominator = Integer.parseInt(fraction.substring(slashIndex + 1));
        }

        public Fraction add(Fraction other) {
            // 通分
            int lcm = lcm(this.denominator, other.denominator);
            int newNumerator = this.numerator * (lcm / this.denominator) + other.numerator * (lcm / other.denominator);
            return new Fraction(newNumerator, lcm).reduce();
        }

        private Fraction reduce() {
            int gcd = gcd(Math.abs(this.numerator), this.denominator);
            return new Fraction(this.numerator / gcd, this.denominator / gcd);
        }

        private int gcd(int a, int b) {
            while (b != 0) {
                int temp = a % b;
                a = b;
                b = temp;
            }
            return a;
        }

        private int lcm(int a, int b) {
            return a * b / gcd(a, b);
        }

        @Override
        public String toString() {
            return this.numerator + "/" + this.denominator;
        }
    }
}

这段代码首先定义了一个内部类Fraction，用于表示分数并进行分数的加法和化简操作。然后，fractionAddition方法通过解析输入字符串，创建分数列表，并将它们相加得到最终结果。最后，将结果分数转换为字符串形式并返回。

四、时间复杂度和空间复杂度

1. 时间复杂度

• parseExpression 方法：

  • 遍历整个表达式字符串一次，时间复杂度为 O(n)，其中 n 是表达式的长度。
  • 在每次循环中，进行常数时间的操作（如字符比较、字符串截取等），所以这部分的时间复杂度是 O(1)。
  • 因此，parseExpression 方法总的时间复杂度是 O(n)。

• fractionAddition 方法：

  • 调用 parseExpression 方法，时间复杂度为 O(n)。
  • 遍历分数列表，列表中的元素个数与表达式中的分数数量成正比，假设为 m 个分数，则遍历的时间复杂度为 O(m)。
  • 在每次循环中，进行分数的加法操作，由于加法操作中包含通分和化简，其时间复杂度为 O(1)（因为分母和分子的最大值是固定的，所以 gcd 和 lcm 的计算时间可以认为是常数）。
  • 因此，fractionAddition 方法总的时间复杂度是 O(n + m)，由于 m ≤ n，可以简化为 O(n)。

2. 空间复杂度

• parseExpression 方法：

  • 创建了一个分数列表，其大小与表达式中的分数数量成正比，假设为 m 个分数，则空间复杂度为 O(m)。
  • 临时变量（如 start 和循环变量 i）占用常数空间，所以这部分的空间复杂度是 O(1)。
  • 因此，parseExpression 方法总的空间复杂度是 O(m)。

• fractionAddition 方法：

  • 调用 parseExpression 方法，空间复杂度为 O(m)。
  • 使用了几个临时变量（如 result），这些变量占用常数空间，所以这部分的空间复杂度是 O(1)。
  • 因此，fractionAddition 方法总的空间复杂度是 O(m)。

综上所述，整个算法的时间复杂度是 O(n)，空间复杂度是 O(m)，其中 n 是输入表达式的长度，m 是表达式中的分数数量。由于 m ≤ n，可以认为空间复杂度也是 O(n)。

五、总结知识点

• 面向对象编程（OOP）：

  • 类的定义（class 关键字）。
  • 类的构造方法（public Fraction(...)）。
  • 类的成员变量（int numerator; int denominator;）。
  • 类的成员方法（public Fraction add(Fraction other) 等）。
  • 内部类的定义（class Fraction 在 Solution 类内部）。

• 字符串操作：

  • 字符串的截取（substring 方法）。
  • 字符串的查找（indexOf 方法）。
  • 字符串转换为整数（Integer.parseInt 方法）。

• 数学运算：

  • 最大公约数（GCD）的计算。
  • 最小公倍数（LCM）的计算。
  • 分数的加法运算。
  • 分数的化简。

• 数据结构：

  • List 接口的使用。
  • ArrayList 类的使用，用于存储分数列表。

• 算法：

  • 分数的通分算法。
  • 分数的化简算法。

• 控制流：

  • 循环结构（for 循环）。
  • 条件判断（if 语句）。

• 递归：

  • gcd 方法使用了递归算法来计算最大公约数。

• 重载方法：

  • toString 方法的重写，用于自定义对象的字符串表示。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。