leetcode-592 问题描述

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

这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

示例

1
2

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

题解

对于两个分数 $\dfrac{x_1}{y_1}$ 和 $\dfrac{x_2}{y_2}$，它们相加的结果为：

$\dfrac{x_1 \times y_2 + x_2 \times y_1}{y_1 \times y_2}$

初始分数的分子为 $\textit{x} = 0$，分母为 $\textit{y} = 1$。我们不断从字符串中获取下一个分数，它的分子为 $\textit{x}_1$，分母为 $\textit{y}_1$，将它加到初始分数上，有：

$$ \begin{cases} \textit{x} = \textit{x} \times \textit{y}_1 + \textit{x}_1 \times \textit{y} \\ \textit{y} = \textit{y} \times \textit{y}_1 \end{cases} $$

最后如果 $\textit{x} = 0$，说明结果为零，直接返回 $\text{“0/1”}$；否则计算分子分母的最大公约数，返回约简后分数的字符串表示。

代码（Python）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def fractionAddition(self, expression: str) -> str:
        x, y = 0, 1  # 分子，分母
        i, n = 0, len(expression)
        while i < n:
            # 读取分子
            x1, sign = 0, 1
            if expression[i] == '-' or expression[i] == '+':
                if expression[i] == '-':
                    sign = -1
                i += 1
            while i < n and expression[i].isdigit():
                x1 = x1 * 10 + int(expression[i])
                i += 1
            x1 = sign * x1
            i += 1

            # 读取分母
            y1 = 0
            while i < n and expression[i].isdigit():
                y1 = y1 * 10 + int(expression[i])
                i += 1

            x = x * y1 + x1 * y
            y *= y1
        if x == 0:
            return "0/1"
        g = gcd(abs(x), y)
        return f"{x // g}/{y // g}"

问题转变

将问题转变一下，若字符串中能出现整数，代码需要稍微改动一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    # @classmethod
    def fractionAddition(self, expression: str):
            x, y = 0, 1  # 分子，分母
            i, n = 0, len(expression)
            while i < n:
                # 读取分子
                x1, sign = 0, 1
                if expression[i] == '-' or expression[i] == '+':
                    if expression[i] == '-':
                        sign = -1
                    i += 1
                while i < n and expression[i].isdigit():
                    x1 = x1 * 10 + int(expression[i])
                    i += 1
                x1 = sign * x1
                # 当读取到 '/' 时跳过
                if expression[i] == '/':
                    i += 1

                # 读取分母
                if expression[i].isdigit():
                    y1 = 0
                    while i < n and expression[i].isdigit():
                        y1 = y1 * 10 + int(expression[i])
                        i += 1
                else:
                    # 若为整数，则分母直接等于 1
                    y1 = 1
                x = x * y1 + x1 * y
                y *= y1
            if x == 0:
                return "0/1"
            g = math.gcd(abs(x), y)
            return f"{x // g}/{y // g}"

Python代码总结

gcd() 函数用于计算两个或多个整数的最大公约数

// 运算符是取整除 - 返回商的整数部分（向下取整）

报错：Python: TypeError: xxx() missing 1 required positional argument: ‘xx’

解决：调用一个类的方法需要先实例化，若不实例化应该用class().fun(argument) 来调用类的方法