1128. Number of Equivalent Domino Pairs*

​​https://leetcode.com/problems/number-of-equivalent-domino-pairs/​​

题目描述

Given a list of ​

​dominoes​

​​, ​

​dominoes[i] = [a, b]​

​​ is equivalent to ​

​dominoes[j] = [c, d]​

​​ if and only if either ​

​(a==c and b==d)​

​​, or ​

​(a==d and b==c)​

​ - that is, one domino can be rotated to be equal to another domino.

Return the number of ​

​pairs (i, j)​

​​ for which ​

​0 <= i < j < dominoes.length​

​​, and ​

​dominoes[i]​

​​ is equivalent to ​

​dominoes[j]​

​.

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1      

Constraints:

• ​

  ​1 <= dominoes.length <= 40000​

  ​
• ​

  ​1 <= dominoes[i][j] <= 9​

  ​

C++ 实现 1

采用 1. Two Sum*​ 的思路, 利用一个哈希表保存已经访问过的 ​

​domino​

​​. 这题容易需要注意的地方是, 比如 ​

​dominoes = [[1, 2], [1, 2], [1, 2], [1, 2]]​

​​, 最后返回的结果应该是 ​

​3 + 2 + 1 = 6​

​.

class Solution {
private:
    struct HashVector {
        std::size_t operator()(const std::vector<int> &vec) const {
            std::size_t seed = vec.size();
            for(auto& i : vec) {
                seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
             }
            return seed;
        }
    };
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<vector<int>, int, HashVector> records;
        int res = 0;
        for (auto &d : dominoes) {
            // 使最小值放在前面
            std::sort(d.begin(), d.end());
            if (records.count(d)) res += records[d] ++;
            else records[d] ++;
        }
        return res;
    }
};