leetcode 1447. 最简分数

2022-02-10

题目

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

1 < n < 100

示例：
n = 3

输出："1/2" "1/3" "2/3"

思路

暴力思路：O(n^2)搜索每一个分子分母搭配，因为数据量小，是可以通过的
那么如何验证最简分数呢？答案是分子分母的最大公约数为1。求两个数的最大公约数可以用欧几里得算法（辗转相除法）
欧几里得算法：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：

1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

以下给出递归版本的实现

代码

class Solution {
    // 欧几里得算法
    int mygcd(int a, int b){
        if(a%b == 0)    return b;
        return b > a%b ? mygcd(b, a%b) : mygcd(a%b, b);
    }
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for(int i=2;i<=n;++i){
            for(int j=1;j<i;++j){
                if(mygcd(i, j)==1){
                    ans.emplace_back(to_string(j)+"/"+to_string(i));
                }
            }
        }
        return ans;
    }
};