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

【LetMeFly】1128.等价多米诺骨牌对的数量：计数

力扣题目链接：https://leetcode.cn/problems/number-of-equivalent-domino-pairs/

给你一组多米诺骨牌 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 * 10⁴
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9

解题方法：计数

使用一个哈希表(或数组)统计每种多米诺骨牌的出现次数。

既然[1, 2]和[2, 1]等价，那么不妨将他们视为同一种骨牌来看待。

即：当[a, b]中a > b时，将[a, b]调整为[b, a]。

哈希表如何设计（如何将两个数映射为一个数）？

(a - 1) * 9 + (b - 1)即可。

这样，哈希表的大小9 * 9 = 81即可。

如何计算“对数”？

两种方法：

统计出每种骨牌出现次数后，遍历哈希表，若这种骨牌出现了 $t$ 次，则可形成 $\frac{t (t - 1)}{2}$ 对骨牌

假设在骨牌 $v$ 加入哈希表之前哈希表中 $v$ 出现了 $t$ 次，那么就先将答案加上 $t$ 再将哈希表中 $v$ 出现次数加一。

时间复杂度：方法一 $O (l e n (d o min oes))$ ；方法二 $O(len(dominoes)+C^2)$ 。其中 $C = 9$
空间复杂度 $O(C^2)$

AC代码

C++ - 方法二

/** @Author: LetMeFly* @Date: 2025-05-04 14:26:01* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-04 15:02:06*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
private:inline int pair2int(vector<int>& v) {if (v[0] > v[1]) {return (v[1] - 1) * 9 + (v[0] - 1);}return (v[0] - 1) * 9 + (v[1] - 1);}
public:int numEquivDominoPairs(vector<vector<int>>& dominoes) {int times[81] = {0};for (vector<int>& v : dominoes) {times[pair2int(v)]++;}int ans = 0;for (int i = 0; i < 81; i++) {ans += times[i] * (times[i] - 1) / 2;}return ans;}
};

C++ - 方法一

/** @Author: LetMeFly* @Date: 2025-05-04 16:12:00* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-04 16:13:46*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
public:int numEquivDominoPairs(vector<vector<int>>& dominoes) {int times[81] = {0} ;int ans = 0;for (vector<int>& d : dominoes) {ans += times[d[0] < d[1] ? (d[0] - 1) * 9 + d[1] - 1 : (d[1] - 1) * 9 + d[0] - 1]++;}return ans;}
};

Python - 方法一

'''
Author: LetMeFly
Date: 2025-05-04 14:26:12
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-04 16:10:15
'''
from typing import Listclass Solution:def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:times = [0] * 81ans = 0for a, b in dominoes:v = (a - 1) * 9 + (b - 1) if a < b else (b - 1) * 9 + (a - 1)ans += times[v]times[v] += 1return ans

Java - 方法一

/** @Author: LetMeFly* @Date: 2025-05-04 14:26:15* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-04 16:15:28*/
class Solution {public int numEquivDominoPairs(int[][] dominoes) {int[] times = new int[81];int ans = 0;for (int[] d : dominoes) {ans += times[d[0] < d[1] ? (d[0] - 1) * 9 + d[1] - 1 : (d[1] - 1) * 9 + d[0] - 1]++;}return ans;}
}

Go - 方法一

/** @Author: LetMeFly* @Date: 2025-05-04 14:26:18* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-04 16:18:34*/
package mainfunc numEquivDominoPairs(dominoes [][]int) (ans int) {times := make([]int, 81)for _, d := range dominoes {var v intif d[0] < d[1] {v = (d[0] - 1) * 9 + d[1] - 1} else {v = (d[1] - 1) * 9 + d[0] - 1}ans += times[v]times[v]++}return
}