leetcode 46题详解（leetcode1447go最简分数）
leetcode 46题详解（leetcode1447go最简分数）提示：1 <= n <= 100示例 4：输入：n = 1 输出：[]示例 2：输入：n = 3 输出：["1/2" "1/3" "2/3"]示例 3：输入：n = 4 输出：["1/2" "1/3" "1/4" "2/3" "3/4"]解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
题目给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。
分数可以以 任意 顺序返回。
示例 1：输入：n = 2 输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
示例 2：输入：n = 3 输出：["1/2" "1/3" "2/3"]
示例 3：输入：n = 4 输出：["1/2" "1/3" "1/4" "2/3" "3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
示例 4：输入：n = 1 输出：[]
提示：1 <= n <= 100
解题思路分析1、暴力法；时间复杂度O(n^2log(n))，空间复杂度O(n^2)
func simplifiedFractions(n int) []string {
res := make([]string 0)
for i := 2; i <= n; i {
for j := 1; j < i; j {
if gcd(i j) == 1 {
res = append(res fmt.Sprintf("%d/%d" j i))
}
}
}
return res
}
func gcd(a b int) int {
if a%b == 0 {
return b
}
return gcd(b a%b)
}
2、哈希辅助；时间复杂度O(n^3)，空间复杂度O(n^2)
func simplifiedFractions(n int) []string {
res := make([]string 0)
m := make(map[string]bool)
for i := 2; i <= n; i {
for j := 1; j < i; j {
str := fmt.Sprintf("%d/%d" j i)
if _ ok := m[str]; ok{
continue
}
res = append(res str)
for k := 1; i *k <= n; k {
m[fmt.Sprintf("%d/%d" j*k i*k)] = true
}
}
}
return res
}总结
Medium题目，可以求最大公约数是1的2个数，也可以使用哈希进行辅助判断
