feat: $1128

lucifer · lucifer · commit 3efa91acf156 · 2021-01-26T11:20:07.000+08:00
diff --git a/README.md b/README.md
@@ -216,6 +216,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0575. 分糖果](./problems/575.distribute-candies.md)
 - [821. 字符的最短距离](./problems/821.shortest-distance-to-a-character.md) 91
 - [0874. 模拟行走机器人](./problems/874.walking-robot-simulation.md)
+- [1128. 等价多米诺骨牌对的数量](./problems/1128.number-of-equivalent-domino-pairs.md) 🆕
 - [1260. 二维网格迁移](./problems/1260.shift-2d-grid.md)
 - [1332. 删除回文子序列](./problems/1332.remove-palindromic-subsequences.md)
 
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -87,6 +87,7 @@
     * [0575. 分糖果](problems/575.distribute-candies.md)
     * [821. 字符的最短距离](problems/821.shortest-distance-to-a-character.md) 91
     * [0874. 模拟行走机器人](problems/874.walking-robot-simulation.md)
+    * [1128. 等价多米诺骨牌对的数量](./problems/1128.number-of-equivalent-domino-pairs.md) 🆕
     * [1260. 二维网格迁移](problems/1260.shift-2d-grid.md)
     * [1332. 删除回文子序列](problems/1332.remove-palindromic-subsequences.md)
 
diff --git a/problems/1128.number-of-equivalent-domino-pairs.md b/problems/1128.number-of-equivalent-domino-pairs.md
@@ -0,0 +1,152 @@
+## 题目地址（1128. 等价多米诺骨牌对的数量）
+
+https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/
+
+## 题目描述
+
+```
+
+给你一个由一些多米诺骨牌组成的列表 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 "状压 DP 是什么？这篇题解带你入门")
+
+由于数字不会超过 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:
+            if a >= b: v = a * 9 + b
+            else: v = b * 9 + a
+            ans += counts[v]
+            counts[v] += 1
+        return ans
+```
+
+**复杂度分析**
+
+令 N 为数组长度。
+
+- 时间复杂度：$$O(N)$$
+- 空间复杂度：$$O(81)$$
+
+## 关键点
+
+- 使用状态压缩可提高性能
+- 使用求和公式技巧可在一次遍历内计算结果
