Medium

题目描述

给定一个整数 n，返回所有分母小于等于 n 且在 0 和 1 之间（不包括 0 和 1）的最简分数列表。你可以按任意顺序返回答案。

示例 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"。

约束条件：

  • 1 <= n <= 100

提示：

  • 分数完全简化意味着没有整数可以同时整除分子和分母。
  • 换句话说，最简分数的分子和分母的最大公约数是 1。

解题思路

这道题要求找出所有分母小于等于 n 的最简分数。核心思想是遍历所有可能的分子和分母组合，然后判断是否为最简分数。

解题思路：

  1. 暴力枚举 + GCD判断：遍历所有可能的分子 i 和分母 j，其中 1 ≤ i < j ≤ n，通过计算最大公约数(GCD)来判断分数是否已经是最简形式。如果 gcd(i, j) = 1，则该分数是最简分数。

  2. 优化思路：由于题目约束 n ≤ 100，暴力解法完全可行。对于每个分母 j，遍历所有小于 j 的分子 i，检查 gcd(i, j) 是否等于 1。

算法步骤：

  • 外层循环遍历分母 j，从 2 到 n
  • 内层循环遍历分子 i，从 1 到 j-1
  • 计算 gcd(i, j)，如果等于 1，则将 “i/j” 加入结果
  • 返回所有最简分数

这种方法时间复杂度较低且易于理解实现。由于需要计算GCD，我们可以使用辗转相除法实现。

代码实现

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> result;
        for (int j = 2; j <= n; j++) {
            for (int i = 1; i < j; i++) {
                if (gcd(i, j) == 1) {
                    result.push_back(to_string(i) + "/" + to_string(j));
                }
            }
        }
        return result;
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        result = []
        for j in range(2, n + 1):
            for i in range(1, j):
                if self.gcd(i, j) == 1:
                    result.append(f"{i}/{j}")
        return result
    
    def gcd(self, a, b):
        while b:
            a, b = b, a % b
        return a

public class Solution {
    public IList<string> SimplifiedFractions(int n) {
        List<string> result = new List<string>();
        for (int j = 2; j <= n; j++) {
            for (int i = 1; i < j; i++) {
                if (Gcd(i, j) == 1) {
                    result.Add($"{i}/{j}");
                }
            }
        }
        return result;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

/**
 * @param {number} n
 * @return {string[]}
 */
var simplifiedFractions = function(n) {
    const result = [];
    
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    for (let denominator = 2; denominator <= n; denominator++) {
        for (let numerator = 1; numerator < denominator; numerator++) {
            if (gcd(numerator, denominator) === 1) {
                result.push(`${numerator}/${denominator}`);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² log n)，其中外层循环 O(n)，内层循环 O(n)，GCD计算 O(log n)
空间复杂度O(1)，除了存储结果的空间外，只使用常数额外空间