[Leetcode] Fraction to Recurring Decimal 分数转为循环小数

desdik 发布于2019-08-14 12:36 / 1334人阅读

摘要：最新解法及思路哈希表法复杂度时间空间思路整数部分很好处理，只要注意正负号的区分就行了，但是如何处理小数部分呢。这里我们可以用一个哈希表记录每次的余数，如果余数出现重复的时候，说明就产生循环了。

Fraction to Recurring Decimal 最新解法及思路：https://yanjia.me/zh/2018/11/...

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)".

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

整数部分很好处理，只要注意正负号的区分就行了，但是如何处理小数部分呢。如果只是简单的除法，那我们每次把余数乘以10，再除以被除数就可以得到当前位的小数了，得到新的余数，直到余数为0。难点在于，对于无尽循环小数，我们一直这么做永远也不能让余数变为0。这里我们可以用一个哈希表记录每次的余数，如果余数出现重复的时候，说明就产生循环了。为了能找出小数中循环的部分，我们在用哈希表时，还要把每个余数对应的小数位记录下来，这样子我们一旦遇到重复，就知道是从哪里开始循环的。

注意

如果输入的被除数很大，那么余数乘以10有可能溢出，所以我们用long来保存numerator和denominator。

代码

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long num = numerator;
        long den = denominator;
        if(num == 0 || den == 0){
            return "0";
        }
        // 判断结果正负号
        boolean negative = (num > 0 && den < 0) || (num < 0 && den > 0);
        num = Math.abs(num);
        den = Math.abs(den);
        // 得到整数部分
        String integ = (negative ? "-" : "") + String.valueOf(num / den);
        // 如果存在小数部分
        if(num % den != 0){
            num = num % den;
            HashMap map = new HashMap();
            int pos = 0;
            map.put(num, pos);
            StringBuilder frac = new StringBuilder();
            // 计算小数部分
            while(num != 0){
                // 先把算出的小数加上，再判断余数是否重复，如果余数重复的话，小数会从下一个开始重复
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果该余数之前出现过，说明有循环，上次出现的位置到当前位置就是循环的部分
                if(map.containsKey(num)){
                    // 将非循环部分和循环部分分开
                    String pre = frac.substring(0, map.get(num));
                    String loop = frac.substring(map.get(num));
                    // 返回有循环的结果
                    return integ + "." + pre + "(" + loop + ")";
                }
                pos++;
                // 记录下当前余数和他对应小数的位置
                map.put(num, pos);
            }
            // 返回无循环有小数的结果
            return integ + "." + frac.toString();
        }
        // 返回无小数的结果
        return integ;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64581.html

166. Fraction to Recurring Decimal

摘要：题目解答看的代码如下判断正负性加入整数部分加入小数部分记录下已经出现过的当有重复的时候，即从前一个开始到当前用包含进去题目：Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractiona...

Fundebug 2019-08-14 14:12 评论0 收藏0
[Learning Python] Chapter 5 Numeric Types

摘要：，可以用十进制十六进制八进制二进制来表示。由实数虚数组成。，在中，八进制可以以开头，但是在中，不能以开头，一定要以或者开头，位的运算表示位向左移动表示位向右移动表示或运算表示运算表示异或运算两者不同为，相同为可以用方法计算二进制数有多少位。 1, 在Python 2.x 中。Python的integer，有两种类型，normal和long。Normal通常是32位的。Long表示无限精...

yuxue 2019-07-25 11:16 评论0 收藏0
JS数值

摘要：由于浮点数不是精确的值，所以涉及小数的比较和运算要特别小心。根据标准，位浮点数的指数部分的长度是个二进制位，意味着指数部分的最大值是的次方减。也就是说，位浮点数的指数部分的值最大为。一前言这篇文章主要解决以下三个问题：问题1:浮点数计算精确度的问题 0.1 + 0.2; //0.30000000000000004 0.1 + 0.2 === 0.3; // ...

williamwen1986 2019-08-22 16:47 评论0 收藏0
[HackerRank] Plus Minus

Problem Given an array of integers, calculate which fraction of its elements are positive, which fraction of its elements are negative, and which fraction of its elements are zeroes, respectively. Pri...

leeon 2019-08-14 15:47 评论0 收藏0
一个有趣的算法问题：如何定义一个分数类

摘要：一个来自于程序设计的经典问题。注意事项负数问题。和上一点是一样的问题，要确定方式是属于具体的对象，还是属于一个类。一个来自于C++程序设计的经典问题。如何定义一个分数类，实现分数的约分化简，分数之间的加法、减法、乘法、除法四则运算？ 1.初见刚看到这道题的时候，第一感觉是挺简单的啊，就是基本的面向对象，定义对应的加减乘除类就可以了啊，然而到了实现的时候才发现许多问题是说起来容易做起...

BearyChat 2019-07-01 12:15 评论0 收藏0