侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【字符串, 模拟】分数加减运算

GabrielxD
2022-07-27 / 0 评论 / 0 点赞 / 50 阅读 / 884 字 / 正在检测是否收录...

题目

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]。
  • 最终结果的分子与分母保证是 32 位整数范围内的有效整数。

解题

方法一:字符串 模拟

思路

把整个表达式按照 '+''-' 分割为单独的分数,分割出来的分数两两累加(分出第一个分数时,累加的结果(ans)为空串,直接把该分数赋值给累加值)。

分数相加:输入的两个分数先分出4个数然后直接做分数加和(a1a2+b1b2=a1×b2+a2×b1a2×b2\frac{a_1}{a_2}+\frac{b_1}{b_2}=\frac{a_1 \times b_2 + a_2 \times b_1}{a_2 \times b_2}),分子如果为负数则把结果分数初始化为 "-" 否则为空,然后求出分子的绝对值与分母的最大公因数,分子分母同除最大公因数加入结果分数中返回。

代码

class Solution {
    public String fractionAddition(String expression) {
        int n = expression.length();
        char[] chs = expression.toCharArray();
        String ans = "", frac;
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n && chs[j] != '+' && chs[j] != '-') j++;
            frac = expression.substring(i, j);
            ans = "".equals(ans) ? frac : clac(frac, ans);
            i = j;
        }
        return ans;
    }

    private String clac(String a, String b) {
        int splitA = a.indexOf('/'), splitB = b.indexOf('/');
        int a1 = Integer.parseInt(a.substring(0, splitA)), a2 = Integer.parseInt(a.substring(splitA + 1));
        int b1 = Integer.parseInt(b.substring(0, splitB)), b2 = Integer.parseInt(b.substring(splitB + 1));
        int m = a1 * b2 + a2 * b1, n = a2 * b2;
        StringBuilder res = new StringBuilder(m < 0 ? "-" : "");
        int mnGCD = gcd(m = Math.abs(m), n);
        res.append(m / mnGCD).append('/').append(n / mnGCD);
        return res.toString();
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
class Solution {
public:
    string clac(const string &a, const string &b) {
        int splitA = a.find('/'), splitB = b.find('/');
        int a1 = stoi(a.substr(0, splitA)), a2 = stoi(a.substr(splitA + 1));
        int b1 = stoi(b.substr(0, splitB)), b2 = stoi(b.substr(splitB + 1));
        int m = a1 * b2 + a2 * b1, n = a2 * b2;
        string res;
        if (m < 0) {
            res += '-';
            m = -m;
        }
        int gcd = __gcd(m, n);
        res += to_string(m / gcd) + "/" + to_string(n / gcd);
        return res;
    }

    string fractionAddition(string expr) {
        int n = expr.length();
        string ans, frac;
        for (int i = 0, j = 1; i < n; i = j, j++) {
            while (j < n && expr[j] != '+' && expr[j] != '-') j++;
            frac = expr.substr(i, j - i);
            ans = ans == "" ? frac : clac(ans, frac);
        }
        return ans;
    }
};
0

评论区