等价多米诺骨牌对的数量(java实现)

力扣 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) 的数量。

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

示例

例1

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

笔者理解

此题是一道数组求解算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现只要把骨牌的组合出现次数计算出来，并把各种组合的骨牌的对数求出来累加即可，就让我们看看具体如何实现吧。

骨牌组合：如[1,2]和[1,2]为同一个组合，[1,2]和[2,1]也为一个组合

骨牌对数：如果组合出现2次，骨牌对数为1，组合出现3次，骨牌对数为2+1，所以组合出现n次，骨牌对数为(n-1)+…+2+1,即*(nn-n)/2**

实现

public int numEquivDominoPairs(int[][] dominoes) {
        if(dominoes.length==1){return 0;}
        //只有一块多米诺骨牌时，返回0
        int result = 0;
        Map <Integer,Integer>times = new HashMap<Integer, Integer>();
        //用来记录对应骨牌的出现次数
        int x,y;
        int num;
        //用来记录多米诺骨牌双值中的较大值和较小值
        for (int i = 0; i < dominoes.length; i++) {
            x = Math.max(dominoes[i][0],dominoes[i][1]);
            y = Math.min(dominoes[i][0],dominoes[i][1]);
            num = x*10+y;
            //以较大值为十位，较小值为个位记录各种骨牌的可能及出现次数
            if(times.getOrDefault(num,0)==0){
                //没这个组合就记录并存入
                times.put(num,1);
            }
            else{
                //有这个组合就将组合出现次数加一
                times.put(num,times.get(num)+1);
            }
        }
        for(int i:times.values()){
            if(i>1){
                //遍历hashmap并将所有对数累加
                result+=(i*i-i)/2;
            }
        }
        return result;
    }