leetcode 592. Fraction Addition and Subtraction | 592. 分数加减运算（最大公因数gcd，最小公倍数lcm）

「爱情、让人受尽委屈。」 2022-08-28 09:58 104阅读 0赞

## 题目 ##

[https://leetcode.com/problems/fraction-addition-and-subtraction/][https_leetcode.com_problems_fraction-addition-and-subtraction]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

这题既简单又麻烦，一道 hard 的 easy 题，被划分在了 medium…

说白了就是把分数相加，注意最后要约分。  
剩下的都是细节了，直接看代码吧。

class Frac { 
        int a; // 分子
        int b; // 分母
    
        public Frac(int a, int b) { 
            this.a = a;
            this.b = b;
        }
    }
    
    class Solution { 
        public String fractionAddition(String exp) { 
            if (exp.charAt(0) != '-') exp = "+" + exp;
    
            Frac frac = null;
            int[] arr = new int[3]; // arr[0]分子，arr[1]分母，arr[2]符号
            int pos = 0;
            for (int i = 0; i < exp.length(); i++) { 
                if (exp.charAt(i) == '/') { 
                    pos = 1;
                } else if (exp.charAt(i) == '+' || exp.charAt(i) == '-') { 
                    // 清算上一个数
                    if (frac != null) frac = add(frac, new Frac(arr[2] * arr[0], arr[1]));
                    else if (i > 0) frac = new Frac(arr[2] * arr[0], arr[1]);
                    // 初始化下一个数
                    Arrays.fill(arr, 0);
                    pos = 0;
                    arr[2] = exp.charAt(i) == '-' ? -1 : 1;
                } else { 
                    arr[pos] *= 10;
                    arr[pos] += (exp.charAt(i) - '0');
                }
            }
            // 清算末尾
            if (frac != null) frac = add(frac, new Frac(arr[2] * arr[0], arr[1]));
            else frac = new Frac(arr[2] * arr[0], arr[1]);
    
            return frac.a + "/" + frac.b;
        }
    
        public Frac add(Frac n1, Frac n2) { 
            // 通分&求和
            int b = lcm(n1.b, n2.b); // 新分母
            int a = n1.a * (b / n1.b) + n2.a * (b / n2.b); // 新分子
            // 约分
            int gcd = Math.abs(gcd(a, b));
            a /= gcd;
            b /= gcd;
            return new Frac(a, b);
        }
    
        // 最大公因数
        static int gcd(int a, int b) { 
            if (a == 0) return b;
            return gcd(b % a, a);
        }
    
        // 最小公倍数
        static int lcm(int a, int b) { 
            return (a / gcd(a, b)) * b;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_fraction-addition-and-subtraction]: https://leetcode.com/problems/fraction-addition-and-subtraction/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/09b840e18da246fa8c762d60e08dea7d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/587743e3c7cf41b982b82de5ec2ee9f7.png