英文原文
Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.
Example 1:
Input: n = 2 Output: ["1/2"] Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:
Input: n = 3 Output: ["1/2","1/3","2/3"]
Example 3:
Input: n = 4 Output: ["1/2","1/3","1/4","2/3","3/4"] Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
Example 4:
Input: n = 1 Output: []
Constraints:
1 <= n <= 100
中文题目
给你一个整数 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
通过代码
高赞题解
- 分母b的范围为[ 2 , n ]
- 分子a的范围为[ 1 , b-1 ]
- 分母b和分子a的最大公约数gcd( a , b )为1，则为最简分数
class Solution { public int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } public List<String> simplifiedFractions(int n) { List<String> res = new ArrayList<String>(); for (int b = 2; b <= n; b++) { for (int a = 1; a < b; a++) { if (gcd(a, b) == 1) { res.add(a + "/" + b); } } } return res; } }
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6247 | 10233 | 61.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
