当前位置：首页 > ai >正文

算法热题——等价多米诺骨牌对的数量

ai 2025/5/10 21:17:13

题目链接：1128. 等价多米诺骨牌对的数量 - 力扣（LeetCode）

题目描述

解法一：哈希表

题目理解

核心思想

标准化方法：

统计方法

举个例子

✅ 总结

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

题目链接：1128. 等价多米诺骨牌对的数量 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

解法一：哈希表

题目理解

你有一组多米诺骨牌 dominoes，每张牌由两个数字组成，例如 [a, b]。

我们定义两张多米诺骨牌是等价的，当其中一张可以通过旋转（0°或180°）变成另一张。也就是说：

[a, b] 与 [c, d] 等价，当且仅当：
- a == c && b == d（不旋转）
- 或者 a == d && b == c（旋转180度）

我们要找出满足 i < j 的前提下，有多少对 (i, j) 是等价的。

核心思想

我们可以把每张多米诺骨牌统一成一个标准形式，这样就可以很容易地判断哪些是“相同的”牌。

标准化方法：

对于每张牌 [a, b]，我们把它变成 [min(a, b), max(a, b)]。

这样一来：

[1, 2] 和 [2, 1] 都会被标准化为 [1, 2]
所有等价的牌都会具有相同的表示

统计方法

我们可以使用一个哈希表来记录每种标准化后的多米诺骨牌出现的次数。

当我们遍历到一个新的牌时：

如果之前已经出现过相同类型的牌，那么它能和之前所有相同的牌组成一对
每遇到一次重复，就将当前已有的数量加到结果中

举个例子

假设输入是：

dominoes = [[1,2], [2,1], [3,4], [5,6], [1,2]]

标准化后变为：

[1,2], [1,2], [3,4], [5,6], [1,2]

遍历过程中：

第1个 [1,2]：没出现过 → 不加
第2个 [1,2]：之前出现了1次 → 加1
第3个 [3,4]：没出现过 → 不加
第4个 [5,6]：没出现过 → 不加
第5个 [1,2]：之前出现了2次 → 加2

最终结果是 1 + 2 = 3

✅ 总结

步骤	描述
1. 标准化	将每个多米诺 `[a,b]` 转换为 `[min(a,b), max(a,b)]`
2. 哈希计数	使用 `HashMap` 统计每种标准化牌出现的次数
3. 计算配对	每遇到一张牌，查看前面有多少张一样的，就是可以组成的对数

Java写法：

        // 使用HashMap存储每种标准化后的多米诺骨牌及其出现的次数Map<String, Integer> map = new HashMap<>();int count = 0;for (int[] domino : dominoes) {// 对多米诺骨牌进行标准化处理，保证a <= bint a = Math.min(domino[0], domino[1]);int b = Math.max(domino[0], domino[1]);String key = a + "," + b;// 如果map中已经存在这种标准化后的多米诺骨牌，// 则说明可以与当前多米诺骨牌形成等价对的数量就是其在map中的计数if (map.containsKey(key)) {count += map.get(key);}// 更新当前标准化后多米诺骨牌的计数map.put(key, map.getOrDefault(key, 0) + 1);}return count;}

C++写法：

#include <vector>
#include <string>
#include <unordered_map>using namespace std;class Solution {
public:int numEquivDominoPairs(vector<vector<int>>& dominoes) {unordered_map<string, int> countMap;int totalPairs = 0;for (const auto& domino : dominoes) {int a = domino[0];int b = domino[1];// 标准化为 min, max 形式if (a > b) swap(a, b);string key = to_string(a) + "," + to_string(b);// 当前可以与之前所有的相同项组成对totalPairs += countMap[key];// 增加计数countMap[key]++;}return totalPairs;}
};