题目

题目描述：

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.

Example 1:

Input: n = 2
Output: [“1/2”]
Explanation: “1/2” is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:

Input: n = 3
Output: [“1/2”,”1/3”,”2/3”]
Example 3:

Input: n = 4
Output: [“1/2”,”1/3”,”1/4”,”2/3”,”3/4”]
Explanation: “2/4” is not a simplified fraction because it can be simplified to “1/2”.

Constraints:

1 <= n <= 100

思路:

两层遍历，不把最大公约数不为1的数放进去就行

代码:

func gcd(a, b int)int{
    if b == 0{
        return a
    }else{
        return gcd(b,a%b)
    }
}


func simplifiedFractions(n int) []string {
    var res []string 
    for i:=2;i<=n;i++{
        for j:=1;j<i;j++{
            
            if  gcd(i,j) !=1{
                continue
            }
            s := fmt.Sprintf("%d", j)+"/"+strconv.Itoa(i)
            res = append(res, s)
        }
    }
    return res
}

代码效率：

执行用时：44 ms, 在所有 Go 提交中击败了51.61%的用户
内存消耗：6.8 MB, 在所有 Go 提交中击败了96.77%的用户