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. Example 1: Input: numerator = 1,denominator = 2 Output: "0.5" Example 2: Input: numerator = 2,denominator = 1 Output: "2" Example 3: Input: numerator = 2,denominator = 3 Output: "0.(6)" ? 解题思路: 这道题目需要明确很多的corner cases: 1. denominator = 0 应该返回什么? 2. 当除得尽时,返回的字符串到最后一个不为零的位置。 3. 当除不尽时,是否循环? 4. 除数与被除数可能为负数,可能为整数。 这里需要注意一点:整数相除的结果都为有理数即有限小数,循环小数等,不会出现无限不循环的情况(这是无理数)。 ? 这里参考了 jackyguo?的解法。 首先考虑特殊情况: 被除数为0,可直接返回“0” 根据输入值的符号来判断最后的符号并且保存。 这里用判断当前余数是否出现过的方式来确认是否出现了循环。 用long long 存储可以防止数字过大可能的溢出。 ? 代码: class Solution { public: string fractionToDecimal(int numerator,int denominator) { if (numerator == 0) return "0"; bool positive = (numerator >= 0 && denominator >= 0) || (numerator < 0 && denominator < 0); long long nu = numerator; long long de = denominator; nu = std::abs(nu); de = std::abs(de); long long integer = nu / de; string decimal = ""; map<long long,int> status_index; long long prev = nu % de; while (1) { // no more remainder if (prev == 0) break; prev *= 10; if (status_index.count(prev)) { // found repeatition int p = status_index[prev]; decimal = decimal.substr(0,p) + "(" + decimal.substr(p) + ")"; break; } status_index[prev] = decimal.length(); long long d = prev / de; assert(d < 10); decimal += (‘0‘ + d); prev = prev % de; } string ret = std::to_string(integer); if (!positive) ret = "-" + ret; if (decimal.length()) ret += "." + decimal; return ret; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |