592.分数加减运算

【LetMeFly】592.分数加减运算：手把手分步のC++讲解

力扣题目链接：https://leetcode.cn/problems/fraction-addition-and-subtraction/

给定一个表示分数加减运算的字符串 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]。
  • 最终结果的分子与分母保证是 32 位整数范围内的有效整数。

方法一：C++模拟

用pair<int, int>表示分数，然后不断模拟即可。

主要需要实现三个功能：

  1. 字符串转分数
    字符串转分数稍微复杂一些。
    首先根据字符串的首个字符判断分数的正负，然后计算分子和分母分别对应字符串中的哪几个字符，最后再把字符串转为int即可。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
       pii string2fraction(string s) {
    	pii ans;
    	// 判断分数的正负
    	if (s[0] == '-') {
    		ans.first = -1;
    	}
    	else {
    		ans.first = 1;
    	}
    	// 计算分子开始位置的下标
    	int l = 0;
    	if (s[0] == '-' || s[0] == '+') {
    		l++;
    	}
    	// 计算分子结束位置的下标
    	int r = l;
    	while (s[r] != '/')
    		r++;
    	// 计算分子分母
    	ans.first *= atoi(s.substr(l, r - l).c_str());
    	ans.second = atoi(s.substr(r + 1, s.size() - r -1).c_str());
    	return ans;
    }
  2. 两个分数相加
    分数相加首先要通分。
    令新的分母为原本两个分数的最小公倍数，然后将两个分数的分子分别化为通分后的值并累加，最后进行约分即可。
    注意分子分母约分的时候，__gcd()函数调用时记得传入分子分母的绝对值，否则求得的最小公倍数可能会为负数。 
    1
    2
    3
    4
    5
    6
    7
    8
    pii add(pii p1, pii p2) {
        pii ans;
        ans.second = p1.second * p2.second / __gcd(p1.second, p2.second);
        ans.first = p1.first * (ans.second / p1.second) + p2.first * (ans.second / p2.second);
        int gcd = __gcd(abs(ans.first), ans.second);
        ans.first /= gcd, ans.second /= gcd;
        return ans;
    }
  3. 将分数转为字符串
    这个功能实现起来相对容易，只需要将分子分母分别转为字符串，并在中间加上/即可。 
    1
    2
    3
    string fraction2string(pii f) {
        return to_string(f.first) + "/" + to_string(f.second);
    }

实现了上述三个功能，只需要在主函数中对原始字符串按加减号进行分割，并把每个分割出来的分数的值累加即可。

1
2
3
4
5
6
7
8
9
10
11
12
string fractionAddition(string expression) {
	pii ans = {0, 1};
	int last = 0;  // 上一个处理到的字符的位置
	for (int i = 1; i < expression.size(); i++) {
		if (expression[i] == '+' || expression[i] == '-') {  // 遇到加减号就开始分割
			ans = add(ans, string2fraction(expression.substr(last, i - last)));
			last = i;
		}
	}
	ans = add(ans, string2fraction(expression.substr(last, expression.size() - last)));  // 注意字符串末尾没有加减号，不要把最后一个分数遗漏了。
	return fraction2string(ans);
}

拓展：

如果想要debug分数长啥样，可以直接重载运算符<<

1
2
3
4
ostream &operator << (ostream& out, pii& p) {
    out << p.first << "/" << p.second;
    return out;
}

这样，当想要debug时，就可以直接

1
2
pair<int, int> fraction = {1, 2};
cout << fraction << endl;

了。

  • 时间复杂度$O(n)$，其中$n$是字符串长度
  • 空间复杂度$O(m)$，其中$m$是一个分数的字符串的平均长度

AC代码

C++

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
typedef pair<int, int> pii;

ostream &operator << (ostream& out, pii& p) {
    out << p.first << "/" << p.second;
    return out;
}

class Solution {
private:
    pii string2fraction(string s) {
        pii ans;
        if (s[0] == '-') {
            ans.first = -1;
        }
        else {
            ans.first = 1;
        }
        int l = 0;
        if (s[0] == '-' || s[0] == '+') {
            l++;
        }
        int r = l;
        while (s[r] != '/')
            r++;
        ans.first *= atoi(s.substr(l, r - l).c_str());
        ans.second = atoi(s.substr(r + 1, s.size() - r - 1).c_str());

        // cout << s << " -> " << ans << endl;

        return ans;
    }

    pii add(pii p1, pii p2) {
        pii ans;
        ans.second = p1.second * p2.second / __gcd(p1.second, p2.second);
        ans.first = p1.first * (ans.second / p1.second) + p2.first * (ans.second / p2.second);
        int gcd = __gcd(abs(ans.first), ans.second);
        ans.first /= gcd, ans.second /= gcd;
        return ans;
    }

    string fraction2string(pii f) {
        return to_string(f.first) + "/" + to_string(f.second);
    }
public:
    string fractionAddition(string expression) {
        pii ans = {0, 1};
        int last = 0;
        for (int i = 1; i < expression.size(); i++) {
            if (expression[i] == '+' || expression[i] == '-') {
                ans = add(ans, string2fraction(expression.substr(last, i - last)));
                last = i;
            }
        }
        ans = add(ans, string2fraction(expression.substr(last, expression.size() - last)));
        return fraction2string(ans);
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126011320

#题解 #模拟 #中等 #数学 #字符串 #LeetCode #重载
592.分数加减运算
https://blog.letmefly.xyz/2022/07/27/LeetCode 0592.分数加减运算/
作者
Tisfy
发布于
2022年7月27日
许可协议