สมมติว่าเรามีรายการเศษส่วนโดยที่เศษส่วนแต่ละส่วนเป็นรายการแต่ละรายการ [ตัวเศษ ตัวส่วน] ซึ่งแทนตัวเลข (ตัวเศษ / ตัวส่วน) เราต้องหาจำนวนคู่ของเศษส่วนที่มีผลรวมเป็น 1
ดังนั้น ถ้าอินพุตเป็นเหมือนเศษส่วน =[[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 :=แผนที่ใหม่
- ตอบ :=0
- สำหรับแต่ละเศษส่วน i ในเศษส่วน ทำ
- x :=i[ตัวเศษ]
- y :=i[ตัวส่วน]
- g :=gcd ของ (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)] เมื่อพร้อมใช้งาน มิฉะนั้น 0)
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
โค้ดตัวอย่าง
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
