fraction_to_recurring_decimal

hitzzc · hitzzc · commit c45acabb61ec · 2016-10-15T20:09:19.000+08:00
diff --git a/README.md b/README.md
@@ -143,6 +143,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [162. Find Peak Element](https://github.com/hitzzc/go-leetcode/tree/master/find_peak_element)
 #### [164. Maximum Gap](https://github.com/hitzzc/go-leetcode/tree/master/maximum_gap)
 #### [165. compare version numbers](https://github.com/hitzzc/go-leetcode/tree/master/compare_version_numbers)
+#### [166. Fraction to Recurring Decimal](https://github.com/hitzzc/go-leetcode/tree/master/fraction_to_recurring_decimal)
 
 
 
diff --git a/fraction_to_recurring_decimal/fraction_to_recurring_decimal.go b/fraction_to_recurring_decimal/fraction_to_recurring_decimal.go
@@ -0,0 +1,44 @@
+package fraction_to_recurring_decimal
+
+import (
+	"strconv"
+)
+
+func fractionToDecimal(numerator int, denominator int) string {
+	if numerator == 0 {
+		return "0"
+	}
+	m := []byte("0123456789")
+	var ret string
+	var neg bool
+	if numerator < 0 {
+		numerator *= -1
+		neg = !neg
+	}
+	if denominator < 0 {
+		denominator *= -1
+		neg = !neg
+	}
+	if neg {
+		ret = "-"
+	}
+	ret += strconv.Itoa(numerator / denominator)
+	remainder := numerator % denominator
+	if remainder == 0 {
+		return ret
+	}
+	ret += "."
+	floatBytes := []byte{}
+	indexMap := map[int]int{}
+	for remainder != 0 {
+		if idx, ok := indexMap[remainder]; ok {
+			return ret + string(floatBytes[:idx]) + "(" + string(floatBytes[idx:]) + ")"
+		}
+		indexMap[remainder] = len(floatBytes)
+		remainder *= 10
+		v := m[remainder/denominator]
+		remainder %= denominator
+		floatBytes = append(floatBytes, v)
+	}
+	return ret + string(floatBytes)
+}
