5130等价多米诺骨牌对的数量

前言

Weekly Contest 146 的 等价多米诺骨牌对的数量：

给你一个由一些多米诺骨牌组成的列表 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

解题思路

一开始我是试了一下暴力破解这个方法，可惜运行超时，只好另想它法了。

后续参考了 Java 中的 HashMap 的位桶的设计，思路如下：

1. 数字 result 表示等价的骨牌对个数，数组 arr 表示多米诺骨牌出现的次数，其中数组下标 i（假设骨牌dominoe=[a,b]，则i=a*10+b）表示对应的多米诺骨牌，arr[i] 表示该骨牌出现的次数

2. 遍历多米诺骨牌列表dominoes，对于每个骨牌dominoe，假设dominoe=[a,b]，然后按照以下逻辑处理

   1. 使用 a*10+b 计算出旋转 0 度时在 arr 的下标 index1；使用b*10+a 计算出旋转 180 度是在 arr 的下标index2
   2. 如果 index1 等于 index2，即表示dominoe 的a等于 b，此时result 增加 arr[index1]，同时arr[index1] 的值自增（避免多累加一次）即可
   3. 如果 index1 不等于 index2，即表示dominoe 的a不等于 b，此时result 增加 arr[index1]，同时arr[index1] 和arr[index2]都自增。

实现代码

暴力破解

暴力破解的方法会出现运行超时的情况，这个是一个错误的示例，列出来给大家参考一下。

    /**
     * 5130. 等价多米诺骨牌对的数量
     * 暴力破解法
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        for (int i = 0; i < dominoes.length; i++) {int a = dominoes[i][0];
            int b = dominoes[i][1];
            for (int j = i+1; j < dominoes.length; j++) {int c = dominoes[j][0];
                int d = dominoes[j][1];
                if((a==c && b==d) || (a==d && b==c)){++result;}
            }
        }
        return result;
    }

有效解答

    /**
     * 5130. 等价多米诺骨牌对的数量
     *
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        // 由于 1 <= dominoes[i][j] <= 9，所以最大值不会超过 99
        int[] arr = new int[100];
        for (int i = 0; i < dominoes.length; i++) {// 以 ij 形式表示骨牌对(i,j)，这个是翻转 0 度（即本身）int index1=dominoes[i][0]*10+dominoes[i][1];
            // 翻转 180 度后
            int index2=dominoes[i][1]*10+dominoes[i][0];
            if(index1 == index2){ // i==j，只要累加一次即可
                result+=arr[index1];
                arr[index1]++;
            }else{result+=arr[index1];
                arr[index1]++;
                arr[index2]++;
            }
        }
        return result;
    }