題目連結:
題目意譯:
給定一個多米諾骨牌列表 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) 數對。將這些貢獻數量加總即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。