题目

给你一个整数 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplified-fractions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

枚举可能出现的分数，需要判断是否可以化简，即分子分母是否互质，如果互质就加入结果。互质即求最大公约数是否为1，使用「辗转相除法」即可。

代码

  1. class Solution {
  2.     public List<String> simplifiedFractions(int n) {
  3.         List<String> ans = new ArrayList<>();
  4.         for (int i = 2; i <= n; i++) {
  5.             for (int j = 1; j < i; j++) {
  6.                 if (gcd(i, j) == 1) {
  7.                     ans.add(j + "/" + i);
  8.                 }
  9.             }
  10.         }
  11.         return ans;
  12.     }
  14.     // 求a和b的最大公约数
  15.     public int gcd (int a, int b) {
  16.         if (a % b == 0) {
  17.             return b;
  18.         }
  19.         return gcd(b, a % b);
  20.     }
  21. }