leetcode逐日一题分享

1128. 等价多米诺骨牌对的数量
尝试过
简单
相关标签
相关企业
提示
给你一组多米诺骨牌 dominoes 。
形式上，dominoes = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。
在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例 1：

1. <strong>输入：</strong>dominoes = [[1,2],[2,1],[3,4],[5,6]]
2. <strong>输出：</strong>1

复制代码

示例 2：

1. <strong>输入：</strong>dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
2. <strong>输出：</strong>3

复制代码

提示：

• 1 <= dominoes.length <= 4 * 104
  
• dominoes.length == 2
  
• 1 <= dominoes[j] <= 9
  

方法一：
暴力解题逐一遍历每一个情况假如满足题目要求就让答案个数加一个
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& A) {
        int nums=A.size();
        vector<int>dp(nums);
        int res=0;
        for(int i=0;i<nums;i++){
            dp=0;
            for(int j=0;j<i;j++){
                if((A[0]==A[j][0]&&A[1]==A[j][1])||(A[1]==A[j][0]&&A[0]==A[j][1])){
                    res++;
                }
            }
        }
        return res;
    }
};

方法二：
运用哈希表对上面的方法举行优化，但是我们对题目所给的数组应该怎样举行处置惩罚呢，以是我们这里想到了一个巧妙的方法，我们先对数组中的每一个元组举行排序按从小到大排序，我们举一个简单的例子对于数组dominoes = [[1,2],[2，1],[1,1],[2，1],[2,2]]，在举行完成排序之后dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]，然后我们在把这样处置惩罚完的数组看成一个整数，对于上面的数组我们直接把他看成[[12],[12],[11],[12],[22]],在经过这样的处置惩罚之后现在这个题目就变得相称明白了，我们直接上代码：
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& A) {
        unordered_map<int, int> hash;
        int res = 0;
       
        for (const auto& domino : A) {
            int key = min(domino[0], domino[1]) * 10 + max(domino[0], domino[1]);
            hash[key]++;
        }
       
        for (const auto& pair : hash) {
            int c = pair.second;
//我们的哈希值求的是每个数出现的个数
//而题目要求是统计两两组合的个数以是这里我们需要利用高中的全分列公式了
            res += c * (c - 1) / 2;
        }
       
        return res;
    }
};

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。