跳转至

LeetCode: 1128. 等价多米诺骨牌对的数量

1、题目描述

给你一个由一些多米诺骨牌组成的列表 dominoes

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的。

形式上,dominoes[i] = [a, b]dominoes[j] = [c, d] 等价的前提是 a==cb==d,或是 a==db==c

0 <= i < j < dominoes.length 的前提下,找出满足 dominoes[i]dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例:

输入:dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出:1

提示:

  • 1 <= dominoes.length <= 40000

  • 1 <= dominoes[i][j] <= 9

2、解题思路

  • 将每个元素排序并转换成元组
  • 统计出现次数,并计算取其中2个的组合个数
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:

        from collections import Counter
        from scipy.special import comb, perm

        c = Counter([tuple(sorted(x)) for x in dominoes])

        res = 0
        for key, count in c.items():
            res += comb(count,2)

        return int(res)