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
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

// @Title: 分数到小数 (Fraction to Recurring Decimal)
// @Author: 15816537946@163.com
// @Date: 2019-09-03 18:26:11
// @Runtime: 0 ms
// @Memory: 2.8 MB
/*
 * @lc app=leetcode.cn id=166 lang=golang
 *
 * [166] 分数到小数
 *
 * https://leetcode-cn.com/problems/fraction-to-recurring-decimal/description/
 *
 * algorithms
 * Medium (24.58%)
 * Likes:    60
 * Dislikes: 0
 * Total Accepted:    4.5K
 * Total Submissions: 18.4K
 * Testcase Example:  '1\n2'
 *
 * 给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
 * 
 * 如果小数部分为循环小数，则将循环的部分括在括号内。
 * 
 * 示例 1:
 * 
 * 输入: numerator = 1, denominator = 2
 * 输出: "0.5"
 * 
 * 
 * 示例 2:
 * 
 * 输入: numerator = 2, denominator = 1
 * 输出: "2"
 * 
 * 示例 3:
 * 
 * 输入: numerator = 2, denominator = 3
 * 输出: "0.(6)"
 * 
 * 
 */
func fractionToDecimal(numerator int, denominator int) string {
	// 处理0
	if numerator == 0 {
		return "0"
	}

	// 符号处理
	sign := 1
	if numerator < 0 {
		numerator = -numerator
		sign = -sign
	}
	if denominator < 0 {
		denominator = -denominator
		sign = - sign
	}

	// 整数处理
	intpart := 0
	if numerator > denominator {
		intpart = numerator/denominator
	}
	numerator %= denominator

	// 小数部分
	floatpart := make([]int,0)
	remainmap := make(map[int]int)
	idx := -1
	for numerator > 0 {
		if _, ok := remainmap[numerator];ok {
			idx = remainmap[numerator]
			break
		}

		// 记录当前余数
		remainmap[numerator] = len(floatpart)

		// 除法计算过程
		numerator = numerator * 10
		f := numerator / denominator
		floatpart = append(floatpart, f)
		numerator = numerator % denominator
	}

	// 计算结果
	s := ""
	if sign < 0 {
		s += "-"
	}
	s += fmt.Sprintf("%d", intpart)
	if len(floatpart) > 0 {
		s += "."
		for i := range floatpart {
			if idx >= 0 && i == idx {
				s+= "("
			}
			s += fmt.Sprintf("%d", floatpart[i])
		}
		if idx >= 0 {
			s += ")"
		}
	}

	return s
}