|
给你一个整数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： 提示： 这题让返回小于1的最简分数，我们只需要枚举所有的结果，然后选择分子和分母不能约分的分数，也就是分子和分母的最大公约数是1。所以这题就转化成了求最大公约数问题，求两个数的最大公约数我们可以使用辗转相除法，也就是欧几里得算法，前面我们在讲618，找出数组的最大公约数的时候有过详细的分析，这里就不在重复介绍，来看下代码 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;
}
//求i和j的最大公约数
private int gcd(int i, int j) {
return i % j == 0 ? j : gcd(j, i % j);
}
|
