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]。
解题分析及思路:
本题可以直接模拟,首先定义两个变量用来保存历史计算后的分子分母
denominator, numerator := 0, 1 // 分子,分母
随后,分别统计每一个分数的分子、分母,分子携带符号
- 分子:因为输入和输出分数格式均为 ±分子/分母,所以分子后面一定是
/
,所以判断当前元素是否为/
来判断分子是否结束 - 分母:分母后面可能是
+
或-
,所以判断当前元素是否为+
或-
来判断分母是否结束
sign := 1
// 读取符号
if expression[i] == '-' || expression[i] == '+' {
if expression[i] == '-' {
sign = -1
}
i++
}
// 读取分子
denominator1 := 0
for i < l && expression[i] != '/' {
denominator1 = denominator1*10 + int(expression[i]-'0')
i++
}
denominator1 *= sign
i++
// 读取分母
numerator1 := 0
for i < l && expression[i] != '+' && expression[i] != '-' {
numerator1 += numerator1*10 + int(expression[i]-'0')
i++
}
最后,根据分数的计算公式,分子 = 分子1 * 分母2 + 分子2 * 分母1
,分母 = 分母1 * 分母2
denominator = denominator*numerator1 + denominator1*numerator
numerator *= numerator1
最后进行分子分母约分即可。
gcd := func(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
g := gcd(abs(denominator), numerator)
return fmt.Sprintf("%d/%d", denominator/g, numerator/g)
复杂度:
- 时间复杂度:O(n)
- 空间复杂度:O(1)
执行结果:
- 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户
- 内存消耗:1.9 MB, 在所有 Go 提交中击败了60.00%的用户
Tags :
通过次数 30K 提交次数 50.1K 通过率 59.8%