C/C++教程

LeetCode 0166 Fraction to Recurring Decimal

本文主要是介绍LeetCode 0166 Fraction to Recurring Decimal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题传送门

1. 题目描述

2. Solution 1

1、思路分析
由于给定的分子和分母的取值范围都是Java int的 4Byte,为了防止计算过程中溢出,需要将分子和分母转换成long类型。
将分数转成整数或小数,做法是计算分子和分母相除的结果。可能结果有三种:整数、有限小数、无限循环小数。
如果分子可以被分母整除,则结果是整数,将分子除以分母的商以字符串的形式返回即可。
如果分子不能被分母整除,则结果是有限小数或无限循环小数,需要通过模拟长除法的方式计算结果。为了方便处理,首先根据分子和分母的正负决定结果的符号(此时,分子分母均不为0),然后将分子和分母都取绝对值,计算长除法。计算长除法时,首先计算结果的整数部分,将以下部分依次拼接到结果中: 1. 如果结果是负数则将负号拼接到结果中,如果结果是正数则跳过这一步;2. 将整数部分拼接到结果中;3. 将小数点拼接到结果中。
完成上述拼接之后,根据余数计算小数部分。
计算小数部分时,每次将余数乘以 10,然后计算小数的下一位数字,并得到新的余数。重复上述操作直到余数变成 0 或者找到循环节。如果余数变成0,则结果是有限循环小数,将小数部分拼接到结果中;如果找到循环节,则找到循环节的开始位置和结束位置并加上括号,然后将小数部分拼接到结果中。
如何判断是否找到循环节?注意到对于相同的余数,计算得到的小数的下一位数字一定是相同的,因此如果计算过程中发现某一位的余数在之前已经出现过,则为找到循环节。为了记录每个余数是否已经出现过,需要使用哈希表存储每个余数在小数部分第一次出现的下标。

2、代码实现

package Q0199.Q0166FractiontoRecurringDecimal;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";     // zero numerator
        StringBuilder result = new StringBuilder();
        if (numerator > 0 ^ denominator > 0) result.append("-");    // determine the sign
        long n = Math.abs((long) numerator), d = Math.abs((long) denominator);    // remove sign of operands
        result.append(n / d);       // append integral part
        if (n % d == 0) return result.toString();   // in case no fractional part
        result.append(".");

        Map<Long, Integer> map = new HashMap<>();
        // simulate the division process
        for (long r = n % d; r != 0; r %= d) {
            // meet a known remainder
            // so we reach the end of the repeating part
            if (map.containsKey(r)) {
                int idx = map.get(r);
                return result.substring(0, idx) + "(" + result.substring(idx) + ")";
            } else {
                // the remainder is first seen
                // remember the current position for it
                map.put(r, result.length());
            }
            r *= 10;
            // append the quotient digit
            result.append(r / d);
        }
        return result.toString();
    }
}

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)

这篇关于LeetCode 0166 Fraction to Recurring Decimal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!