1447题-最简分数

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

下面是题目：

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

这是我一开始的思路：

    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

提交了一下，结果如下：

#LeetCode #TypeScript

上次更新: 2020/10/28, 07:52:19