X

LEETCODE 1447. Simplified Fractions 解题思路分析

题目大意:

最简分数

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1447

解题思路分析:

  1. 最简分数分母的取值范围是2到n。
  2. 最简分数分子的取值范围是1到分母-1
  3. 通过两层循环来遍历每一种分子与分母的组合
  4. 判断当前分子和分母是否是最简分数,可以通过判断他们之间的最大公约数,如果最大公约数是1,说明当前是最简分数,将当前分数加入到返回结果。
  5. 判断最大公约数的方法可参照文章:LEETCODE常用小知识点总结(不断更新)中【求最大公约数】章节。

实现代码:

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;
}
// 求最大公约数
int gcd(int a, int b) {
    if(a > b) return gcd(b, a);
    if (a == 0) return b;
    return gcd(b % a, a);
}

本题解法执行时间为35ms。

Runtime: 35 ms, faster than 68.36% of Java online submissions for Simplified Fractions.

Memory Usage: 89.6 MB, less than 100.00% of Java online submissions for Simplified Fractions.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1447-simplified-fractions-解题思路分析/
Categories: leetcode
kwantong: