จำนวนคู่โดมิโนเทียบเท่าใน Python

ให้ลิสต์โดมิโน แต่ละอันมี 2 ตัวเลข โดมิโน D[i] = [a,b] และ D[j] = [c,d] ถือว่าเทียบเท่ากันถ้า a=c และ b=d หรือ a=d และ b=c (กลับด้านได้) หาจำนวนคู่ (i,j) ที่ i<j และเทียบเท่ากัน

ตัวอย่าง: [[1,2],[2,1],[3,4],[6,5]] ผลลัพธ์ = 1 (คู่ [1,2] กับ [2,1])

ขั้นตอนการแก้ปัญหา

1. สร้าง dictionary d นับความถี่
2. วนลูปแต่ละคู่ใน dominoes:
   • เรียงลำดับคู่ (sort) เพื่อให้ [1,2] และ [2,1] กลายเป็น key เดียวกัน
   • แปลงเป็น tuple เพื่อเป็น key ได้
   • เพิ่มจำนวนใน dictionary
3. สำหรับแต่ละความถี่ b ใน dictionary: เพิ่ม b * (b-1) / 2 เข้าคำตอบ (จำนวนคู่จาก b อัน)
4. คืนคำตอบ

ตัวอย่างโค้ด

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        d = {}
        ans = 0
        for i in dominoes:
            i.sort()
            i = tuple(i)
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for b in d.values():
            ans += (b * (b - 1)) // 2
        return ans

ob1 = Solution()
print(ob1.numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6],[4,3]]))

อินพุต

[[1,2],[2,1],[3,4],[5,6],[4,3]]

เอาต์พุต

2

วิธีแก้แบบ Pythonic (ใช้ Counter)

from collections import Counter

def numEquivDominoPairs(dominoes):
    cnt = Counter(tuple(sorted(d)) for d in dominoes)
    return sum(v * (v - 1) // 2 for v in cnt.values())