leetcode做题笔记166. 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 104 。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"

思路一：模拟竖式计算

c++解法

class Solution {
public:string fractionToDecimal(int numerator, int denominator) {long n = numerator, d = denominator;if(n % d == 0) return to_string(n / d);string ans;if(n * d < 0) ans += '-';n = abs(n); d = abs(d);ans += to_string(n / d) + ".";n %= d;int len = ans.size();unordered_map<int, int> up;while(n && !up.count(n)){up[n] = len++;n *= 10;ans += to_string(n / d);n %= d;}if(n != 0){int pos = up[n];ans = ans.substr(0, pos) + '(' + ans.substr(pos) + ')';}return ans;}
};

分析：

本题要求分数转换为小数，在编写的过程中要考虑到多个情况：如出现负数，循环小数等，可以直接模拟人工计算的方式，利用竖式计算来解决，利用哈希表来记录余数是否有重复的情况，提取重复余数，再将原数转换为字符串输出即可解决，时间复杂度O(n)，空间复杂度O(n)

总结：

本题考察对除运算的理解，利用竖式计算来计算小数，哈希表来记录重复小数，将重复余数用括号括起来拼接后输出即可解决