题目简介：
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。
示例 1：
1
2
3
| 输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
|
示例 2：
1
2
| 输入：n = 3
输出：["1/2","1/3","2/3"]
|
示例 3：
1
2
3
| 输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
|
示例 4：
提示：
思路：
嵌套循环，若分子与分母互质(公约数只有1的两个整数，即为最简)，则压入vector。
tip:
- 用 辗转相除法 判断两数是否互质。
- 辗转相除法：用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
int gcd(int a,int b){
int temp;
while(1){
temp = a % b;
if(temp == 0)
break;
else{
a = b;
b = temp;
}
}
return b;
}
vector<string> simplifiedFractions(int n) {
vector<string> res;
for(int i = 2; i <= n; i++){
for(int j = 1; j < i; j++){
if(gcd(i, j) == 1){
string temp = to_string(j) + "/" + to_string(i);
res.push_back(temp);
}
}
}
return res;
}
};
|
