最简分数

2021-03-21

1447. 最简分数

难度中等11收藏分享切换为英文接收动态反馈

给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的最简分数。分数可以以任意顺序返回。

示例 1：

1
2
3

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

示例 2：

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

示例 3：

1
2
3

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

示例 4：

1 2	输入：n = 1 输出：[]

提示：

1 <= n <= 100

最大公约数判断是否可以化简


class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> list=new ArrayList<>();
        // 分子为1的情况
        for(int i=2;i<=n;i++){
            list.add("1/"+i);
        }
		// 遍历分子不为1的情况
        for(int i=2;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(j%i!=0&&gcd(j,i)==1){
                    list.add(i+"/"+j);
                }
            }
        }

        return list;
    }

	// 求最大公约数
    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true