Medium
Related Topics: Math / String / Simulation
LeetCode Source

解題想法

首先我們要定義分子跟分母為0跟1

之後在尋訪時依照以下步驟

我們在分子的部份

當前遇到分數之分子乘以目前加總之分母

加上

當前遇到分數之分母乘以目前加總之分子

在分母的部份直接乘以當前遇到之分母

之後就是找尋加總分子跟分母的最大公因數

然後將當前加總分子跟分母除以最大公因數

最後回傳字串分子 + "/" + 分母

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Python

class Solution:
    def fractionAddition(self, expression: str) -> str:
        up, down = 0, 1

        i = 0

        while i < len(expression):
            sign = 1
            if expression[i] == '-':
                sign = -1
                i += 1
            elif expression[i] == '+':
                i += 1

            up_num = 0

            while i < len(expression) and expression[i].isdigit():
                up_num = up_num * 10 + int(expression[i])
                i += 1

            up_num *= sign
            i+= 1

            down_num = 0

            while i < len(expression) and expression[i].isdigit():
                down_num = down_num * 10 + int(expression[i])
                i += 1

            up = up * down_num + up_num * down
            down *= down_num

            if up == 0:
                down = 1    
            else:
                ccc = gcd(abs(up), down)
                up //= ccc
                down //= ccc

        return f"{up}/{down}"

C++

class Solution {
public:
    string fractionAddition(string expression) {
        std::istringstream iss (expression);
        int up = 0, down = 1, n_up, n_down;
        char dummy;
        while (iss >> n_up >> dummy >> n_down) {
            up = up * n_down + n_up * down;
            down *= n_down;
            int gcd = std::gcd(abs(up), down);
            up /= gcd;
            down /= gcd;
        }

        string res = "";

        res += to_string(up);
        res += "/";
        res += to_string(down);

        return res;
    }
};