ETH官方钱包

前往
大廳
主題

LeetCode - 1128. Number of Equivalent Domino Pairs 解題心得

Not In My Back Yard | 2021-03-27 00:00:13 | 巴幣 0 | 人氣 231

題目連結:


題目意譯:
給定一個多米諾骨牌列表 dominoes,dominoes[i] = [a, b] 等價於 dominoes[j] = [c, d] 若且唯若(a == c 且 b == d) 或者是 (a == d 且 b == c),也就是說一個多米諾骨牌可以旋轉而等於另一個骨牌。

回傳 (i, j) 數對,其 0 ≦ i < j < dominoes.length 且 dominoes[i] 等價於 dominoes[j]

限制:
1 ≦ dominoes.length ≦ 40000
1 ≦ dominoes[i][j] ≦ 9



範例測資:
輸入: dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出: 1


解題思維:
將所有多米諾骨牌 [a, b] 統一轉成 a ≦ b 之形式。然後將所有骨牌用雜湊表(Hash Table)儲存起來並計算每一種的數量。

接著對於每一種骨牌之數量 C ,該種骨牌可以貢獻 C × (C - 1) ÷ 2 種可行的 (i, j) 數對。將這些貢獻數量加總即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作