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%

Related Posts

1026. 节点与其祖先之间的最大差值

## 题目描述:给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)示例 1: ![](/img/leetcode/1026节点与其祖先之间的最大差值/tmp-tre

read more

1038. 从二叉搜索树到更大和树

## 题目描述:给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:- 节点的左子树仅包含键 小于 节点键的节点。 - 节点的右子树仅包含键 大于 节点键的节点。 - 左右子树也必须是二叉搜索树。*示例 1:***![](/img/leetcode/

read more

105. 从前序与中序遍历序列构造二叉树

## 题目描述:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1: ``` 输入: preorder = [3,9,20,15,7], inorder = [

read more

106. 从中序与后序遍历序列构造二叉树

## 题目描述:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例 1: ``` 输入:inorder = [9,3,15,20,7], postorder

read more

109. 有序链表转换二叉搜索树

## 题目描述:给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。示例 1: ``` 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9

read more

114. 二叉树展开为链表

## 题目描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1: ``` 输入:root

read more