数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：计算和为1的分数对数量
假设我们有一个分数列表，每个分数都是一个单独的列表 [分子, 分母]，表示数字 (分子 / 分母)。我们必须找到和为 1 的分数对的数量。
因此，如果输入类似于 fractions = [[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]，则输出将为 4，因为 (2/7 + 5/7), (3/12 + 3/4), (3/4 + 1/4), (4/14 + 5/7) 是四个和为 1 的对。
为了解决这个问题，我们将遵循以下步骤：
- d := 一个新的映射
- ans := 0
- 对于分数列表 fractions 中的每个分数 i：
- x := i[分子]
- y := i[分母]
- g := (x, y) 的最大公约数
- x := x / g
- y := y / g
- temp_x := y - x
- temp_y := y
- 如果 (temp_x, temp_y) 在 d 中，则：
- ans := ans + d[temp_x, temp_y]
- d[x, y] := 1 + (如果存在 d[(x, y)]，则为 d[(x, y)]，否则为 0)
- 返回 ans
让我们看看下面的实现以更好地理解。
示例代码
class Solution:
def solve(self, fractions):
import math
d = {}
ans = 0
for i in fractions:
x = i[0]
y = i[1]
g = math.gcd(x, y)
x /= g
y /= g
temp_x = y - x
temp_y = y
if (temp_x, temp_y) in d:
ans += d[(temp_x, temp_y)]
d[(x, y)] = d.get((x, y), 0) + 1
return ans
ob = Solution()
fractions = [[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]
print(ob.solve(fractions))输入
[[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]
输出
4
更新于：2020年11月25日
1K+ 浏览量
广告