欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年12月30日 09:16:29   作者:劉09k11  
這篇文章主要為大家介紹了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的過程詳解

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

    這篇文章主要介紹了Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過程詳解,大概思路是在Go的結(jié)構(gòu)體中每個屬性打上一個excel標(biāo)簽,利用反射獲取標(biāo)簽中的內(nèi)容,作為表格的Header,需要的朋友可以參考下
    2022-06-06
  • GO語言實現(xiàn)TCP服務(wù)器的示例代碼

    GO語言實現(xiàn)TCP服務(wù)器的示例代碼

    這篇文章主要為大家詳細(xì)介紹了如何通過GO語言實現(xiàn)TCP服務(wù)器,文中的示例代碼講解詳細(xì),對我們深入了解Go語言有一定的幫助,需要的可以參考一下
    2023-03-03
  • Go安裝和環(huán)境配置圖文教程

    Go安裝和環(huán)境配置圖文教程

    本文主要介紹了Go安裝和環(huán)境配置圖文教程,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04
  • go語言簡單的處理http請求的函數(shù)實例

    go語言簡單的處理http請求的函數(shù)實例

    這篇文章主要介紹了go語言簡單的處理http請求的函數(shù),實例分析了Go語言處理http請求的技巧,需要的朋友可以參考下
    2015-03-03
  • GO語言延遲函數(shù)defer用法分析

    GO語言延遲函數(shù)defer用法分析

    這篇文章主要介紹了GO語言延遲函數(shù)defer用法,較為詳細(xì)的分析了GO語言的特性與具體用法,并給出了一個比較典型的應(yīng)用實例,具有一定的參考借鑒價值,需要的朋友可以參考下
    2014-12-12
  • Go語言的互斥鎖的詳細(xì)使用

    Go語言的互斥鎖的詳細(xì)使用

    本文主要介紹了Go語言的互斥鎖的詳細(xì)使用,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-06-06
  • golang數(shù)據(jù)結(jié)構(gòu)之golang稀疏數(shù)組sparsearray詳解

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

    這篇文章主要介紹了golang數(shù)據(jù)結(jié)構(gòu)之golang稀疏數(shù)組sparsearray的相關(guān)知識,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • 最新評論