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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结果：

超时了。

复杂度分析：

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

空间复杂度：O(1)。

解法2：哈希

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

结果报错了：

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

用 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.cn id=1128 lang=cpp
 *
 * [1128] 等价多米诺骨牌对的数量
 */

// @lc code=start
// class Solution
// {
// public:
//     int numEquivDominoPairs(vector> &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(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) / 2
            count += freq * (freq - 1) / 2;
        }
        return count;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

结果：

复杂度分析：

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

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