Leetcode/166.cpp at master · JarvisZhang/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//
//  166.cpp
//  LeetCode
//
//  Created by 张佐玮 on 15/8/14.
//  Copyright (c) 2015年 JarvisZhang. All rights reserved.
//
//  Title: Fraction to Recurring Decimal
//

#include <iostream>
#include <sstream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (!denominator) {
            return "";
        }
        if (!numerator) {
            return "0";
        }
        stringstream integer, decimal;
        long dividend = numerator, divisor = denominator;
        bool positive = true;
        if (dividend < 0) {
            dividend = -dividend;
            positive = !positive;
        }
        if (denominator < 0) {
            divisor = -divisor;
            positive = !positive;
        }
        if (!positive ) {
            integer << "-";
        }
        integer << (dividend / divisor);
        dividend %= divisor;
        if (dividend) {
            integer << ".";
        }
        unordered_map<long, long> repeat;
        int loc = 0;
        while (dividend) {
            if (repeat.find(dividend) != repeat.end()) {
                return integer.str() + decimal.str().substr(0, repeat[dividend]) + "(" + decimal.str().substr(repeat[dividend]) + ")";
            }
            else {
                repeat[dividend] = loc++;
                dividend *= 10;
                decimal << (dividend / divisor);
                dividend %= divisor;
            }
        }
        return integer.str() + decimal.str();
    }
};

class Test {
public:
    void sample() {
        int n = -1, d = -2147483648;
        Solution solution;
        cout << solution.fractionToDecimal(n, d);
    }
};