C++实现LeetCode(166.分数转循环小数)

[LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

这道题还是比较有意思的，开始还担心万一结果是无限不循环小数怎么办，百度之后才发现原来可以写成分数的都是有理数，而有理数要么是有限的，要么是无限循环小数，无限不循环的叫无理数，例如圆周率pi或自然数e等，小学数学没学好，汗！由于还存在正负情况，处理方式是按正数处理，符号最后在判断，那么我们需要把除数和被除数取绝对值，那么问题就来了：由于整型数INT的取值范围是-2147483648～2147483647，而对-2147483648取绝对值就会超出范围，所以我们需要先转为long long型再取绝对值。那么怎么样找循环呢，肯定是再得到一个数字后要看看之前有没有出现这个数。为了节省搜索时间，我们采用哈希表来存数每个小数位上的数字。还有一个小技巧，由于我们要算出小数每一位，采取的方法是每次把余数乘10，再除以除数，得到的商即为小数的下一位数字。等到新算出来的数字在之前出现过，则在循环开始出加左括号，结束处加右括号。代码如下：

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        int s1 = numerator >= 0 ? 1 : -1;
        int s2 = denominator >= 0 ? 1 : -1;
        long long num = abs( (long long)numerator );
        long long den = abs( (long long)denominator );
        long long out = num / den;
        long long rem = num % den;
        unordered_map<long long, int> m;
        string res = to_string(out);
        if (s1 * s2 == -1 && (out > 0 || rem > 0)) res = "-" + res;
        if (rem == 0) return res;
        res += ".";
        string s = "";
        int pos = 0;
        while (rem != 0) {
            if (m.find(rem) != m.end()) {
                s.insert(m[rem], "(");
                s += ")";
                return res + s;
            }
            m[rem] = pos;
            s += to_string((rem * 10) / den);
            rem = (rem * 10) % den;
            ++pos;
        }
        return res + s;
    }
};
赞 (0)

相关推荐

  • C++实现LeetCode165.版本比较)

    [LeetCode] 165.Compare Version Numbers 版本比较 Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 <version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain onl

  • C++实现LeetCode(904.水果装入果篮)

    [LeetCode] 904. Fruit Into Baskets 水果装入果篮 In a row of trees, the `i`-th tree produces fruit with type `tree[i]`. You start at any tree of your choice, then repeatedly perform the following steps: Add one piece of fruit from this tree to your baskets.

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • C++实现LeetCode(228.总结区间)

    [LeetCode] 228.Summary Ranges 总结区间 Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input:  [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: 0,1,2 form a continuous ran

  • C++实现LeetCode(162.求数组的局部峰值)

    [LeetCode] 162.Find Peak Element 求数组的局部峰值 A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that c

  • C++实现LeetCode(161.一个编辑距离)

    [LeetCode] 161. One Edit Distance 一个编辑距离 Given two strings s and t, determine if they are both one edit distance apart. Note:  There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s 

  • C++实现LeetCode(163.缺失区间)

    [LeetCode] 163. Missing Ranges 缺失区间 Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges. Example: Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99, Output: ["2&q

  • C++实现LeetCode(164.求最大间距)

    [LeetCode] 164. Maximum Gap 求最大间距 Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sor

  • C++实现LeetCode(166.分数转循环小数)

    [LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数 Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Fo

  • SQL实现LeetCode(178.分数排行)

    [LeetCode] 178.Rank Scores 分数排行 Write a SQL query to rank scores. If there is a tie between two scores, both should have the same ranking. Note that after a tie, the next ranking number should be the next consecutive integer value. In other words, th

  • C++实现LeetCode(149.共线点个数)

    C++实现LeetCode(149.共线点个数)

    [LeetCode] 149. Max Points on a Line 共线点个数 Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example 1: Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | |        o |     o |  o   +------------->

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • Java使用LinkedHashMap进行分数排序

    分数排序的特殊问题 在java中实现排序远比C/C++简单,我们只要让集合中元素对应的类实现Comparable接口,然后调用Collections.sort();方法即可. 这种方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在现实中是没有意义的. 典型例子就是学生成绩统计的问题,例如高考中,满分是150,成千上万的学生成绩都在0-150之间,平均一个分数的人数成百上千,这时如果排序还用传统方法明显就浪费了. 进一步思考 成绩既然有固定的分数等级,我们可

  • Java求一个分数数列的前20项之和的实现代码

    题目:有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和. 程序分析:请抓住分子与分母的变化规律. 程序设计: public class test20 { public static void main(String[] args) { float fm = 1f; float fz = 1f; float temp; float sum = 0f; for (int i=0;i<20;i++){ temp = fm; fm = fz; fz =

  • 利用标准库fractions模块让Python支持分数类型的方法详解

    前言 你可能不需要经常处理分数,但当你需要时,Python的Fraction类会给你很大的帮助.本文将给大家详细介绍关于利用标准库fractions模块让Python支持分数类型的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍: fractions模块 fractions模块提供了分数类型的支持. Fraction类 该类是fractions模块的核心,它继承了numbers.Rational类并且实现了该类所有的方法. 构造函数并不复杂: class fractions

  • 如何编写一个小数转换分数的函数？

    Public Function XtoF(str As Currency, Optional fenm As Integer = 32) As String ' 只限于整除分数.  Dim Cfm As Currency  Dim cfmmod As Integer  On Error GoTo Erroreof Cfm = 1 / fenm  XtoF = ""  If str = 0 Then XtoF = "": Exit Function Dim point

  • Python中分数的相关使用教程

    你可能不需要经常处理分数,但当你需要时,Python的Fraction类会给你很大的帮助.在该指南中,我将提供一些有趣的实例,用于展示如何处理分数,突出显示一些很酷的功能. 1 基础 Fraction类在Lib/fractions.py文件中,所以可以这样导入: from fractions import Fraction 有很多种实例化Fraction类的方法. 首先,你可以传入分子和分母: >>> Fraction(1, 2) Fraction(1, 2) 或者利用另一个分数进行实例

随机推荐