LeetCode刷题【1447】最简分数

输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。

输入：n = 3
输出：["1/2","1/3","2/3"]

输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。

输入：n = 1
输出：[]

GCD辗转相除法【欧几里德算法（Euclidean algorithm）】
相关知识链接碾转相除法

这是一个求最大公约数的方法

1. 实现一个gcd(int a, int b)辗转相除方法，判断两个数的最大公约数是否为1
2. 如果为1则表明这两个数互质
3. 剩下的就是枚举从i到n和从i+1到n的分子分母关系了

class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <=n ; j++) {
                if (gcd(i,j)==1){
                    list.add(i+"/"+j);
                }
            }
        }
        return list;
    }

    int gcd(int a, int b){
        if (b==0){
            return a;
        }
        return gcd(b,a%b);
    }
}