【刷穿 LeetCode】1128. 等价多米诺骨牌对的数量（简单）

题目描述

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。

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

示例：

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

提示：

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

哈希表解法

dominoes 中的值的范围是 [1,9]，因此可以使用单个骨牌里的两个数来构建成一个范围在 [11,99] 的数。

这里让较小的数作为十位数，较大的数作为个位数。这样就实现了两个等效的骨牌对应的是同一个数。

构造出来的数作为 key，统计每类骨牌的出现次数。

当使用哈希表进行统计之后，对于个数大于等于 2 的骨牌。根据骨牌的出现次数，使用等差数列求和公式来计算对数：

注意：对于数量为 cnt 的骨牌的对数的项数为 n - 1

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int[] dominoe : dominoes) {
            int key = Math.min(dominoe[0], dominoe[1]) * 10 + Math.max(dominoe[0], dominoe[1]);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        int ans = 0;
        for (int key : map.keySet()) {
            int cnt = map.get(key);
            if (cnt >= 2) {
                ans += (cnt - 1) + (cnt - 1) * (cnt - 2) / 2;
            }
        }
        return ans;
    }
}

• 时间复杂度：对数组进行了一次遍历。复杂度为

• 空间复杂度：最坏情况下，没有等价的骨牌，每块骨牌在哈希表占用一个 key。复杂度为

数组解法

由于转换出来的数的范围固定为 [11,99]，我们可以直接使用等长数组来进行计数。

对于数量为 n 的骨牌，其对数等于 1 + 2 + 3 + 4 + ... + (n - 1)

因此可以采用边遍历边累加的方式：

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] cnt = new int[89];
        int ans = 0;
        for (int[] dominoe : dominoes) {
            int idx = Math.min(dominoe[0], dominoe[1]) * 10 + Math.max(dominoe[0], dominoe[1]) - 11;
            ans += cnt[idx];
            cnt[idx]++;
        }
        return ans;
    }
}

• 时间复杂度：对数组进行了一次遍历。复杂度为

• 空间复杂度：进行计数的数组长度固定。复杂度为

最后

这是我们「刷穿 LeetCode」系列文章的第 * 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。