LeetCode 题解工作台
最简分数
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。 示例 1： 输入： n = 2 输出： ["1/2"] 解释： "1/2" 是唯一一个分母小于等于 2 的最简分数。 示例 2： 输入： n = 3 输出： …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数学·string
答案摘要
我们可以枚举分子 和分母 ，其中 $1 \leq i < j \leq n$，并判断 和 的最大公约数是否为 ，如果是则 是一个最简分数。 时间复杂度 $O(n^2 \times \log n)$，空间复杂度 $O(\log n)$。其中 是给定的参数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给你一个整数 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
解题思路
方法一：枚举分子分母
我们可以枚举分子 和分母 ，其中 ，并判断 和 的最大公约数是否为 ，如果是则 是一个最简分数。
时间复杂度 ，空间复杂度 。其中 是给定的参数。
class Solution:
def simplifiedFractions(self, n: int) -> List[str]:
return [
f'{i}/{j}'
for i in range(1, n)
for j in range(i + 1, n + 1)
if gcd(i, j) == 1
]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of fractions generated, which is approximately O(n^2) due to the nested loops. For each fraction, checking the GCD takes constant time, and space complexity is also O(n^2) to store the fractions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of GCD and its application to fraction simplification
- question_mark
Ability to work with loops and basic string formatting
- question_mark
Familiarity with time and space complexity analysis in mathematical problems
常见陷阱
外企场景- error
Forgetting to check the GCD of the numerator and denominator to ensure the fraction is simplified
- error
Generating fractions in the wrong order or including fractions like '2/4' that aren't simplified
- error
Not handling edge cases, such as when n is 1 (which would not result in any simplified fractions)
进阶变体
外企场景- arrow_right_alt
Modify the problem to return fractions in ascending order by value
- arrow_right_alt
Return only fractions where the numerator is prime
- arrow_right_alt
Optimize the solution by using a sieve approach to identify valid fractions