[leetcode] 1447. Simplified Fractions

[leetcode] 1447. Simplified Fractions

Description

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. The fractions can be in any order.

Example 1:

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

Example 2:

Input: n = 3Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4Output: ["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".

Example 4:

Input: n = 1Output: []

Constraints:

1 <= n <= 100

分析

题目的意思是：给定一个数n，求出其简化的分数形式，其中分母小于等于n。思路也很简单，双循环，其中一个循环为分母，另一个循环为分子，由于需要简化形式，所以需要求一下公约数，然后把分子分母除以公约数变成字符串就行了。最后去重一下就行了。

代码

class Solution: def common_factor(self,m,n): if(n==0): return m return self.common_factor(n,m%n) def simplifiedFractions(self, n: int) -> List[str]: res=[] for i in range(1,n+1): for j in range(1,i): fac=self.common_factor(i,j) res.append(str(j//fac)+'/'+str(i//fac)) return list(set(res))

参考文献

​​梳理使用Python实现求两数最大公约数（四种方法）​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。