`

Leetcode - Fraction to Recurring Decimal

 
阅读更多
[分析]
处理int型整数运算时,为避免溢出,省事的做法就是内部转为long类型处理,不然极可能在极值case上栽跟头,比如int a = Integer.MIN_VALUE, int b = -1 和 long a = Integer.MIN_VALUE, long b = -1, 两者a / b的结果是不一样的,前者会发生溢出,
在比如Math.abs(Integer.MIN_VALUE) 结果竟然是Integer_MIN_VALUE,这都是各种Wrong Answer耐心地告诉我的。
实现2参考https://leetcode.com/discuss/23079/my-clean-java-solution, 有条理的一步步构造出答案,觉得这种方式实现更不容易出错些,自己的实现1就犯过在判断符号后忘记讲intPart取绝对值导致的错误。

public class Solution {
    // especially take care of case like -2147483648 / -1
    // Method 2
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0)
            return "Error: divide zero.";
        if (numerator == 0)
            return "0";
        StringBuilder res = new StringBuilder();
        res.append((numerator > 0 ^ denominator > 0) ? "-" : "");
        long a = Math.abs((long)numerator);
        long b = Math.abs((long)denominator);
        //integer part
        res.append(a / b);
        long mod = a % b;
        if (mod == 0)
            return res.toString();
        //fraction part
        res.append(".");
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        map.put(mod, res.length());
        while (mod != 0) {
            mod *= 10;
            res.append(mod / b);
            mod %= b;
            if (map.containsKey(mod)) {
                res.insert(map.get(mod), "(");
                res.append(")");
                break;
            } else {
                map.put(mod, res.length());
            }
        } 
        return res.toString();
    }
    // Method 1
    public String fractionToDecimal1(int numerator, int denominator) {
        long a = numerator, b = denominator; // Attention! 
        if (b == 0) return "Divide zero exception.";
        long intPart = a / b;
        long mod = a % b;
        if (mod == 0) 
            return String.valueOf(intPart);
            
        boolean isNeg = (a > 0 ^ b > 0) ? true : false;
        intPart = Math.abs(intPart);
        mod = Math.abs(mod);
        b = Math.abs(b);
        
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        StringBuilder fractionPart = new StringBuilder();
        int i = 0;
        while (mod != 0 && !map.containsKey(mod)) {
            map.put(mod, i++);
            mod *= 10;
            fractionPart.append(mod / b);
            mod = mod % b;
        }
        if (mod == 0) {
            return (isNeg ? "-" : "") + intPart + "." + fractionPart.toString();
        } else { 
            int startRepeat = map.get(mod);
            return (isNeg ? "-" : "") + intPart + "."
                + fractionPart.substring(0, startRepeat)  
                + "(" + fractionPart.substring(startRepeat, fractionPart.length()) + ")";
        }
    }
}
分享到:
评论

相关推荐

    python-leetcode题解之166-Fraction-to-Recurring-Decimal.py

    LeetCode题号166的题目要求参与者编写一个函数,将两个整数表示的分数转换为小数。这一过程通常涉及到基本的数学运算,但在涉及到循环小数的情况时会更加复杂。 首先,我们需要明确的是,在任何两个整数a和b之间(b...

    js-leetcode题解之166-fraction-to-recurring-decimal.js

    本题是leetCode平台中的一道编程挑战题目,编号为166。在该题目中,需要使用JavaScript语言来编写一个函数,该函数接收两个整数参数,分别代表分数的分子和分母,并返回一个字符串,该字符串以小数形式表示输入的...

    字符串整数的余数leetcode-fraction-to-recurring-decimal:分数到循环小数

    字符串可能的余数分数到循环小数 给定两个表示分数分子和分母的整数,以字符串格式返回分数。 如果小数部分是重复的,请将重复部分括在括号中。 Example 1: Input: numerator = ...分子和分母都是负数,应该得到正分

    dna匹配leetcode-leetcode:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring Without Repeating Characters 哈希表 双指针 滑动窗口 Substring ...Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    LeetCode最全代码

    462 | [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) | [C++](./C++/minimum-moves-to-equal-array-elements-ii.cpp) [Python](./Python/...

    leetcode常见的100热点算法题

    如"Fraction to Recurring Decimal"(分数到小数)和"Job Scheduling"(作业调度)就可能涉及贪心策略。 5. **二叉树与图**:二叉树题目如"Binary Tree Inorder Traversal"(二叉树的中序遍历)和"Lowest Common ...

Global site tag (gtag.js) - Google Analytics