# 1128. 等价多米诺骨牌对的数量
## 题目地址（1128. 等价多米诺骨牌对的数量）
## 题目描述
```
给你一个由一些多米诺骨牌组成的列表 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) 的数量。
示例：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1
提示：
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
```
## 前置知识
* 组合计数
## “排序” + 计数
### 思路
我们可以用一个哈希表存储所有的 \[a,b] 对的计数信息。为了让形如 \[3,4] 和 \[4,3]被算到一起，我们可以对其进行排序处理。由于 dominoe 长度固定为 2，因此只需要**判断两者的大小并选择性交换即可**。
接下来，可以使用组合公式 $C*{n}^{2}$ 计算等价骨牌对的数量，其中 n 为单个骨牌的数量。 比如**排序后** \[3,4] 骨牌对有 5 个，那么 n 就是 5，由 \[3,4]构成的等价骨牌对的数量就是 $C*{5}^{2} = 5\times(5-1)\div2 = 10$ 个。
### 代码
代码支持：Python3
Python3 Code:
```python
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
n = len(dominoes)
cnt = 0
cntMapper = dict()
for a, b in dominoes:
k = str(a) + str(b) if a > b else str(b) + str(a)
cntMapper[k] = cntMapper.get(k, 0) + 1
for k in cntMapper:
v = cntMapper[k]
if v > 1:
cnt += (v * (v - 1)) // 2
return cnt
```
**复杂度分析**
令 N 为数组长度。
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
## 状态压缩 + 一次遍历
### 思路
观察到题目给的数据范围是 `1 <= dominoes[i][j] <= 9`。这个数字很小，很容易让人想到状态压缩。关于状态压缩这部分可以看我之前写过的题解[状压 DP 是什么？这篇题解带你入门](https://mp.weixin.qq.com/s/ecxTTrRvUJbdWwSFbKgDiw)
由于数字不会超过 9，因此使用一个 5 bit 表示就足够了。
我们可以用两个 5 bit 分别表示 a 和 b，即一共 10 个 bit 就够了。10 个 bit 一共最多 1024 种状态，因此使用一个 1024 大小的数组是足够的。
上面代码我们是先进行一次遍历，求出计数信息。然后再次遍历计算总和。实际上，我们可以将两者合二为一，专业的话来说就是 **One Pass**，中文是一次遍历。
注意到我们前面计算总和用到了组合公式 $C\_{n}^{2}$，等价于 $n\times(n-1)\div{2}$，这其实就是等差数列 `1,2,3....n-1`的求和公式。同时注意到我们的计数信息也是每次增加 1 的，即从 0 -> 1, 1 -> 2, n - 1 -> n。也就是说**我们的计数信息其实就是公差为 1 的等差数列，正好对应前面写的等差数列**。那我们是不是可以从 1 开始累加计数信息，直到 n -1（注意不是 n）。
> 力扣中有好几个题目都使用到了这种 One Pass 技巧。
### 代码
代码支持：Python3
Python3 Code:
```python
counts = [0] * 1024
ans = 0
for a, b in dominoes:
if a >= b: v = a <<5 | b
else: v = b << 5 | a
ans += counts[v]
counts[v] += 1
return ans
```
**复杂度分析**
令 N 为数组长度。
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1024)$
## 状态压缩优化
### 思路
代码上，我使用了 int 来存储，因此实际上会用 32 个字节（取决于不同的编程语言），这并没有发挥二进制的状态压缩的优点。由于 `1 <= dominoes[i][j] <= 9`，我们也可直接用 9 进制来存，刚好 `9 * 9 = 81` 种状态。 这样开辟一个大小为 81 的数组即可。
### 代码
代码支持：Python3
Python3 Code:
```python
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
counts = [0] * 9 * 9
ans = 0
for a, b in dominoes:
v = min((a - 1) * 9 + (b - 1), (b - 1) * 9 + (a - 1))
ans += counts[v]
counts[v] += 1
return ans
```
**复杂度分析**
令 N 为数组长度。
* 时间复杂度：$O(N)$
* 空间复杂度：$O(81)$
## 关键点
* 使用状态压缩可提高性能
* 使用求和公式技巧可在一次遍历内计算结果
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/1128.number-of-equivalent-domino-pairs.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.