go語言題解LeetCode1128等價多米諾骨牌對的數(shù)量
題目描述
1128. 等價多米諾骨牌對的數(shù)量 - 力扣(LeetCode)
給你一個由一些多米諾骨牌組成的列表 dominoes
。
如果其中某一張多米諾骨牌可以通過旋轉(zhuǎn) 0
度或 180
度得到另一張多米諾骨牌,我們就認(rèn)為這兩張牌是等價的。
形式上,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)
的數(shù)量。
示例:
輸入:dominoes = [[1,2],[2,1],[3,4],[5,6]] 輸出:1
提示:
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
思路分析
這道題想到的是用關(guān)聯(lián)容器來解決,其中用無序容器更好做。
分析題目的條件 可以等價為 比較兩個子vector里面的最大值和最小值(比較vec1和vec1的最大值,比較vec1和vec2的最小值) 所以KEY 可以設(shè)為minNUM maxNUM
在桶里面將存放{minNUM,maxNUM}
遍歷整個dominoes 求出每個子vector里的最大值maxNUM,最小值minNUM 形成KEY {minNUM,maxNUM} 然后在桶里查找這個KEY {minNUM,maxNUM},如果沒找到,則將這個KEY存入桶里并遞增計數(shù)1 ,找到了就在對應(yīng)的KEY 遞增計數(shù)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; } };
偷懶解法
思路:
把每個多米諾骨牌翻成小的數(shù)字在上,大的數(shù)字在下的情況,這樣可以使相同的多米諾骨牌的狀態(tài)也相同,便于統(tǒng)計數(shù)目。然后用哈希字典來統(tǒng)計每種多米諾骨牌的個數(shù),最后遍歷每種骨牌,用組合數(shù)學(xué) n * (n - 1) // 2 求每種骨牌成對的數(shù)目,將其累加得到最后結(jié)果。
圖解:
代碼:
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
哈希表+元素轉(zhuǎn)換
解題思路
將每個元素 [a,b] 轉(zhuǎn)換為 ab,降成一維數(shù)組以后就可以利用哈希表統(tǒng)計頻數(shù),因為元素翻轉(zhuǎn)相同或者不反轉(zhuǎn)相同都是等價的,所以可以利用高斯求和公式計算每個頻數(shù)超過1的元素的數(shù)量,再將所以數(shù)量相加即為結(jié)果。
代碼
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
復(fù)雜度分析
時間復(fù)雜度:O(N)
空間復(fù)雜度:O(N)
以上就是go語言題解LeetCode1128等價多米諾骨牌對的數(shù)量的詳細(xì)內(nèi)容,更多關(guān)于go題解等價多米諾骨牌數(shù)量的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章

Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過程詳解

golang數(shù)據(jù)結(jié)構(gòu)之golang稀疏數(shù)組sparsearray詳解