1447. Simplified Fractions-1447. 最简分数

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

Python:

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        result =[]
        for i in range(1, n):
            for j in range(i+1, n+1):
                if gcd(i, j) == 1:
                    result.append(str(i)+'/'+str(j))
        return result

    def gcd(a, b):
        if b == 0:
            return a 
        else:
            return gcd(b, a % b)

Java:

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

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