最简分数

(https://leetcode-cn.com/problems/simplified-fractions/description/)

给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。

示例

示例 1：

输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
ABNF

示例 2：

输入：n = 3
输出：["1/2","1/3","2/3"]
Excel

示例 3：

输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
Excel

示例 4：

输入：n = 1
输出：[]
ABNF

提示

  • 1 <= n <= 100

思路

从2到n遍历，获取每次遍历时由 i 作为分母的最简分式，分子小于i，大于0，并且与分母i的最大公约数是1

源码

function simplifiedFractions(n: number): string[] {
    let res: Array<string> = [];
    for (let i = 2; i <= n; i++) {
        res = getNums(i, res);
    }
    return res;
};
/**
 * 获取小于n,大于0，且与n的最大公约数为1的数值与n组成的分式
 * @param n 
 */
function getNums(n: number, res: Array<string>): string[] {
    res.push(`1/${n}`)
    let buffer: Array<number> = [];//存放最大公约数不为1的数
    for (let i = 2; i < n; i++) {
        if (buffer.includes(i)) continue;
        if (n % i !== 0) {
            res.push(`${i}/${n}`);
        } else {
            for (let j = 1; i * j < n; j++) {
                buffer.push(i * j)
            }
        }
    }
    return res;
}
TypeScript

结果

image-20220210110657161