题目大意：
最简分数
给你一个整数 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1447
解题思路分析：
- 最简分数分母的取值范围是2到n。
- 最简分数分子的取值范围是1到分母-1
- 通过两层循环来遍历每一种分子与分母的组合
- 判断当前分子和分母是否是最简分数，可以通过判断他们之间的最大公约数，如果最大公约数是1，说明当前是最简分数，将当前分数加入到返回结果。
- 判断最大公约数的方法可参照文章：LEETCODE常用小知识点总结（不断更新）中【求最大公约数】章节。
实现代码：
public List<String> simplifiedFractions(int n) {
List<String> res = new ArrayList<>();
for(int i=2;i<=n;i++){ // 分母
for(int j=1;j<i;j++){ // 分子
if(gcd(i,j)==1){
res.add(j+"/"+i);
}
}
}
return res;
}
// 求最大公约数
int gcd(int a, int b) {
if(a > b) return gcd(b, a);
if (a == 0) return b;
return gcd(b % a, a);
} 本题解法执行时间为35ms。
Runtime: 35 ms, faster than 68.36% of Java online submissions for Simplified Fractions.
Memory Usage: 89.6 MB, less than 100.00% of Java online submissions for Simplified Fractions.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1447-simplified-fractions-解题思路分析/