分数到小数

class Solution {
public:
    string frac2Dec(int n, int m) {
        string result="";
        long long a=n, b=m;
        if (a*b<0) result+="-";
        a=abs(a); b=abs(b);
        
        if (a%b==0) return result+to_string(a/b);
        
        result+=to_string(a/b)+".";
        a=a%b;
        unordered_map<long long, int> map;
        while (a!=0) {
            map[a]=result.size();
            a=a*10;
            result+=to_string(a/b);
            a=a%b;
            if (map.count(a)) {
                return result.substr(0, map[a])+"("+result.substr(map[a])+")";
            }
        }
        return result;
    }
};

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @param m int整型
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4c16ea1e884b48bc90869184f52b9b66?tpId=196&tqId=40441&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：秋越海
    算法：
        1. 获取结果的正负号
        2. 计算整数部分。若恰好整除，直接返回；否则进行步骤3
        3. 计算小数部分
    复杂度：
        时间复杂度：O(1)
        空间复杂度：O(1)
    """

    def frac2Dec(self, n, m):
        # write code here
        sign = 1 if n * m > 0 else -1  # 同号相除，结果为正；异号相除，结果为负

        n, m = abs(n), abs(m)

        i, j = n / m, n % m # i为整数部分，j为小数部分
        intPart = str(i) if sign == 1 else "-" + str(i)
        if j == 0: # 可以整除，直接返回
            return intPart

        d, k = {}, [] # 使用列表k存储小数部分整除结果，使用哈希表k存储分子是否出现过，键：分子j，值为当前计算的小数位
        while j != 0:
            if j not in d: # 分子j未出现过
                d[j] = len(k) # 记录分子j对应的小数位
                j = j * 10
                k.append(str(j // m))
                j = j % m
            else:
                pos = d[j] # 对于已出现的分子j，从哈希表中找出j对应的小数位下标，在其左右两侧分别加入左右括号"(", ")"，饭后退出循环
                k.insert(pos, "(")
                k.append(")")
                break
        return intPart + "." + "".join(k) # 结果为整数部分 + 小数部分

if __name__ == "__main__":
    sol = Solution()

    n, m = 1, 3

    # n, m = 5, 4

    # n, m = 4, -2

    res = sol.frac2Dec(n, m)

    print res