feat: $801

lucifer · lucifer · commit 2cddbca672c6 · 2021-02-15T20:01:32.000+08:00
diff --git a/README.md b/README.md
@@ -324,6 +324,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0754. 到达终点数字](./problems/754.reach-a-number.md)
 - [0785. 判断二分图](./problems/785.is-graph-bipartite.md)
 - [0799. 香槟塔](./problems/799.champagne-tower.md) 🆕
+- [0801. 使序列递增的最小交换次数](./problems/801.minimum-swaps-to-make-sequences-increasing.md) 🆕
 - [0816. 模糊坐标](./problems/816.ambiguous-coordinates.md)
 - [0820. 单词的压缩编码](./problems/820.short-encoding-of-words.md)
 - [0875. 爱吃香蕉的珂珂](./problems/875.koko-eating-bananas.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -188,6 +188,7 @@
   - [0754. 到达终点数字](./problems/754.reach-a-number.md)
   - [0785. 判断二分图](./problems/785.is-graph-bipartite.md)
   - [0799. 香槟塔](./problems/799.champagne-tower.md) 🆕
+  - [0801. 使序列递增的最小交换次数](./problems/801.minimum-swaps-to-make-sequences-increasing.md) 🆕
   - [0816. 模糊坐标](./problems/816.ambiguous-coordinates.md)
   - [0820. 单词的压缩编码](./problems/820.short-encoding-of-words.md)
   - [0875. 爱吃香蕉的珂珂](./problems/875.koko-eating-bananas.md)
diff --git a/problems/801.minimum-swaps-to-make-sequences-increasing.md b/problems/801.minimum-swaps-to-make-sequences-increasing.md
@@ -0,0 +1,175 @@
+## 题目地址(801. 使序列递增的最小交换次数)
+
+https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing/
+
+## 题目描述
+
+```
+我们有两个长度相等且不为空的整型数组 A 和 B 。
+
+我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
+
+在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
+
+给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
+
+示例:
+输入: A = [1,3,5,4], B = [1,2,3,7]
+输出: 1
+解释:
+交换 A[3] 和 B[3] 后，两个数组如下:
+A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
+两个数组均为严格递增的。
+
+注意:
+
+A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
+A[i], B[i] 均为 [0, 2000]区间内的整数。
+```
+
+## 前置知识
+
+- 动态规划
+
+## 公司
+
+- 暂无
+
+## 思路
+
+要想解决这道题，需要搞定两个关键点。
+
+### 关键点一：无需考虑全部整体，而只需要考虑相邻两个数字即可
+
+这其实也是可以使用动态规划解决问题的关键条件。对于这道题来说，**最小**的子问题就是当前项和前一项组成的局部，**无法**再小了，**没有必要**再大了。
+
+为什么只关心两个数字即可？因为要使得整个数组递增，**假设**前面的 i - 2 项已经满足递增了，那么现在**采取某种方式**使得满足 A[i] > A[i-1] 即可(B 也是同理)。
+
+> 因为 A[i - 1] > A[i-2] 已经成立，因此如果 A[i] > A[i - 1]，那么整体就递增了。
+
+这提示我们可以使用动态规划来完成。 如果上面的这些没有听懂，则很有可能对动态规划不熟悉，建议先看下基础知识。
+
+### 关键点二：相邻两个数字的大小关系有哪些？
+
+由于题目一定有解，因此交换相邻项中的**一个或两个**一定能满足**两个数组都递增**的条件。换句话说，如下的情况是不可能存在的：
+
+```
+A:[1,2,4]
+B:[1,5,1]
+```
+
+因为无论怎么交换都无法得到两个递增的序列。那相邻数字的大小关系究竟有哪些呢？实际上大小关系一共有四种。为了描述方便，先列举两个条件，之后直接用 q1 和 q2 来引用这两个关系。
+
+```
+q1：A[i-1] < A[i] and B[i-1] < B[i]
+q2：A[i-1] < B[i] and B[i-1] < A[i]
+```
+
+- q1 表示的是两个数组本身就已经递增了，你**可以选择**不交换。
+- q2 表示的是两个数组必须进行一次交换，你**可以选择**交换 i 或者交换 i - 1。
+
+铺垫已经有了，接下来我们来看下这四种关系。
+
+关系一：q1 满足 q2 满足。换不换都行，换 i 或者 i - 1 都行, 也可以都换
+
+关系二：q1 不满足 q2 不满足。无解，对应上面我举的不可能存在的情况
+
+关系三：q1 满足 q2 不满足。换不换都行，但是如果换需要都换。
+
+关系四：q1 不满足 q2 满足 。必须换，换 i 或者 i - 1
+
+接下来按照上面的四种关系进行模拟即可解决。
+
+## 关键点
+
+- 无需考虑全部整体，而只需要考虑相邻两个数字即可
+- 分情况讨论
+- 从题目的**一定有解**条件入手
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```py
+
+class Solution:
+    def minSwap(self, A: List[int], B: List[int]) -> int:
+        n = len(A)
+        swap = [n] * n
+        no_swap = [n] * n
+        swap[0] = 1
+        no_swap[0] = 0
+
+        for i in range(1, len(A)):
+            q1 = A[i-1] < A[i] and B[i-1] < B[i]
+            q2 = A[i-1] < B[i] and B[i-1] < A[i]
+            if q1 and q2:
+                no_swap[i] = min(swap[i-1], no_swap[i-1]) # 都不换或者换i-1
+                swap[i] = min(swap[i-1], no_swap[i-1]) + 1 # 都换 或者 换 i
+            if q1 and not q2:
+                swap[i] = swap[i-1] + 1 # 都换
+                no_swap[i] = no_swap[i-1] # 都不换
+            if not q1 and q2:
+                swap[i] = no_swap[i-1] + 1 # 换 i
+                no_swap[i] = swap[i-1] # 换 i - 1
+
+        return min(swap[n-1], no_swap[n-1])
+```
+
+实际上，我们也可以将逻辑进行合并，这样代码更加简洁。力扣中国题解区很多都是这种写法。即：
+
+```py
+if q1:
+    no_swap[i] = no_swap[i-1] # 都不换
+    swap[i] = swap[i-1] + 1 # 都换
+if q2:
+    swap[i] = min(swap[i], no_swap[i-1] + 1) # 换 i
+    no_swap[i] =  min(no_swap[i], swap[i-1]) # 换 i - 1
+```
+
+可以看出，这种写法和上面逻辑是一致的。
+
+逻辑合并之后的代码，更简短。但由于两个分支可能都执行到，因此不太容易直接写出。
+
+代码：
+
+```py
+class Solution:
+    def minSwap(self, A: List[int], B: List[int]) -> int:
+        n = len(A)
+        swap = [n] * n
+        no_swap = [n] * n
+        swap[0] = 1
+        no_swap[0] = 0
+
+        for i in range(1, len(A)):
+            # 如果交换之前有序，则可以不交换
+            if A[i-1] < A[i] and B[i-1] < B[i]:
+                no_swap[i] = no_swap[i-1]
+                swap[i] = swap[i-1] + 1
+            # 否则至少需要交换一次（交换当前项或者前一项）
+            if A[i-1] < B[i] and B[i-1] < A[i]:
+                swap[i] = min(swap[i], no_swap[i-1] + 1) # i 换
+                no_swap[i] =  min(no_swap[i], swap[i-1]) # i - 1 换
+
+        return min(swap[n-1], no_swap[n-1])
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(n)$
+- 空间复杂度：$O(n)$
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
