LeetCode刷题实战592分数加减运算

　　算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！
　　今天和大家聊的问题叫做分数加减运算，我们先来看题面：
　　https：leetcodecn。comproblemsfractionadditionandsubtraction
　　Givenastringexpressionrepresentinganexpressionoffractionadditionandsubtraction，returnthecalculationresultinstringformat。
　　Thefinalresultshouldbeanirreduciblefraction。Ifyourfinalresultisaninteger，changeittotheformatofafractionthathasadenominator1。Sointhiscase，2shouldbeconvertedto21。
　　给定一个表示分数加减运算的字符串expression，你需要返回一个字符串形式的计算结果。
　　这个结果应该是不可约分的分数，即最简分数。如果最终结果是一个整数，例如2，你需要将它转换成分数形式，其分母为1。所以在上述例子中，2应该被转换为21。
　　示例示例1：
　　输入：expression1212
　　输出：01
　　示例2：
　　输入：expression121213
　　输出：13
　　示例3：
　　输入：expression1312
　　输出：16
　　解题
　　因为是分数相加，为了便于编写和理解我抽象出了Number表示分数，并实现了分数相加的add方法（通分分子相加）。
　　通分要利用到求最小公倍数，约分要用到求最大公因数。
　　之后就是字符串切割，切出每个带符号的分数，相加即可。classSolution｛
　　classNumber｛
　　分子
　　publicintnumerator；
　　分母
　　publicintdinominator；
　　Number（intnumerator，intdinominator）｛
　　this。numeratornumerator；
　　this。dinominatordinominator；
　　｝
　　publicvoidadd（Numbernumber）｛
　　inttmpDgetMinMultiple（this。dinominator，number。dinominator）；
　　inttmpNthis。numeratortmpDthis。dinominatornumber。numeratortmpDnumber。dinominator；
　　this。numeratortmpN；
　　this。dinominatortmpD；
　　｝
　　｝
　　publicStringfractionAddition（Stringexpression）｛
　　ListlistnewLinkedList；
　　intpre0；
　　for（inti0；iexpression。length；i）｛
　　if（i！0（expression。charAt（i）expression。charAt（i）））｛
　　list。add（stringToNumber（expression。substring（pre，i）））；
　　prei；
　　｝
　　｝
　　list。add（stringToNumber（expression。substring（pre，expression。length）））；
　　NumbernumbernewNumber（0，1）；
　　for（Numbern：list）｛
　　number。add（n）；
　　｝
　　intgcdgcd（number。numerator，number。dinominator）；
　　number。numeratornumber。numeratorgcd；
　　number。dinominatornumber。dinominatorgcd；
　　if（number。dinominator0）｛
　　number。numerator1；
　　number。dinominator1；
　　｝
　　returnnumber。numeratornumber。dinominator；
　　｝
　　字符串转换为分数
　　publicNumberstringToNumber（Stringexpression）｛
　　Stringstrsexpression。split（）；
　　returnnewNumber（Integer。valueOf（strs〔0〕），Integer。valueOf（strs〔1〕））；
　　｝
　　求最大公因数
　　publicintgcd（inta，intb）｛
　　if（b0）｛
　　returna；
　　｝else｛
　　returngcd（b，ab）；
　　｝
　　｝
　　求最小公倍数
　　publicintgetMinMultiple（inta，intb）｛
　　returnabgcd（a，b）；
　　｝
　　｝
　　作者：suspectX
　　链接：https：leetcodecn。comproblemsfractionadditionandsubtractionsolutionjavabysuspectx
　　来源：力扣（LeetCode）
　　著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
　　上期推文：
　　LeetCode1580题汇总，希望对你有点帮助！
　　LeetCode刷题实战581：最短无序连续子数组
　　LeetCode刷题实战582：杀掉进程
　　LeetCode刷题实战583：两个字符串的删除操作
　　LeetCode刷题实战584：寻找用户推荐人
　　LeetCode刷题实战585：2016年的投资
　　LeetCode刷题实战586：订单最多的客户
　　LeetCode刷题实战587：安装栅栏
　　LeetCode刷题实战588：设计内存文件系统
　　LeetCode刷题实战589：N叉树的前序遍历
　　LeetCode刷题实战590：N叉树的后序遍历
　　LeetCode刷题实战591：标签验证器