力扣166题：分数到小数
在本篇文章中，我们将详细解读力扣第166题“分数到小数”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解，以便于理解。
问题描述
力扣第166题“分数到小数”描述如下：
给定两个整数，分别表示分数的分子
numerator和分母denominator，以字符串形式返回小数。如果小数部分是循环小数，则将循环部分括在括号内。
示例 1:
输入: numerator = 1, denominator = 2 输出: "0.5"
示例 2:
输入: numerator = 2, denominator = 1 输出: "2"
示例 3:
输入: numerator = 2, denominator = 3 输出: "0.(6)"
解题思路
方法一：模拟长除法
- 初步分析：
- 使用长除法模拟计算小数部分，并记录每一步余数的位置来检测循环。
- 使用哈希表存储余数的位置，如果发现重复的余数，则表示循环节开始。
- 步骤：
- 处理分子和分母的符号，计算整数部分。
- 模拟长除法计算小数部分，记录每一步余数的位置。
- 如果发现重复的余数，则将循环部分括在括号内。
代码实现
def fractionToDecimal(numerator, denominator): if numerator == 0: return "0" result = [] if (numerator < 0) ^ (denominator < 0): result.append("-") numerator, denominator = abs(numerator), abs(denominator) result.append(str(numerator // denominator)) remainder = numerator % denominator if remainder == 0: return "".join(result) result.append(".") remainders = {} while remainder != 0: if remainder in remainders: result.insert(remainders[remainder], "(") result.append(")") break remainders[remainder] = len(result) remainder *= 10 result.append(str(remainder // denominator)) remainder %= denominator return "".join(result) # 测试案例 print(fractionToDecimal(1, 2)) # 输出: "0.5" print(fractionToDecimal(2, 1)) # 输出: "2" print(fractionToDecimal(2, 3)) # 输出: "0.(6)"
ASCII图解
假设输入为 numerator = 2 和 denominator = 3，图解如下：
2 ÷ 3 = 0.6666... 步骤： 整数部分: 0 小数部分: 2 * 10 = 20, 20 ÷ 3 = 6, 余数 = 2 2 * 10 = 20, 20 ÷ 3 = 6, 余数 = 2 (循环开始) 结果：0.(6)
方法二：通过字符串操作
- 初步分析：
- 直接通过字符串操作来构建结果字符串。
- 使用哈希表记录每个余数出现的位置，检测循环节。
- 步骤：
- 处理分子和分母的符号，计算整数部分。
- 使用字符串操作计算小数部分，记录每个余数的位置。
- 如果发现重复的余数，则将循环部分括在括号内。
代码实现
def fractionToDecimal(numerator, denominator): if numerator == 0: return "0" sign = "-" if (numerator < 0) ^ (denominator < 0) else "" numerator, denominator = abs(numerator), abs(denominator) integer_part = str(numerator // denominator) remainder = numerator % denominator if remainder == 0: return sign + integer_part result = [sign + integer_part + "."] remainder_map = {} while remainder != 0: if remainder in remainder_map: result.insert(remainder_map[remainder], "(") result.append(")") break remainder_map[remainder] = len(result) remainder *= 10 result.append(str(remainder // denominator)) remainder %= denominator return "".join(result) # 测试案例 print(fractionToDecimal(1, 2)) # 输出: "0.5" print(fractionToDecimal(2, 1)) # 输出: "2" print(fractionToDecimal(2, 3)) # 输出: "0.(6)"
复杂度分析
- 时间复杂度：
- 模拟长除法方法：O(n)，其中 n 是小数部分的长度，主要消耗在余数的检测和计算上。
- 字符串操作方法：O(n)，其中 n 是小数部分的长度，主要消耗在字符串构建和余数检测上。
- 空间复杂度：
- 模拟长除法方法：O(n)，需要额外的哈希表空间来存储余数的位置。
- 字符串操作方法：O(n)，需要额外的哈希表空间来存储余数的位置。
模拟面试问答
问题 1：你能描述一下如何解决这个问题的思路吗？
回答：我们需要将分数转换为小数，并检测是否存在循环小数。可以使用模拟长除法的方法，记录每一步余数的位置来检测循环。如果发现重复的余数，则表示循环节开始，将循环部分括在括号内。另一种方法是通过字符串操作直接构建结果，使用哈希表记录每个余数出现的位置，检测循环节。
问题 2：为什么要使用哈希表记录余数的位置？
回答：使用哈希表记录余数的位置可以有效检测循环小数。当发现重复的余数时，表示开始出现循环节，可以将循环部分括在括号内。这种方法可以快速确定循环节的起始位置和结束位置。
问题 3：你的算法的时间复杂度和空间复杂度是多少？
回答：模拟长除法方法的时间复杂度是 O(n)，空间复杂度是 O(n)，其中 n 是小数部分的长度。字符串操作方法的时间复杂度是 O(n)，空间复杂度是 O(n)。
问题 4：在什么情况下会出现循环小数？
回答：当分子和分母的最大公约数不为1时，且分母有质因数2或5之外的其他质因数时，分数转换为小数会出现循环小数。例如，2/3转换为小数时，会出现循环小数0.(6)。
问题 5：你能解释一下模拟长除法的方法吗？
回答：模拟长除法的方法通过逐步计算小数部分，每一步记录当前的余数位置。如果发现重复的余数，则表示开始出现循环节。将循环部分括在括号内，生成最终结果。
问题 6：如何处理分子或分母为负数的情况？
回答：首先判断分子和分母的符号，通过异或运算确定结果的符号。然后将分子和分母转换为正数，继续进行后续计算。最后将符号添加到结果字符串的开头。
问题 7：在代码中如何处理分数的整数部分和小数部分？
回答：首先计算整数部分，将整数部分添加到结果字符串中。然后计算小数部分，通过模拟长除法或字符串操作的方法逐步计算，检测循环节并构建最终结果。
问题 8：你能举例说明在面试中如何回答优化问题吗？
回答：在面试中，如果面试官问到如何优化算法，我会首先分析当前算法的瓶颈，如时间复杂度和空间复杂度，然后提出优化方案。例如，对于分数到小数问题，我会提到使用哈希表记录余数的位置，以快速检测循环节，并解释其原理和优势，最后提供代码实现和复杂度分析。
问题 9：如何验证代码的正确性？
回答：通过多个测试案例验证代码的正确性，包括正常情况和边界情况。例如，测试分数的整数部分和小数部分、前导零情况、循环小数情况等，确保代码在各种情况下都能正确运行。
问题 10：你能解释一下分数到小数转换的重要性吗？
回答：分数到小数的转换在数学计算、科学研究和工程应用中非常重要。例如，精确表示和计算分数值，确保计算结果的准确性。分数到小数的转换还用于金融和统计分析中，帮助人们更直观地理解和比较数值大小。
总结
本文详细解读了力扣第166题“分数到小数”，通过模拟长除法和字符串操作两种方法，高效地解决了这一问题，并提供了详细的ASCII图解和模拟面试问答。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
欢迎关注微信公众号 数据分析螺丝钉
