592.分数加减运算 纯纯的数学题，Python 7行代码+详细
2022-09-13 本文已影响0人
清风Python
592.分数加减运算
https://leetcode.cn/problems/fraction-addition-and-subtraction/solution/by-qingfengpython-g1mn/
难度：中等
题目：
给定一个表示分数加减运算的字符串expression，你需要返回一个字符串形式的计算结果。
这个结果应该是不可约分的分数，即最简分数。如果最终结果是一个整数，例如2，你需要将它转换成分数形式，其分母为1。
所以在上述例子中, 2应该被转换为2/1。
提示:
- 输入和输出字符串只包含'0' 到'9'的数字，以及'/', '+' 和'-'。
- 输入和输出分数格式均为±分子/分母。如果输入的第一个分数或者输出的分数是正数，则'+'会被省略掉。
- 输入只包含合法的最简分数，每个分数的分子与分母的范围是[1,10]。如果分母是1，意味着这个分数实际上是一个整数。
- 输入的分数个数范围是 [1,10]。
- 最终结果的分子与分母保证是 32 位整数范围内的有效整数。
示例：
示例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，不会存在两位数，使得难度进一步降低。
下来考虑以下，我们该以什么方式分割这些表达式：
- 表达式字符串是一个个的个位数除法公式
- 除了除法以外只涉及+ 、 - 法两个符号
- 减法可以转化为 (+)-的方式，比如 -10 == (+)-10
- 那么我们使用replace将所有-号转化为+-
- 再通过+号即可分割所有个位的除法公式
通过上述思路已经将表达式分割成单个的除法，下来该怎么做？
既然最终仍要表达仍需要分式结尾，那么可以通过求所有分母的最小公倍数，然后将每个分子等比放大求和。
最终将分子总和与分母的最小公倍数，求最大公约数(即分子、分母约分)，返回答案即可。
解题：
Python:
from math import gcd
class Solution:
def fractionAddition(self, expression: str) -> str:
stack = [list(map(int, i.split('/'))) for i in expression.replace('-', '+-').split('+') if i]
mod, total = 1, 0
for i in stack:
mod *= i[1] // gcd(mod, i[1])
for i in stack:
total += mod // i[1] * i[0]
return '%s/%s' % (total // gcd(total, mod), mod // gcd(total, mod))
欢迎关注我的公_众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
