• 【LeetCode】592. 分数加减运算


    题目

    592. 分数加减运算

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

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

    示例 1:

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

    示例 2:

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

    示例 3:

    输入: expression = "1/3-1/2"
    输出: "-1/6"
    
    • 1
    • 2

    提示:

    • 输入和输出字符串只包含 '0''9' 的数字,以及 '/', '+''-'
    • 输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数,则 '+' 会被省略掉。
    • 输入只包含合法的最简分数,每个分数的分子分母的范围是 [1,10]。 如果分母是1,意味着这个分数实际上是一个整数。
    • 输入的分数个数范围是 [1,10]。
    • 最终结果的分子与分母保证是 32 位整数范围内的有效整数。

    思路

    • 遍历字符串,通过=-符号将字符串分隔为多个分数运算
    • 分数运算的方式为:
      • 将分数分隔成分子和分母,并转化为整数
      • 通分为两个分母的积
      • 进行运算
      • 约分:分子和分母除以他们的最大公因数

    代码

    class Solution:
        def fractionAddition(self, expression: str) -> str:
            def calc(a: str, b: str, operator: str):
                operands = a.split("/")
                a1 = int(operands[0])
                a2 = int(operands[1])
    
                operands = b.split("/")
                b1 = int(operands[0])
                b2 = int(operands[1])
    
                b3 = a2*b2
                a3 = a1 * b2 + a2*b1 if operator == "+" else a1 * b2 - a2*b1
                mod = math.gcd(a3,b3)
                a3 //= mod
                b3 //= mod
                return F"{a3}/{b3}"
            if expression[0] == "-": expression = "0/1"+expression
            
            if len(expression) <3: return expression
            i = 0
            while i < len(expression) and expression[i] not in "+-": i += 1
            ret = expression[:i]
    
            while i < len(expression):
                start = i
                i+=1
                while i < len(expression) and expression[i] not in "+-": i += 1
                ret = calc(ret, expression[start+1:i], expression[start])
            return ret
    
    • 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

    复杂度

    • 时间复杂度: O ( n + log ⁡ C ) O(n+\log C) O(n+logC)
    • 空间复杂度: O ( 1 ) O(1) O(1)
  • 相关阅读:
    Jenkins配置远程服务器之Publish over SSH、SSH Servers
    用代码实现全自动化批量下单官网的 iPhone-14-Pro 集成智能下单购物系统,附源码可直接运行
    这几个音乐伴奏提取的方法快码住了
    LVM_基本操作
    计算机网络层(2)
    linux ubuntu 实用快捷键汇总(持续更新)
    爬虫获取静态网页数据
    ASP.NET Core - 日志记录系统(一)
    全产业链核心升级 集聚创新大展宏图——慕尼黑华南电子展回顾
    CentOS查看CPU、内存、网络流量和磁盘 I/O
  • 原文地址:https://blog.csdn.net/apple_50661801/article/details/126007423