携手创造,一起生长!这是我参加「日新方案 8 月更文挑战」的第22天,点击查看活动详情
前语
咱们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 工作健身教练。)的 Swift 算法题题解收拾为文字版以方便咱们学习与阅览。
LeetCode 算法到现在咱们已经更新到 163 期,咱们会保持更新时刻和进展(周一、周三、周五早上 9:00 发布),每期的内容不多,咱们希望咱们能够在上班路上阅览,长久堆集会有很大提高。
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。假如咱们有建议和定见欢迎在文末留言,咱们会尽力满足咱们的需求。
难度水平:中等
1. 描述
给定两个整数,分别表明分数的分子numerator
和分母 denominator
,以 字符串方式返回小数 。
假如小数部分为循环小数,则将循环的部分括在括号内。
假如存在多个答案,只需返回 恣意一个 。
对于一切给定的输入,确保 答案字符串的长度小于 10^4
。
2. 示例
示例 1
输入:numerator = 1, denominator = 2
输出:"0.5"
示例 2
输入:numerator = 2, denominator = 1
输出:"2"
示例 3
输入:numerator = 4, denominator = 333
输出:"0.(012)"
约束条件:
-2^31 <= numerator, denominator <= 2^31 - 1
denominator != 0
3. 答案
class FractionToRecurringDecimal {
func fractionToDecimal(_ numerator: Int, _ denominator: Int) -> String {
guard numerator != 0 else {
return "0"
}
guard denominator != 0 else {
fatalError("Invalid Denominator")
}
var isPositive = (numerator < 0) == (denominator < 0), numerator = abs(numerator), res = "", numToIndex = [Int: Int](), hasDot = false
let denominator = abs(denominator)
while numerator != 0 {
let (q, r) = numerator.quotientAndRemainder(dividingBy: denominator)
if let numIndex = numToIndex[numerator]{
res.insert("(", at: res.index(res.startIndex, offsetBy: numIndex))
res.append(")")
break
} else {
res += "\(q)"
if !hasDot && r != 0 {
res.append(".")
hasDot = true
} else {
// update numToIndex
numToIndex[numerator] = res.count - 1
}
// update reminder
numerator = r * 10
}
}
return isPositive ? res : "-" + res
}
}
- 首要思想:求商和余数,假如余数存在,则重复。
- 时刻复杂度: O(logn)
- 空间复杂度: O(n)
该算法题解的仓库:LeetCode-Swift
点击前往 LeetCode 练习
关于咱们
咱们是由 Swift 爱好者一起维护,咱们会共享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容,也收拾搜集优秀的学习资料。
后续还会翻译大量资料到咱们公众号,有感爱好的朋友,能够参加咱们。