[leetcode]592. Fraction Addition and Subtraction_leetcode fraction addition and subtraction java-程序员宅基地

技术标签: 其它(重要)  leetcode  

题目链接:https://leetcode.com/problems/fraction-addition-and-subtraction/#/description

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.

Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input:"1/3-1/2"
Output: "-1/6"

Example 4:

Input:"5/3+1/3"
Output: "2/1"

Note:

  1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
  2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
  3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
  4. The number of given fractions will be in the range [1,10].
  5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.


思路:Keep the overall result in A / B, read the next fraction into a / b. Their sum is (Ab + aB) / Bb (but cancel their greatest common divisor).

方法一:


 

class Solution {
public:
    string fractionAddition(string expression) {
        istringstream ss(expression);
        int A = 0, B = 1, a, b;
        char _;
        while (ss >> a >> _ >> b) {
            A = A * b + a * B;
            B *= b;
            int g = abs(GCD(A, B));
            A /= g;
            B /= g;
        }
        return to_string(A) + '/' + to_string(B);
    }
private:
    int GCD(int a, int b )
    {
        return (b == 0) ? a : GCD(b, a % b);
    }

};

 

 方法二:

class Solution {
public:
    string fractionAddition(string expression)
    {
        int n = 0, d = 1, p = 0, p1 = 0, p2 = 0; // n为上一个分子,d为上一个分母
        if (expression[0] != '-') expression = "+" + expression;
        while (p < expression.size())
        {
            for (p1 = p + 1; expression[p1] != '/'; ++p1);
            for (p2 = p1 + 1; p2 < expression.size() && expression[p2] != '+' && expression[p2] != '-'; ++p2);
            auto nn = stoi(expression.substr(p + 1, p1 - p - 1)), dd = stoi(expression.substr(p1 + 1, p2 - p1 - 1));// nn为当前分子,dd为当前分母
            cout<<nn<<"  "<<dd<<endl;
            n=n*dd+(expression[p] == '-' ? -1 : 1)*nn*d;
            d*=dd;
            int g=abs(GCD(n,d));
            n/=g;
            d/=g;
            p=p2;
        }
        return to_string(n) + "/" + to_string(d);

    }
private:
    int GCD(int a, int b )
    {
        return (b == 0) ? a : GCD(b, a % b);
    }

};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xiaocong1990/article/details/75948684

智能推荐

【扩频通信】基于matlab扩频通信系统仿真【含Matlab源码 968期】_扩频matlab代码-程序员宅基地

文章浏览阅读1.3k次,点赞2次,收藏13次。扩频通信系统仿真完整的代码,方可运行;可提供运行操作视频!适合小白!_扩频matlab代码

HNOI2006 潘多拉的盒子-程序员宅基地

文章浏览阅读134次。题目描述题解:题目的描述比较长,理解起来也有一定难度。仔细读题后我们发现整个任务可以分成两个部分:找出咒语机之间所有的升级关系、求最长升级序列。1、求升级关系:容易看出,咒语机i可以抽象成一个图Gi,其顶点集Vi为ni个元件,每个顶点发出两条边——“0”边和“1”边,分别表示将信号加“0”和加“1”。我们枚举两个咒语机A、B(A≠B),判断B是否是A的升级。最简单的...

大数据面试题汇总_hr能问的大数据面试题-程序员宅基地

文章浏览阅读299次。大数据面试题汇总自我介绍hr常问的几道面试题SparkSpark 有什么优缺点?Spark RDD有什么特性kafkaKafka为什么这么快?hbaseHbase系统架构Hbase数据模型HBase vs RDBMSHBase rowkey设计原则HBase 预分区HiveHive order/sort/distribute/cluster by 有什么区别?..._hr能问的大数据面试题

POJ 3083 (bfs + dfs)_nput to this problem will begin with a line contai-程序员宅基地

文章浏览阅读312次。Children of the Candy Corn Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13904 Accepted: 6014Description The cornfield maze is a popular Halloween treat. Visitors are shown_nput to this problem will begin with a line containing a single integer n in

Python 读取某个目录下所有png图片导入Excel_python png插入excel-程序员宅基地

