1447.最简分数

链接：1447.最简分数
难度：Medium
标签：数学、字符串、数论
简介：给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。

题解 1 - cpp

• 编辑时间：2022-02-10
• 执行用时：116ms
• 内存消耗：32.5MB
• 编程语言：cpp
• 解法介绍：判断最大公约数。

class Solution {
   public:
    vector<string> simplifiedFractions(int n) {
        unordered_set<string> s;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int num = gcd(i, j);
                s.insert(to_string(j / num) + "/" + to_string(i / num));
            }
        }
        vector<string> ans;
        for (auto& str : s) ans.push_back(str);
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-02-10
• 执行用时：48ms
• 内存消耗：21.3MB
• 编程语言：cpp
• 解法介绍：判断最大公约数。

class Solution {
   public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (j == 1 || gcd(i, j) == 1)
                    ans.push_back(to_string(j) + "/" + to_string(i));
            }
        }
        return ans;
    }
};

题解 3 - typescript

• 编辑时间：2021-12-11
• 执行用时：104ms
• 内存消耗：44.8MB
• 编程语言：typescript
• 解法介绍：最大公约数为 1。

function gcd(a: number, b: number) {
  return b ? gcd(b, a % b) : a;
}
function simplifiedFractions(n: number): string[] {
  const ans: string[] = [];
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      if (gcd(i, j) === 1) ans.push(`${j}/${i}`);
    }
  }
  return ans;
}