题目
思路 暴力
遍历分子和分母,判断最小公因数是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;
}
};