文章浏览阅读1.9k次。一、安装xlsxwriter库pip3 install xlsxwriter二、代码import xlsxwriter, osimage = []# 打包前路径:os.path.abspath(__file__)# 打包后路径:os.path.realpath(sys.executable))# 获取文件目录下所有的.png图片def GetImgPathFromFolder(): for root, dirs, files in os.walk(os.path.dirna_python png插入excel

小学计算机走进智慧城堡教案,重大版(第八版)小学五年级下册信息技术教案设计(修改)-邓荣.doc...-程序员宅基地

文章浏览阅读677次。PAGE 1小学五年级下期信息技术重庆市南岸区教师进修学院附属小学校(2018—2019学年度下期)教 案学 科: 信息技术年 级: 五年级册 次: 下 册教 师:课题第3课 恐龙家族的数字密码第 1 课时课型新 课学习目标1、认识Excel窗口、单元格,能准确说出单元格的名称。2、学会在单元格中输入数据。3、学会用电子表格软件记录数据,并能对表格中的数据进行修改。4、培养..._重大版小学信息技术走进智慧城堡

随便推点

Pangolin介绍、Pangolin安装_pangolin能不能再macos上安装-程序员宅基地

文章浏览阅读1.9w次,点赞7次,收藏61次。Pangolin介绍英文好的直接看github主仓的介绍:https://github.com/stevenlovegrove/PangolinPangolin是一个轻量、便携的管理OpenGl显示、交互和提取的视频输入的快速开发库。其核心是一个简单的OpenGl视口管理器,它能帮助模块化3D可视化,不增加复杂性,提供一个先进且直接的3D导航处理器。Pangolin也提供一个操作程序的机制,这个机制通过配置文件和UI集成,有一个灵活的实时绘图仪,用于可视图形图像数据。穿山甲的宗旨是在不影响性能的前提_pangolin能不能再macos上安装

Python+opencv实现人脸表情判别,口罩识别_face_recognition 口罩识别-程序员宅基地

文章浏览阅读5.9k次,点赞9次,收藏86次。文章目录一、dlib以及opencv-python库安装dlib安装方法:Cmake安装Boost下载安装dlibopencv-python安装方法二、dlib的68点模型三、Python实现人脸识别&表情判别四、参考文章一、dlib以及opencv-python库安装介于我使用的是jupyter notebook,所以在安装dlib和opencv-python时是在这个命令行安装的dlib安装方法:1.若可以,直接使用上图所示命令行输入以下命令:pip install cmakep_face_recognition 口罩识别

【Educoder作业】C&C++指针实训-程序员宅基地

文章浏览阅读3k次,点赞12次,收藏28次。不是很熟练,之前从来没用过,讲解不到位恕罪。_c&c++指针实训

在qt窗体里面显示html_如何将html文件显示到qtdesigner里-程序员宅基地

文章浏览阅读1.2w次,点赞4次,收藏31次。1)首先新建一个qt工程。在pro文件里面添加 webkitwidgets 和 network模块QT += core gui webkitwidgets networkgreaterThan(QT_MAJOR_VERSION, 4): QT += widgetsTARGET = html1TEMPLATE = appSOURCES += main.cpp\ _如何将html文件显示到qtdesigner里

WordPress缓存插件Cache Enabler使用教程-程序员宅基地

文章浏览阅读458次。Cache Enabler是适用于WordPress的轻量级缓存插件,它通过生成静态HTML文件来使您的网站更快,并且它是最早使用WebP支持的缓存插件之一。它是由KeyCDN背后的公司创建的,该内容交付网络服务可与WordPress一起使用。该插件设计轻巧,安装时间最短。剩余内容访问博客:WordPress缓存插件Cache Enabler使用教程..._cache enabler

eayui的风琴标题字体大小,改变easyui-accordion标题字体大小_easy怎么设置标题字体大小-程序员宅基地

文章浏览阅读500次。由于eayui的面板标题修改不支持直接修改,例: 标题大小修改 显然这是不行的。_easy怎么设置标题字体大小

推荐文章

热门文章

相关标签