链接
题目
给你一个整数
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
思路
- 由于1<=n<=100,分母≤n,数值范围为(0,1),最多约有100*100=1w种情况,所以我们可以用暴力法枚举分母和分子直接求解。
- 首先当n=0,1,时,不存在解。
- 当n≥2时,对于每个n,枚举2-n之间的分母,对于分子,当分子为1时必然成立,然而枚举分子为[2,n-1]之间的数,对分子和分母进行最大公约数判断,如果最大公约数为1,则说明无法约分,将这种情况保存,否则不符合条件。
那么怎么求最大公约数呢?(即怎么判断两个数互质)
欧几里得算法(辗转相除法)
定理:gcd(a,b) = gcd(b,a mod b) // a和b的最大公因数,a和b的大小没影响。
①0和任意自然数的最大公约数就是那个自然数。
②互质指最大公约数等于1的两个自然数。
③1和任意数互质。
判断是否互质代码如下:(如果求最大公因数,输出b即可)
C++ Code
class Solution {
public:
int gcd(int m, int n)
{
while(m>0)
{
int c = n % m;
n = m;
m = c;
}
return n;
}//最大公约数n为1时两数互质
vector<string> simplifiedFractions(int n)
{
vector<string> S;
if(n<=1) return S;
for(int i=2;i<=n;i++) //分母
{
string temp= "1/"+to_string(i);
S.push_back(temp);
for(int j=2;j<i;j++) //分子
{
if(gcd(i,j)==1)
{
temp=to_string(j)+"/"+to_string(i);
S.push_back(temp);
}
}
}
return S;
}
};
C++ Code(简便写法)
class Solution {
public:
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
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) continue ;
ans.push_back(to_string(i) + "/" + to_string(j));
}
}
return ans;
}
};