Số Cặp Domino Tương Đương (Equivalent Domino Pairs) Trong Python

Cho danh sách domino, mỗi domino có 2 số [a, b]. Hai domino [a,b] và [c,d] tương đương nếu a==c và b==d HOẶC a==d và b==c (có thể lật ngửa). Đếm số cặp (i, j) với i < j mà 2 domino tương đương.

Ví dụ: [[1,2],[2,1],[3,4],[5,6],[4,3]] → 2 cặp: ([1,2],[2,1]) và ([3,4],[4,3]).

Thuật toán

1. Chuẩn hóa mỗi domino: sắp xếp 2 số → tuple(sorted(domino))
2. Đếm tần suất mỗi domino chuẩn hóa → dictionary freq
3. Với mỗi tần suất f, số cặp = C(f, 2) = f * (f-1) / 2
4. Tổng cộng tất cả

Ví dụ (Python)

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        freq = {}
        for d in dominoes:
            key = tuple(sorted(d))
            freq[key] = freq.get(key, 0) + 1
        
        ans = 0
        for count in freq.values():
            ans += count * (count - 1) // 2
        return ans

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

Độ phức tạp

• Thời gian: O(n) (sort 2 phần tử là O(1))
• Không gian: O(n)

Đầu vào / Đầu ra

Input:  [[1,2],[2,1],[3,4],[5,6],[4,3]]
Output: 2