给你一个整数 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
**输出：** []
提示：
方法一：数学
由于要保证分数在 (0,1) 范围内，我们可以枚举分母 denominator}\in [2,n] 和分子 numerator}\in [1,\textit{denominator})，若分子分母的最大公约数为 1，则我们找到了一个最简分数。
[sol1-Python3]1
2
3
| class Solution:
def simplifiedFractions(self, n: int) -> List[str]:
return [f"{numerator}/{denominator}" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<string> simplifiedFractions(int n) {
vector<string> ans;
for (int denominator = 2; denominator <= n; ++denominator) {
for (int numerator = 1; numerator < denominator; ++numerator) {
if (__gcd(numerator, denominator) == 1) {
ans.emplace_back(to_string(numerator) + "/" + to_string(denominator));
}
}
}
return ans;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<String> simplifiedFractions(int n) {
List<String> ans = new ArrayList<String>();
for (int denominator = 2; denominator <= n; ++denominator) {
for (int numerator = 1; numerator < denominator; ++numerator) {
if (gcd(numerator, denominator) == 1) {
ans.add(numerator + "/" + denominator);
}
}
}
return ans;
}
public int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public IList<string> SimplifiedFractions(int n) {
IList<string> ans = new List<string>();
for (int denominator = 2; denominator <= n; ++denominator) {
for (int numerator = 1; numerator < denominator; ++numerator) {
if (GCD(numerator, denominator) == 1) {
ans.Add(numerator + "/" + denominator);
}
}
}
return ans;
}
public int GCD(int a, int b) {
return b != 0 ? GCD(b, a % b) : a;
}
}
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func simplifiedFractions(n int) (ans []string) {
for denominator := 2; denominator <= n; denominator++ {
for numerator := 1; numerator < denominator; numerator++ {
if gcd(numerator, denominator) == 1 {
ans = append(ans, strconv.Itoa(numerator)+"/"+strconv.Itoa(denominator))
}
}
}
return
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #define MAX_FRACTION_LEN 10
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
char ** simplifiedFractions(int n, int* returnSize) {
char ** ans = (char **)malloc(sizeof(char *) * n * (n - 1) / 2 );
int pos = 0;
for (int denominator = 2; denominator <= n; denominator++) {
for (int numerator = 1; numerator < denominator; numerator++) {
if (gcd(numerator, denominator) == 1) {
ans[pos] = (char *)malloc(sizeof(char) * MAX_FRACTION_LEN);
snprintf(ans[pos++], MAX_FRACTION_LEN, "%d%c%d", numerator, '/', denominator);
}
}
}
*returnSize = pos;
return ans;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var simplifiedFractions = function(n) {
const ans = [];
for (let denominator = 2; denominator <= n; ++denominator) {
for (let numerator = 1; numerator < denominator; ++numerator) {
if (gcd(numerator, denominator) == 1) {
ans.push(numerator + "/" + denominator);
}
}
}
return ans;
};
const gcd = (a, b) => {
if (b === 0) {
return a;
}
return gcd(b, a % b);
}
|
复杂度分析
