Giả sử chúng ta có một danh sách các phân số trong đó mỗi phân số là các danh sách riêng lẻ [tử số, mẫu số] đại diện cho số (tử số / mẫu số). Chúng ta phải tìm số cặp phân số có tổng bằng 1.
Vì vậy, nếu đầu vào giống như phân số =[[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]], thì đầu ra sẽ là 4, vì (2/7 + 5/7), (3/12 + 3/4), (3/4 + 1/4), (4/14 + 5/7) là bốn cặp tổng đến 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- d:=một bản đồ mới
- ans:=0
- đối với mỗi phân số i trong các phân số, hãy thực hiện
- x:=i [tử số]
- y:=i [mẫu số]
- g:=gcd của (x, y)
- x:=x / g
- y:=y / g
- temp_x:=y - x
- temp_y:=y
- nếu (temp_x, temp_y) bằng d, thì
- ans:=ans + d [temp_x, temp_y]
- d [x, y]:=1 + (d [(x, y)] khi có sẵn, nếu không thì 0)
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Mã mẫu
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)) Đầu vào
[[2, 7],[3, 12],[4, 14],[5, 7],[3, 4],[1, 4]]
Đầu ra
4