Leetcode 1447. Simplified Fractions

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，枚举所有的可能的数字组合，如果分子为1，一定是符合条件的，其它情况，需要判断二者是否有大于1最大公约数，使用辗转相除法，求余数，如果存在最大公约数，则返回的余数一定为0，否则返回的余数为1，当约束为1时，符合条件，加入到结果集中。

• Version 1

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for x in range(1, n):
            for y in range(x+1, n+1):
                if x == 1:
                    res.append(f'{x}/{y}')
                else:
                    if self.gcd(x, y):
                        res.append(f'{x}/{y}')
        return res
    
    
    def gcd(self, a, b):
        remainder = a % b
        while remainder > 1:
            a = b
            b = remainder
            remainder = a % b
        return remainder

Reference

1. https://leetcode.com/problems/simplified-fractions/