「每日LeetCode」2022年2月10日

本文最后更新于：2023年3月19日 晚上

1447.最简分数

1447.最简分数

Category Difficulty Likes Dislikes
algorithms Medium (61.30%) 60 -

Tags
Companies
给你一个整数 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

思路

按题意模拟即可

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * @lc app=leetcode.cn id=1447 lang=javascript
 *
 * [1447] 最简分数
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var simplifiedFractions = function (n) {
  const res = [];

  const getNum = (num1, num2) => {
    let num = Math.min(num1, num2);
    while (true) {
      if (num1 % num === 0 && num2 % num === 0) return num;
      num--;
    }
  };

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      const num = getNum(i, j);
      if (i < j && num === 1) {
        res.push(`${i}/${j}`);
      }
    }
  }

  return res;
};
// @lc code=end