641，最简分数，使用最大公约数求解

问题描述

来源：LeetCode第1447题

难度：中等

给你一个整数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的最简分数，我们只需要枚举所有的结果，然后选择分子和分母不能约分的分数，也就是分子和分母的最大公约数是1。所以这题就转化成了求最大公约数问题，求两个数的最大公约数我们可以使用辗转相除法，也就是欧几里得算法，前面我们在讲618，找出数组的最大公约数的时候有过详细的分析，这里就不在重复介绍，来看下代码

public List<String> simplifiedFractions(int n) {
    List<String> res = new ArrayList<>();
    //枚举所有的可能结果
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            //判断如果分子和分母不能约分，就是我们需要的
            if (gcd(i, j) == 1) {
                res.add(j + "/" + i);
            }
        }
    }
    return res;
}

//求i和j的最大公约数
private int gcd(int i, int j) {
    return i % j == 0 ? j : gcd(j, i % j);
}

●598，动态规划解目标和

●603，回溯算法解划分为k个相等的子集

●608，滑动窗口判断是否存在重复元素 II

●532，BFS解打开转盘锁