leetcode-每日一题2022.2.10 最简分数

本文主要是介绍leetcode-每日一题2022.2.10 最简分数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

力扣

思路 暴力

遍历分子和分母，判断最小公因数是1的话，就添加进结果中。

求最小公因素的笨蛋代码

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for(int i = 1; i < n; i++){
            for(int j = i+1; j <= n; j++){
                bool flag = true;
                for(int k = 2; k <= i; k++){
                    if(i % k == 0 && j % k ==0){
                        // cout<<i<<' '<<j<<endl;
                        flag = false;
                        break;
                    }
                }
                if(!flag) continue;
                ans.push_back(to_string(i)+'/'+to_string(j));
            }
        }
        return ans;
    }
};

C++内置函数__gcd

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for(int i = 1; i < n; i++){
            for(int j = i+1; j <= n; j++){
                if(__gcd(i,j)==1)
                    ans.push_back(to_string(i)+'/'+to_string(j));
            }
        }
        return ans;
    }
};

欧几里得算法

class Solution {
public:
    int gcd(int a,int b){
        return b == 0 ? a : gcd(b, a % b);
    }
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for(int i = 1; i < n; i++){
            for(int j = i+1; j <= n; j++){
                if(gcd(i,j)==1)
                    ans.push_back(to_string(i)+'/'+to_string(j));
            }
        }
        return ans;
    }
};

这篇关于leetcode-每日一题2022.2.10 最简分数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！