共计 4102 个字符,预计需要花费 11 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 801. 使序列递增的最小替换次数 ,难度为 艰难。
Tag :「状态机 DP」、「动静布局」
咱们有两个长度相等且不为空的整型数组 nums1
和 nums2
。
在一次操作中,咱们能够替换 $nums1[i]$ 和 $nums2[i]$ 的元素。
例如,如果 $nums1 = [1,2,3,8]$,$nums2 =[5,6,7,4]$,你能够替换 $i = 3$ 处的元素,失去 $nums1 =[1,2,3,4]$ 和 $nums2 =[5,6,7,8]$。
返回 使 nums1
和 nums2
严格递增 所需操作的最小次数。
数组 arr
严格递增 且 $arr[0] < arr[1] < arr[2] < … < arr[arr.length – 1]$。
留神:
用例保障能够实现操作。
示例 1:
输出: nums1 = [1,3,5,4], nums2 = [1,2,3,7] | |
输入: 1 | |
解释: | |
替换 A[3] 和 B[3] 后,两个数组如下: | |
A = [1, 3, 5, 7],B = [1, 2, 3, 4] | |
两个数组均为严格递增的。 |
示例 2:
输出: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9] | |
输入: 1 |
提醒:
- $2 <= nums1.length <= 10^5$
- $nums2.length = nums1.length$
- $0 <= nums1[i], nums2[i] <= 2 * 10^5$
根本剖析
这是一道很裸的状态机 DP 使用题。
因为每次替换只会产生在两数组的雷同地位上,使得问题变得简略:仅需思考替换以后地位后,以后元素与前后元素大小关系变动即可。
又因为咱们会从前往后解决每个地位,因而只须要思考以后地位与前一地位的大小关系即可。
状态机 DP
定义 $f[i][j]$ 为思考下标范畴为 $[0, i]$ 的元素,且地位 $i$ 的替换状态为 $j$ 时(其中 $j = 0$ 为不替换,$j = 1$ 为替换)两数组满足严格递增的最小替换次数。
最终答案为 $\min(f[n – 1][0], f[n – 1][1])$,同时咱们有不言而喻的初始化条件 $f[0][0] = 0$ 和 $f[0][1] = 1$,其余未知状态初始化为正无穷。
不失一般性思考 $f[i][j]$ 该如何转移:
- 若 $nums1[i] > nums1[i – 1]$ 且 $nums2[i] > nums2[i – 1]$(即程序位满足要求),此时要么以后地位 $i$ 和前一地位 $i – 1$ 都不替换,要么同时产生替换,此时有(别离对应两个地位「都不替换」和「都替换」):
$$ \begin{cases}
fi = fi – 1 \
fi = fi – 1 + 1
\end{cases}$$
- 若 $nums1[i] > nums2[i – 1]$ 且 $nums2[i] > nums1[i – 1]$(即穿插位满足要求),此时以后地位 $i$ 和前一地位 $i – 1$ 只能有其一产生替换,此时有(别离对应「前一地位替换」和「以后地位替换」):
$$ \begin{cases}
fi = \min(fi, fi – 1); \
fi = \min(fi, fi – 1 + 1)
\end{cases}$$
Java 代码:
class Solution {public int minSwap(int[] nums1, int[] nums2) { | |
int n = nums1.length; | |
int[][] f = new int[n][2]; | |
for (int i = 1; i < n; i++) f[i][0] = f[i][1] = n + 10; | |
f[0][1] = 1; | |
for (int i = 1; i < n; i++) {if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {f[i][0] = f[i - 1][0]; | |
f[i][1] = f[i - 1][1] + 1; | |
} | |
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {f[i][0] = Math.min(f[i][0], f[i - 1][1]); | |
f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1); | |
} | |
} | |
return Math.min(f[n - 1][0], f[n - 1][1]); | |
} | |
} |
TypeScript 代码:
function minSwap(nums1: number[], nums2: number[]): number { | |
const n = nums1.length | |
const f = new Array<Array<number>>(n) | |
f[0] = [0, 1] | |
for (let i = 1; i < n; i++) f[i] = [n + 10, n + 10] | |
for (let i = 1; i < n; i++) {if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {f[i][0] = f[i - 1][0] | |
f[i][1] = f[i - 1][1] + 1 | |
} | |
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {f[i][0] = Math.min(f[i][0], f[i - 1][1]) | |
f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1) | |
} | |
} | |
return Math.min(f[n - 1][0], f[n - 1][1]) | |
} |
Python 代码:
class Solution: | |
def minSwap(self, nums1: List[int], nums2: List[int]) -> int: | |
n = len(nums1) | |
f = [[0, 0] for _ in range(n)] | |
for i in range(1, n): | |
f[i][0] = f[i][1] = n + 10 | |
f[0][1] = 1 | |
for i in range(1, n): | |
if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]: | |
f[i][0], f[i][1] = f[i - 1][0], f[i - 1][1] + 1 | |
if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]: | |
f[i][0], f[i][1] = min(f[i][0], f[i - 1][1]), min(f[i][1], f[i - 1][0] + 1) | |
return min(f[n - 1][0], f[n - 1][1]) |
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
滚动数组
利用 $f[i][X]$ 仅依赖于 $f[i – 1][X]$,咱们能够采纳「滚动数组」的形式,通过机械性操作将空间优化到 $O(1)$。
Java 代码:
class Solution {public int minSwap(int[] nums1, int[] nums2) { | |
int n = nums1.length; | |
int[][] f = new int[2][2]; | |
f[0][1] = 1; | |
for (int i = 1; i < n; i++) { | |
int a = n + 10, b = n + 10; | |
int prev = (i - 1) & 1, cur = i & 1; // 防止反复的 & 操作 | |
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {a = f[prev][0]; | |
b = f[prev][1] + 1; | |
} | |
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {a = Math.min(a, f[prev][1]); | |
b = Math.min(b, f[prev][0] + 1); | |
} | |
f[cur][0] = a; f[cur][1] = b; | |
} | |
return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]); | |
} | |
} |
TypeScript 代码:
function minSwap(nums1: number[], nums2: number[]): number { | |
const n = nums1.length | |
const f = new Array<Array<number>>(2) | |
f[0] = [0, 1], f[1] = [0, 0] | |
for (let i = 1; i < n; i++) { | |
let a = n + 10, b = n + 10 | |
const prev = (i - 1) & 1, cur = i & 1 | |
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {a = f[prev][0] | |
b = f[prev][1] + 1 | |
} | |
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {a = Math.min(a, f[prev][1]) | |
b = Math.min(b, f[prev][0] + 1) | |
} | |
f[cur][0] = a; f[cur][1] = b | |
} | |
return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]) | |
} |
Python 代码:
class Solution: | |
def minSwap(self, nums1: List[int], nums2: List[int]) -> int: | |
n = len(nums1) | |
f = [[0, 1], [0, 0]] | |
for i in range(1, n): | |
a, b = n + 10, n + 10 | |
prev, cur = (i - 1) & 1, i & 1 | |
if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]: | |
a, b = f[prev][0], f[prev][1] + 1 | |
if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]: | |
a, b = min(a, f[prev][1]), min(b, f[prev][0] + 1) | |
f[cur][0], f[cur][1] = a, b | |
return min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]) |
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.801
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布