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

给你一组多米诺骨牌 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：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

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

解题思路

输入：一个数组 dominoes

输出：判断有几对等价多米诺骨牌

本题属于 哈希表 + 数组计数 问题。

我们可以将遍历到的多米诺骨牌排序后转成字符串或者元祖存入到哈希表当中

遍历到新的多米诺牌后都在哈希表中找之前出现过几次等价牌数，数量为 count += cache[key]

最后返回答案 count

代码实现

python

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        cache = {}  # 用于统计每种等价牌的出现次数
        count = 0   # 最终结果：等价对的数量

        for a, b in dominoes:
            # 将每张牌的两个数字按升序排序，确保 [1,2] 和 [2,1] 归为同一类
            key = (min(a, b), max(a, b))

            # 如果已经出现过这种组合，则已有 count[key] 个可以与当前配对
            if key in cache:
                count += cache[key]  # 当前这张牌能和已有的每一张等价牌组成一对
                cache[key] += 1      # 更新出现次数
            else:
                cache[key] = 1       # 第一次出现，初始化为 1

        return count

javascript

/**
 * @param {number[][]} dominoes
 * @return {number}
 */
var numEquivDominoPairs = function(dominoes) {
    const cache = new Map();
    let count = 0;
    for (let arr of dominoes) {
        arr = [Math.min(...arr), Math.max(...arr)];
        const key = String(arr);

        if (cache.has(key)) {
            count += cache.get(key);
            cache.set(key, cache.get(key) + 1);
        } else {
            cache.set(key, 1);
        }
    }

    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1128 国际版

27 中文版