LeetCode·每日一题·592.分数加减运算·模拟

题目

 

示例

 

思路

解题思路
题目说不会超过 int 范围，因此必定同分的时候不会溢出！题目中分子分母要求明确，因此使用两个数组，表示分子和分母，其中符号位在分子中体现，然后进行上面类似 reduce 操作进行模拟计算。

1.预处理
由于没有正则提取，有点麻烦，但是其规律也就是开头不同，其余的都是 +/- 数字，因此只要处理开头的不标准的格式就可以解决问题。
比如：-1/2+1/3:开头的 -1/2 单独处理，直接拿出来，后面的分式全是 符号 + 数字。
再比如 1/2+1/2:这种也是把开头 1/2 直接提取出来，然后处理后面的。

AtoI:函数如同符号分割读取一样，在上面预处理操作后，所有的分式出现形式都是一样的。即读取 +- 之前的数字，以 / 作为分子分母的分隔位，我们以布尔变量 bool isDividend = true;表示当前是在读取分子，否则遇到 / 就换成分母，直到函数遇到符号或者字符串结束，最后返回终止位置。
2.通分化简
求 gcd 然后通分化简，这里使用的是通分一次化简一次，不然可能越乘越大，可能会有溢出风险。

代码

#define abs(a) ((a) >= 0 ? (a) : (a) * -1)

int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int AtoI(char * expression, int idx, int *digits) {
    bool isDividend = true;
    while (expression[idx] != '\0' && expression[idx] != '+' && expression[idx] != '-') {
        if (expression[idx] == '/') {
            isDividend = false;
        } else if (isDividend) {
            digits[0] = digits[0] * 10 + expression[idx] - 48;
        } else {
            digits[1] = digits[1] * 10 + expression[idx] - 48;
        }
        idx++;
    }
    return idx;  // 符号位
}

char * fractionAddition(char * expression){
    int digits1[] = {0, 0}, digits2[] = {0, 0};  // 分子、分母
    int idx = 0, symbol = 1;
    if (*expression == '-') {
        symbol = -1;
        idx++;
    }
    idx = AtoI(expression, idx, digits1);
    digits1[0] *= symbol;  // 符号位
    while (expression[idx] != '\0') {
        symbol = expression[idx] == '+' ? 1 : -1;  // 符号位
        idx = AtoI(expression, idx + 1, digits2);
        int lcm = (digits1[1] * digits2[1]) / gcd(digits1[1], digits2[1]);  // 算最小公倍数
        int dividend = digits1[0] * (lcm / digits1[1]) + symbol * digits2[0] * (lcm / digits2[1]);
        int _gcd = gcd(abs(dividend), lcm);  // 化简分子分母最小公因数
        digits1[0] = dividend / _gcd;  // 分子化简
        digits1[1] = lcm / _gcd;  // 分母化简
        memset(digits2, 0, sizeof(int) * 2);  // 需要注意清空，否则下次计算错误
    }

    char *res;
    asprintf(&res, "%d/%d", digits1[0], digits1[1]);
    return res;
}

时间空间复杂度