LeetCode 题解工作台
分数加减运算
给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 这个结果应该是不可约分的分数，即 最简分数 。 如果最终结果是一个整数，例如 2 ，你需要将它转换成分数形式，其分母为 1 。所以在上述例子中, 2 应该被转换为 2/1 。 示例 1: 输入: expr…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数学·string
答案摘要
class Solution: def fractionAddition(self, expression: str) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给定一个表示分数加减运算的字符串 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 位整数范围内的有效整数。
解题思路
方法一：数学
class Solution:
def fractionAddition(self, expression: str) -> str:
x, y = 0, 6 * 7 * 8 * 9 * 10
if expression[0].isdigit():
expression = '+' + expression
i, n = 0, len(expression)
while i < n:
sign = -1 if expression[i] == '-' else 1
i += 1
j = i
while j < n and expression[j] not in '+-':
j += 1
s = expression[i:j]
a, b = s.split('/')
x += sign * int(a) * y // int(b)
i = j
z = gcd(x, y)
x //= z
y //= z
return f'{x}/{y}'
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(\log(\min(a, b))) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates a clear understanding of fraction arithmetic and simplification.
- question_mark
They can efficiently manipulate strings to parse and handle fractions correctly.
- question_mark
The candidate can break down complex mathematical problems into simpler, manageable steps, ensuring correctness in the final result.
常见陷阱
外企场景- error
Misinterpreting the sign of a fraction when parsing the string can lead to incorrect results.
- error
Forgetting to simplify the resulting fraction to its irreducible form can cause unnecessary complexity in the answer.
- error
Overcomplicating the process by not handling fractions step by step, which could lead to inefficient or erroneous calculations.
进阶变体
外企场景- arrow_right_alt
Handling more complex expressions with mixed operations (e.g., multiple additions and subtractions in the same expression).
- arrow_right_alt
Returning the result as a decimal instead of a fraction, while maintaining accuracy.
- arrow_right_alt
Working with fractions that involve larger numbers, requiring more efficient GCD algorithms.