資料結構
網路
關係資料庫管理系統 (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+ 瀏覽量
廣告