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

难度：简单

二、题解

方法一：哈希表

由于可能出现重复的骨牌，因此需要记录同一种骨牌出现的次数，由于翻转180度可视为同一张骨牌，因此需要考虑翻转情况，但又要除去骨牌的两个数字都相等时的翻转，避免重复相加。

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        map<vector<int>,int> mp;
        int ans = 0;
        for(vector<int> dominoe:dominoes){
            if(mp.find(dominoe)==mp.end()){
                mp[dominoe] = 1;
            }else{
                ans+=mp[dominoe];
                mp[dominoe]++;  
            }
            
            reverse(dominoe.begin(),dominoe.end());
            if(dominoe[0]!=dominoe[1]&&mp.find(dominoe)!=mp.end()){
                ans+=mp[dominoe];
            }
        }
        return ans;
    }
};
           

方法二：二元组表示 + 计数

比较巧妙的方法，注意到二元对中的元素均不大于 99，因此我们可以将每一个二元对拼接成一个两位的正整数，即 (x,y)→10x+y。这样就无需使用哈希表统计元素数量，而直接使用长度为 100的数组即可。

翻转情况：让每一个二元对都变为指定的格式，即第一维必须不大于第二维

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] nums = new int[100];
        int ans = 0;
        for(int[] dominoe:dominoes){
            int val = dominoe[0]<dominoe[1]?10*dominoe[0]+dominoe[1]:10*dominoe[1]+dominoe[0];
            ans += nums[val];
            nums[val]++;
        }
        return ans;
    }
}