【LeetCode】592. 分数加减运算

这题也不难

所有的减法都可以看成是加法

这题需要一边遍历，一边构建分数然后累加就行

可以单独写出求最大公约数和最小公倍数的方法，这个也是关键

然后第一个分数应该累加到0/1这种格式的分数中

还有就是要注意，在循环累加的过程中发现分子为0了，那么分母可以直接置为1，不需要在求最小公倍数去通分了

非常重要的注意点：

抽离出来的获取最大公约数和最小公倍数的函数的参数要是一个非负数

代码如下：

    public String fractionAddition(String expression) {
        // 两两分数相加时的两个分数（因为减法的本质还是加法）
        // 数组第一个参数是分子，第二个参数是分母
        int[] fraction1 = new int[2], fraction2 = new int[2];
        // 第一个分数分子为0，分母为1，在遍历式子的过程中找到的分数都是分数2，分数2不断累加到分数1中
        fraction1[0] = 0;
        fraction1[1] = 1;
        // 当前分子的正负情况，正是1，负是-1，默认一开始是正
        int sign = 1;
        // 下一个数到底是分子还是分母，分子是0，分母是1
        int location = 0;
        // 式子的长度
        int len = expression.length();

        // 遍历字符串
        for (int i = 0; i < len; i++) {
            char ch = expression.charAt(i);
            // 如果这一位是0的话，说明这个数字是10，在前一个循环中已经考虑过了，所以跳过
            // '/'也不需要额外考虑
            if (ch == '0' || ch == '/') {
                continue;
            } else if (ch == '+') {
                // 当这一位是‘+’时，说明这个数的分子是正的
                sign = 1;
            } else if (ch == '-') {
                // 当这一位是‘-’时，说明这个数的分子是负的
                sign = -1;
            } else {
                // 当这一位是一个数字时，去构建分数
                // 如果这一位是1，需要判断下一位是否存在且是不是0，如果是的话，这个数字应该是10
                if (ch == '1' && i != len - 1 && expression.charAt(i + 1) == '0') {
                    fraction2[location] = 10;
                } else {
                    // 不然的话，就把这个数字的值存到对应的分子或者分母中去
                    fraction2[location] = ch - '0';
                }

                // 如果这一位是分母的话，说明这个分数统计完毕，我们就可以把这个数2累加到数1上
                if (location == 1) {
                    // 先对两个数的分母求取最小公倍数
                    int commonMultiple = leastCommonMultiple(Math.abs(fraction1[1]), Math.abs(fraction2[1]));
                    // 再求分子
                    fraction1[0] = commonMultiple / fraction1[1] * fraction1[0];
                    fraction2[0] = commonMultiple / fraction2[1] * fraction2[0];
                    fraction1[0] += fraction2[0];
                    // 为分母赋值
                    fraction1[1] = commonMultiple;

                    // 约分
                    int commonDivisor = greatestCommonDivisor(Math.abs(fraction1[0]), Math.abs(fraction1[1]));
                    fraction1[0] /= commonDivisor;
                    fraction1[1] /= commonDivisor;

                    // 如果此时，分数1的分子是0的话，将分母也置为1
                    if (fraction1[0] == 0) {
                        fraction1[1] = 1;
                    }
                } else {
                    // 是分子的话，需要加上符号
                    fraction2[0] *= sign;
                }

                // 确定下一个数是分子还是分母
                location ^= 1;
            }
        }

        return fraction1[0] + "/" + fraction1[1];
    }

    
    public int leastCommonMultiple(int m, int n) {
        int max = (m > n) ? m : n;
        for (int i = max; i <= m * n; i++) {
            if ((i % m == 0) && (i % n == 0)) {
                return i;
            }
        }
        return 0;
    }

    
    public int greatestCommonDivisor(int m, int n) {
        int min = (m <= n) ? m : n;
        for (int i = min; i >= 1; i--) {
            if ((m % i == 0) && (n % i == 0)) {
                return i;
            }
        }
        return 1;
    }