【Python3/C++/C】LeetCode#34 1447. 最简分数（最大公约数、字符串、malloc） Medium
Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.
Example 1:
Input:
n = 2
Output:
["1/2"]
Explanation:
"1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:
Input:
n = 3
Output:
["1/2","1/3","2/3"]
Example 3:
Input:
n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation:
"2/4" is not a simplified fraction because it can be simplified to "1/2".
Constraints:
1 <= n <= 100
给你一个整数 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
题解
-
分母i的范围是[2, n], 分子j的范围是[1, i - 1]
-
求分子分母的最大公约数：
-
Python的math模块gcd函数运用：gcd(x, y) == 1，最大公约数为1，x / y为最简分数 -
C++的gcd函数运用：__gcd(x, y)函数，用于求x，y的最大公约数；x与y不能是浮点数 -
C：自定义gcd()
AC代码
Python3
class Solution:
def simplifiedFractions(self, n: int) -> List[str]:
ans = []
for i in range(2, n + 1):
for j in range(1, i):
if gcd(j, i) == 1:
ans.append(str(j) + '/' + str(i))
return ans
C++
class Solution {
public:
vector<string> simplifiedFractions(int n)
{
vector<string> res;
for (int i = 2; i <= n; ++i) // 分母i
{
for (int j = 1; j < i; ++j) // 分子j
{
if (__gcd(i, j) == 1)
// __gcd(x, y)函数:用于求x，y的最大公约数；x,y不能是浮点数
{
res.push_back(to_string(j) + "/" + to_string(i));
// push_back:函数将一个新的元素加到vector的最后面，位置为当前最后一个元素的下一个元素
// to_string:将数字常量转换为字符串
}
}
}
return res;
}
};
C
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int gcd(int x, int y)
{
int t;
while (y)
{
t = x % y;
x = y;
y = t;
}
return x;
}
char ** simplifiedFractions(int n, int* returnSize)
{
char ** res = (char **)malloc(sizeof(char *) * n * (n + 1) / 2);
// 开辟空间，最简分数最多只有(1 + n) * n / 2
int pos = 0;
for (int i = 2; i <= n; ++i) // 分母
{
for (int j = 1; j <= i; ++j) // 分子
{
int g = gcd(i, j);
if (g == 1) // 分母和分子的最大公约数为1，则该分数为最简分数
{
res[pos] = (char *)malloc(sizeof(char) * 20);
sprintf(res[pos++], "%d/%d", j, i); // sprintf()：将一个格式化的字符串输出到一个目的字符串中
}
}
}
*returnSize = pos;
return res;
}