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

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

 更新時間:2022年12月30日 09:16:29   作者:劉09k11  
這篇文章主要為大家介紹了go語言題解LeetCode1128等價多米諾骨牌對的數(shù)量示例詳解,

題目描述

1128. 等價多米諾骨牌對的數(shù)量 - 力扣(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) 的數(shù)量。

示例:

輸入:dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出:1

提示:

1 <= dominoes.length <= 40000

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

思路分析

這道題想到的是用關聯(lián)容器來解決,其中用無序容器更好做。

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

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

遍歷整個dominoes 求出每個子vector里的最大值maxNUM,最小值minNUM 形成KEY {minNUM,maxNUM} 然后在桶里查找這個KEY {minNUM,maxNUM},如果沒找到,則將這個KEY存入桶里并遞增計數(shù)1 ,找到了就在對應的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ù)學 n * (n - 1) // 2 求每種骨牌成對的數(shù)目,將其累加得到最后結果。

圖解:

代碼:

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,降成一維數(shù)組以后就可以利用哈希表統(tǒng)計頻數(shù),因為元素翻轉相同或者不反轉相同都是等價的,所以可以利用高斯求和公式計算每個頻數(shù)超過1的元素的數(shù)量,再將所以數(shù)量相加即為結果。

代碼

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

復雜度分析

時間復雜度:O(N)

空間復雜度:O(N)

以上就是go語言題解LeetCode1128等價多米諾骨牌對的數(shù)量的詳細內容,更多關于go題解等價多米諾骨牌數(shù)量的資料請關注腳本之家其它相關文章!

相關文章

  • GO中sync包自由控制并發(fā)示例詳解

    GO中sync包自由控制并發(fā)示例詳解

    這篇文章主要為大家介紹了GO中sync包自由控制并發(fā)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2022-08-08
  • Go語言讀取文本文件的三種方式總結

    Go語言讀取文本文件的三種方式總結

    工作中時不時需要讀取文本,文本文件是最常見的文件類型。本文將利用Go語言從逐行、逐個單詞和逐個字符三個方法讀取文件,感興趣的可以了解一下
    2023-01-01
  • Go語言實現(xiàn)選擇法排序實例

    Go語言實現(xiàn)選擇法排序實例

    這篇文章主要介紹了Go語言實現(xiàn)選擇法排序的方法,實例分析了選擇法排序的實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-02-02
  • Go結合反射將結構體轉換成Excel的過程詳解

    Go結合反射將結構體轉換成Excel的過程詳解

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

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

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

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

    本文主要介紹了Go安裝和環(huán)境配置圖文教程,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    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用法,較為詳細的分析了GO語言的特性與具體用法,并給出了一個比較典型的應用實例,具有一定的參考借鑒價值,需要的朋友可以參考下
    2014-12-12
  • Go語言的互斥鎖的詳細使用

    Go語言的互斥鎖的詳細使用

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

    golang數(shù)據(jù)結構之golang稀疏數(shù)組sparsearray詳解

    這篇文章主要介紹了golang數(shù)據(jù)結構之golang稀疏數(shù)組sparsearray的相關知識,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09

最新評論