难度: Easy
给你一组多米诺骨牌 dominoes 。
形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。
在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
示例 1：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]] 输出：1
示例 2：
输入：dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]] 输出：3
提示：
1 <= dominoes.length <= 4 * 104dominoes[i].length == 21 <= dominoes[i][j] <= 9运行时间: 28 ms
内存: 22.9 MB
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
num = [0] * 100
ret = 0
for x, y in dominoes:
val = (x * 10 + y if x <= y else y * 10 + x)
ret += num[val]
num[val] += 1
return ret
本题目的主要思路是使用哈希表来统计每种多米诺骨牌出现的次数。首先，对于每一对多米诺骨牌 [x, y]，为了避免旋转后的等价性问题，我们首先将每对多米诺骨牌按照元素大小排序，确保较小的数字总是在前。这样，每一对可以唯一地表示为两位数 val = min(x, y) * 10 + max(x, y)。利用一个长度为 100 的数组 num 来统计每种 val 的出现次数。对于每一对多米诺骨牌，如果它在之前已经出现过，那么它能与之前的每一对形成一个新的等价对。因此，每次遇到同样的 val，当前的等价对数就是 val 已经出现的次数，我们把这个数累加到结果 ret 中。随后，更新这个 val 的出现次数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
num = [0] * 100 # 初始化计数器，用于记录每种多米诺骨牌组合出现的次数
ret = 0 # 初始化结果变量，用于累计等价多米诺骨牌对的数量
for x, y in dominoes: # 遍历每一对多米诺骨牌
val = (x * 10 + y if x <= y else y * 10 + x) # 确保每对多米诺骨牌的小数字在前，大数字在后
ret += num[val] # 将当前 val 对应的已出现次数加到结果中，因为每个之前的出现都能与当前这一对形成一个新的等价对
num[val] += 1 # 更新当前多米诺骨牌组合的出现次数
return ret # 返回总的等价多米诺骨牌对数
将多米诺骨牌的数对转换成一个两位数进行表示的主要原因是为了简化查找和存储过程。使用两位数可以直接通过简单的数组索引来访问和记录每种组合的出现次数，这比使用哈希表或元组更为高效和直接。数组的访问时间复杂度为O(1)，而哈希表虽然平均情况下也提供O(1)的访问时间，但在最坏情况下会退化到O(n)。此外，使用两位数可以避免哈希冲突并减少内存使用。
使用公式 `val = min(x, y) * 10 + max(x, y)` 不会造成不同的多米诺骨牌对应同一个 val 值。这是因为，公式首先确定了较小的数字作为十位数，较大的数字作为个位数，确保了每个多米诺骨牌对都有一个唯一的表示。例如，无论是多米诺骨牌 [2, 5] 还是 [5, 2]，它们都将被表示为 25，确保了表示的唯一性。
数组长度为 100 是足够的，因为多米诺骨牌的每个数值最大为 9（通常情况下），因此使用前述公式 `val = min(x, y) * 10 + max(x, y)`，最大的 val 值为 99。这样的表示方法确保了所有可能的多米诺骨牌组合都能在数组长度为 100 的数组中得到记录，不会存在溢出或冲突的情况。
这种方法确实考虑了多米诺骨牌之间的不同组合次数，包括同样的多米诺骨牌重复出现的情况。每次遇到一个多米诺骨牌对，算法通过将其转换成唯一的数值 val 并记录在数组中。如果同样的 val 再次出现，其对应的数组值（即之前出现的次数）就会被加到结果中。这意味着每个多米诺骨牌对的每一次出现都将与之前的每一次出现形成新的等价对，因此可以正确地计算出所有可能的等价多米诺骨牌对的总数。