go語言題解LeetCode1128等價多米諾骨牌對的數量

更新時間：2022年12月30日 09:16:29 作者：劉09k11

這篇文章主要為大家介紹了go語言題解LeetCode1128等價多米諾骨牌對的數量示例詳解，

題目描述

1128. 等價多米諾骨牌對的數量 - 力扣（LeetCode）

給你一個由一些多米諾骨牌組成的列表 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

思路分析

這道題想到的是用關聯容器來解決，其中用無序容器更好做。

分析題目的條件可以等價為比較兩個子vector里面的最大值和最小值（比較vec1和vec1的最大值，比較vec1和vec2的最小值）所以KEY 可以設為minNUM maxNUM

在桶里面將存放{minNUM,maxNUM}

遍歷整個dominoes 求出每個子vector里的最大值maxNUM，最小值minNUM 形成KEY ｛minNUM,maxNUM｝然后在桶里查找這個KEY ｛minNUM,maxNUM｝，如果沒找到，則將這個KEY存入桶里并遞增計數1 ,找到了就在對應的KEY 遞增計數1，并且更新count

AC 代碼

struct KEY
{
    int minNum;
    int maxNum;
    KEY(int f,int s):minNum(f),maxNum(s){}
};
struct HashFunc
{
    size_t operator()(const KEY& key) const
    {
        return ((hash<int>()(key.minNum) ^ (hash<int>()(key.maxNum) << 1)) >> 1);
    }
};
struct EqualKey
{
	bool operator () (const KEY &lhs, const KEY &rhs) const
	{
		return lhs.minNum  == rhs.minNum && lhs.maxNum == rhs.maxNum;
	}
};
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<KEY,int,HashFunc,EqualKey> um;
        int count = 0;
        int maxNum = 0,minNum = 0;
        for(auto &n : dominoes)
        {
            minNum = min(n[0],n[1]);
            maxNum = max(n[0],n[1]);
            if(um.find({minNum,maxNum}) != um.end())
            {
                count += um[{minNum,maxNum}];
                um[{minNum,maxNum}]++;
            }
            else
            {
                um[{minNum,maxNum}]++;
            }
        }
        return count;
    }
};

偷懶解法

思路：

把每個多米諾骨牌翻成小的數字在上，大的數字在下的情況，這樣可以使相同的多米諾骨牌的狀態(tài)也相同，便于統(tǒng)計數目。然后用哈希字典來統(tǒng)計每種多米諾骨牌的個數，最后遍歷每種骨牌，用組合數學 n * (n - 1) // 2 求每種骨牌成對的數目，將其累加得到最后結果。

圖解：

代碼：

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        ans = 0
        d = dict()
        for d1, d2 in dominoes:
            # 排序后加入字典
            index = tuple(sorted((d1, d2)))
            if index in d:
                d[index] += 1
            else:
                d[index] = 1
        # 計算答案
        for i in d:
            ans += d[i] * (d[i] - 1) // 2
        return ans

哈希表+元素轉換

解題思路

將每個元素 [a,b] 轉換為 ab，降成一維數組以后就可以利用哈希表統(tǒng)計頻數，因為元素翻轉相同或者不反轉相同都是等價的，所以可以利用高斯求和公式計算每個頻數超過1的元素的數量，再將所以數量相加即為結果。

代碼

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        dominoes_new = []
        for i in dominoes:
            a = i[0]
            b = i[1]
            if a > b:
                a, b = b, a
            dominoes_new.append(a*10+b)
        Hash = {}
        for j in dominoes_new:
            Hash[j] = Hash.get(j, 0) + 1
        res = 0
        for key in Hash.keys():
            n = Hash[key]
            res += n*(n-1)//2
        return res