点击获取AI摘要

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

给你一组多米诺骨牌 dominoes 。

形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。

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

示例 1：

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

示例 2：

1
2
输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
输出：3

提示：

  • 1 <= dominoes.length <= 4 * 10⁴
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9

问题分析

  • 给你一个多米诺骨牌列表 dominoes，每个骨牌是一个长度为 2 的数组 [a, b]。
  • 如果两张骨牌旋转后能完全一致，就称它们等价。
  • 例如 [1,2] 与 [2,1] 等价。我们要统计所有满足等价关系的骨牌对 (i, j) (i<j)(i < j) 的总数。

算法思路

  1. 规范化（标准化）表示

    • 每张骨牌 [a, b]，将它变成有序对 (min(a,b), max(a,b))。
    • 这样无论原来是 [1,2] 还是 [2,1]，都统一映射为为 (1,2)。

  2. 哈希表计数

    • 用一个字典（或 Python 的 Counter）记录每种“规范化后”的骨牌出现了多少次。
    • 键（key）就是那个二元组，值（value）就是出现次数。

  3. 组合数学计算对数

    • 如果某种骨牌规范后出现了 kk 次，那么这 kk 张骨牌两两之间都能组成等价对，共有组合数

      (k2)  =  k×(k−1)2\binom{k}{2} \;=\;\frac{k\times (k-1)}{2}

    • 把所有不同骨牌规范的组合数累加，就是答案。

时间复杂度

  • 时间复杂度：遍历一次骨牌列表 O(n)O(n)，再遍历一次哈希表（最坏也是 O(n)O(n)），总体 O(n)O(n)。
  • 空间复杂度：哈希表存储规范后骨牌的计数，最坏情况键值对有 O(n)O(n) 个。

代码分解

  1. 初始化计数字典

    1
    2
    from collections import Counter
    count = Counter()

  2. 标准化并计数

    1
    2
    3
    for a, b in dominoes:
        key = (a, b) if a <= b else (b, a) # 保证顺序
        count[key] += 1

  3. 组合数学求配对数

    1
    2
    3
    for k in count.values():
        if k > 1:
            result += k*(k-1)//2

    (k2)\binom{k}{2} 的计算公式直接用整数运算实现

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:
        # 1. 用 Counter 创建一个空的哈希表
        count = Counter()
        
        # 2. 遍历每一张骨牌
        for a, b in dominoes:
            # 2.1 规范化：用元组(key)表示，保证先小后大
            if a <= b:
                key = (a, b)
            else:
                key = (b, a)
            # 2.2 对该 key 的出现次数 +1
            count[key] += 1
        
        # 3. 统计所有规范对的组合数之和
        result = 0
        # 3.1 对哈希表中每一种规范对
        for k in count.values():
            # 只有 k>=2 时才会有配对
            if k > 1:
                # 组合数 C(k,2) = k*(k-1)//2
                result += k * (k - 1) // 2
        
        # 4. 返回结果
        return result

以 [[1,2], [2,1], [3,4], [5,6]] 为例：

原始骨牌 规范化后 累计到哈希表中
[1,2] (1,2) count[(1,2)] = 1
[2,1] (1,2) count[(1,2)] = 2
[3,4] (3,4) count[(3,4)] = 1
[5,6] (5,6) count[(5,6)] = 1

最终哈希表 count 为：

1
2
3
4
5
{
  (1,2): 2,
  (3,4): 1,
  (5,6): 1
}

接下来计算组合数：

  • 对 (1,2)，出现次数 k=2k=2，组合数 (22)=1\binom{2}{2} = 1
  • (3,4) 与 (5,6) 都只出现过 1 次，不会贡献配对（因为 (12)=0\binom{1}{2}=0 ）

所以总对数 = 1。