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

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一组多米诺骨牌 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

提示：

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

解题思路

函数接受一个二维数组 dominoes，其中每个元素表示一对多米诺骨牌。该函数使用一个对象 cnt 来统计每种多米诺骨牌的出现次数。然后遍历 cnt 对象，计算每种多米诺骨牌的等价对的数量，并累加到变量 res 中。最后返回 res。

具体实现是通过将每对多米诺骨牌排序并转换为字符串作为键来统计其出现次数。然后根据组合公式计算每种多米诺骨牌的等价对的数量，并累加到结果中。

AC代码

/**
 * @param {number[][]} dominoes
 * @return {number}
 */
var numEquivDominoPairs = function(dominoes) {
    const cnt = {};
    for(const domino of dominoes){
        const key = domino.sort().join('-');
        let val = cnt[key] || 0;
        cnt[key] = val + 1;
    }
    let res = 0;
    for(const key in cnt){
        const count = cnt[key] - 1;
        res += (1 + count) * count / 2;
    }
    return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。