每日一题:LeetCode:1447.最简分数

---

• 每日一题：LeetCode：1447.最简分数
  • 时间：2022-02-10
  • 力扣难度：Medium
  • 个人难度：Medium
  • 数据结构：哈希表
  • 算法：最大公约数

---

2022-02-10：LeetCode：1447.最简分数

1. 题目描述

• 题目：原题链接

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

• 输入输出规范

  • 输入：整数 n
  • 输出：最简分数构成的List

• 输入输出示例

  • 输入：n = 4
  • 输出：[“1/2”,”1/3”,”1/4”,”2/3”,”3/4”]

---

2. 方法一：哈希表

• 思路

  • 本题的数据规模较小，可以枚举每一个分母和分子，但是由于最后要求的是最简分数，所以需要去重
  • 可以使用一个Set来进行去重，Set中存储Double类型的数值，表示分母与分子的比值，当比值不重复时，将当前枚举到的结果存入最终的List中，重复时不进行操作

• 题解

  public List<String> simplifiedFractions1(int n) {
      List<String> list = new ArrayList<>();
      Set<Double> set = new HashSet<>();
      if(n < 2) return list;
      StringBuilder sb;
      for(int down = 2; down <= n; down++) {
          for(int up = 1; up < down; up++) {
              sb = new StringBuilder();
              sb.append(up).append("/").append(down);
              if(set.contains((double)down / up)) continue;
              set.add((double)down / up);
              list.add(sb.toString());
          }
      }
      // Collections.sort(list);
      return list;
  }

• 复杂度分析：n 是数组的大小

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

---

3. 方法二：辗转相除法

• 思路

  • 使用Set的解题方式一方面需要$O(n^2)$的空间复杂度，另一方面可能涉及到大量的扩容，导致效率不高
  • 我们可以通过数学中*最大公约数 *(即gcd函数)，来判断当前分数是否重复，即如果一个分数不是最简分数，可以约分，那么其分母与分子的最大公约数不为1，而最简分数时最大公约数为1
  • 所以，在枚举分母与分子时，计算每组分母分子的最大公约数，为1时将结果加入List
  • 求解最大公约数的方法主要为：辗转相除法、更相减损法

• 题解

  public List<String> simplifiedFractions(int n) {
      List<String> list = new ArrayList<>();
      if(n < 2) return list;
      StringBuilder sb;
      for(int down = 2; down <= n; down++) {
          for(int up = 1; up < down; up++) {
              sb = new StringBuilder();
              if(gcd(down, up) == 1) {
                  sb.append(up).append("/").append(down);
                  list.add(sb.toString());
              }
          }
      }
      // Collections.sort(list);
      return list;
  }
  
  private int gcd(int num1, int num2) {
      if(num2 != 0) return gcd(num2, num1 % num2);
      else return num1;
  }

• 复杂度分析：n 是数组的大小

  • 时间复杂度：$O(n^2*logn)$
  • 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-02-10 22:59:27
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1447.最简分数
本文链接： https://chthollists.github.io/post/8e9bff18.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！

支持

感谢您的支持

支付宝

微信