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