Leetcode1128. 等价多米诺骨牌对的数量

数量"/>

Leetcode1128. 等价多米诺骨牌对的数量

Every day a Leetcode

题目来源：1128. 等价多米诺骨牌对的数量

解法1：暴力

代码：

class Solution
{
public:int numEquivDominoPairs(vector<vector<int>> &dominoes){int n = dominoes.size(), count = 0;for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++){if (dominoes[i] == dominoes[j] || dominoes[i] == vector<int>(dominoes[j].rbegin(), dominoes[j].rend()))count++;}return count;}
};

结果：

超时了。

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 dominoes 的长度。

空间复杂度：O(1)。

解法2：哈希

遍历数组 dominoes，对每一个多米诺骨牌 domino 排序，这样就保证等价的多米诺骨牌能存储在一个哈希值里。用一个形如 unordered_map<vector<int>, int> 的哈希表，记录等价的多米诺骨牌的数量。

结果报错了：

error: call to implicitly-deleted default constructor of ‘unordered_map＜vector＜int＞, int＞‘

用 map 就行了。

具体办法：error: call to implicitly-deleted default constructor of ‘unordered_map＜vector＜int＞, int＞‘

设一种多米诺骨牌的出现次数为 n，则等价的骨牌对 (i, j) 的数量为 C(n, 2) = n * (n - 1) / 2。答案为等价的骨牌对 (i, j) 的数量的总和。

代码：

/** @lc app=leetcode id=1128 lang=cpp** [1128] 等价多米诺骨牌对的数量*/// @lc code=start
// class Solution
// {
// public:
//     int numEquivDominoPairs(vector<vector<int>> &dominoes)
//     {
//         int n = dominoes.size(), count = 0;
//         for (int i = 0; i < n - 1; i++)
//             for (int j = i + 1; j < n; j++)
//             {
//                 if (dominoes[i] == dominoes[j] || dominoes[i] == vector<int>(dominoes[j].rbegin(), dominoes[j].rend()))
//                     count++;
//             }
//         return count;
//     }
// };class Solution
{
public:int numEquivDominoPairs(vector<vector<int>> &dominoes){int n = dominoes.size();map<vector<int>, int> hash;for (vector<int> &domino : dominoes){sort(domino.begin(), domino.end());hash[domino]++;}int count = 0;for (auto it = hash.begin(); it != hash.end(); it++){int freq = it->second;// 组合：C(n, 2) = n * (n - 1) / 2count += freq * (freq - 1) / 2;}return count;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 dominoes 的长度。

空间复杂度：O(n)，其中 n 是数组 dominoes 的长度。