1447题-最简分数

今天刷题的时候遇到一个最简分数的题。记录一下

下面是题目:

题目

一开始的时候,没有想到使用gcd(欧几里得算法),只是单纯的判断能不能被整除。

这是我一开始的思路:

    function simplifiedFractions(n: number): string[] {
        let data=[];
        for(let i=2;i<n+1;i++){
            for(let j=1;j<i;j++){
                if(i%j!=0||j===1){
                    data.push(`${j}/${i}`);
                }
            }
        }
        return data;
    };

1
2
3
4
5
6
7
8
9
10
11
12

发现这种只能识别 "2/4" "3/6" ,"6/9" "4/6" 这种的就无法识别。

就想到了最大公约数,就手写了一个。

最后的代码就是这样的。

function simplifiedFractions(n: number): string[] {
    let data=[]
    for(let i=2;i<n+1;i++){
        for(let j=1;j<i;j++){
            if(gcd(i,j)===1){
                data.push(`${j}/${i}`)
            }
        }
    }
    return data
};
/**
 * 计算两个非负整数a,b的最大公约数
 * @param a 被除数
 * @param b 除数
 */
function gcd(a:number,b:number):number{
    return a%b===0?b:gcd(b,a%b)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

提交了一下,结果如下:

结果

上次更新: 2020/11/03, 06:57:50
最近更新
01
搜索Excel表里sheet名称
11-03
02
搜狗微信文章的抓取
10-26
03
TypeScript中实现swap
10-21
更多文章>