LeetCode - 1128. 等价多米诺骨牌对的数量

本文主要是介绍LeetCode - 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) 的数量。

 

示例：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/
 

求解

    class Solution {public:// 方法一， 暴力解法// 超时未通过int numEquivDominoPairs_vio(vector<vector<int>> &dominoes) {const int n = dominoes.size();int count = 0;for (int i = 0; i < n - 1; ++i) {for (int j = i + 1; j < n; ++j) {if (isDominoes(dominoes[i], dominoes[j])) {++count;}}}return count;}// 方法二，利用查找表// 低效率通过int numEquivDominoPairs_2e(const vector<vector<int>> &dominoes) {const int n = dominoes.size();int count = 0;std::unordered_map<int, vector<vector<int>>> record; // <和， 点对数组>记录，用于快速查找for (auto &dominoe : dominoes) {int sum = dominoe[0] + dominoe[1];if (record.count(sum) > 0) {const auto &vecs = record[sum];for (const auto &vec : vecs) {if (isDominoes(dominoe, vec)) {++count;}}}record[sum].push_back(std::move(dominoe));}return count;}// 方法三，参考官方解答// 1 <= dominoes[i][j] <= 9，因此对每对的两个数字编码，10*min(x,y) + max(x,y)肯定总是小于100int numEquivDominoPairs_3e(const vector<vector<int>> &dominoes) {vector<int> record(100, 0); // 100做记录足够了int res = 0;for (const auto &p : dominoes) {int val = p[0] < p[1] ? 10 * p[0] + p[1] : 10 * p[1] + p[0];res += record[val];++record[val];}return res;}// 方法四，hash散列，重定义等价性计数，就是速度太慢// 函数对象实现hash计算struct dominoeHash {std::size_t operator()(const vector<int> &vec) const {std::hash<int> intHash;return vec[0] < vec[1] ? intHash(vec[0]) ^ intHash(vec[1]) : intHash(vec[1]) ^ intHash(vec[0]);}};// 函数对象实现equal_tostruct dominoeEqualTo {bool operator()(const vector<int> &vec1, const vector<int> &vec2) const {return (vec1[0] == vec2[0] && vec1[1] == vec2[1]) || (vec1[0] == vec2[1] && vec1[1] == vec2[0]);}};int numEquivDominoPairs(const vector<vector<int>> &dominoes) {// todo 使用lambda表达式
//            auto const &hashcode = [](const vector<int> &vec) {
//                std::hash<int> intHash;
//                return vec[0] < vec[1] ? intHash(vec[0]) ^ intHash(vec[1]) : intHash(vec[1]) ^ intHash(vec[0]);
//            };
//
//            auto const &equalDominoe = [](const vector<int> &vec1, const vector<int> &vec2) {
//                return (vec1[0] == vec2[0] && vec1[1] == vec2[1]) || (vec1[0] == vec2[1] && vec1[1] == vec2[0]);
//            };// 使用函数对象实现hash计算和equal_toint count = 0;std::unordered_multiset<vector<int>, dominoeHash, dominoeEqualTo> record;for (const auto &p : dominoes) {int num = record.count(p);if (num > 0) {count += num;}record.emplace(p.begin(), p.end());}return count;}private:inline bool isDominoes(const vector<int> &vec1, const vector<int> &vec2) const {return (vec1[0] == vec2[0] && vec1[1] == vec2[1]) || (vec1[0] == vec2[1] && vec1[1] == vec2[0]);}};

 

这篇关于LeetCode - 1128. 等价多米诺骨牌对的数量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---