class Solution {
public:
vector<string> simplifiedFractions(int n) {
}
};
1447. 最简分数
给你一个整数 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原站题解
javascript 解法, 执行用时: 104 ms, 内存消耗: 47.7 MB, 提交时间: 2022-11-26 17:50:12
/**
* @param {number} n
* @return {string[]}
*/
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);
}
golang 解法, 执行用时: 40 ms, 内存消耗: 6.9 MB, 提交时间: 2022-11-26 17:49:51
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
}
python3 解法, 执行用时: 68 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-26 17:49:35
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]