动态规划，求解《801. 使序列递增的最小交换次数》
例题
801. 使序列递增的最小交换次数
我们有两个长度相等且不为空的整型数组 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 <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 105
答案
动态规划
交换时：要么交换 i - 1 位置，要么交换 i 位置
var minSwap = function(nums1, nums2) {
const n = nums1.length
let a = 0, b = 1
for (let i = 1; i < n; i++) {
const la = a, lb = b
a = b = n
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la
b = lb + 1
}
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
a = Math.min(a, lb)
b = Math.min(b, la + 1)
}
}
return Math.min(a, b)
};function minSwap(nums1: number[], nums2: number[]): number {
const n = nums1.length
let a = 0, b = 1
for (let i = 1; i < n; i++) {
const la = a, lb = b
a = b = n
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la
b = lb + 1
}
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
a = Math.min(a, lb)
b = Math.min(b, la + 1)
}
}
return Math.min(a, b)
};class Solution {
function minSwap($nums1, $nums2) {
$n = count($nums1);
$a = 0;
$b = 1;
for ($i = 1; $i < $n; $i++) {
$la = $a;
$lb = $b;
$a = $b = $n;
if ($nums1[$i] > $nums1[$i - 1] && $nums2[$i] > $nums2[$i - 1]) {
$a = $la;
$b = $lb + 1;
}
if ($nums2[$i] > $nums1[$i - 1] && $nums1[$i] > $nums2[$i - 1]) {
$a = min($a, $lb);
$b = min($b, $la + 1);
}
}
return min($a, $b);
}
}func minSwap(nums1 []int, nums2 []int) int {
n, a, b := len(nums1), 0, 1
for i := 1; i < n; i++ {
la, lb := a, b
a, b = n, n
if nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1] {
a, b = la, lb + 1
}
if nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1] {
a, b = min(a, lb), min(b, la + 1)
}
}
return min(a, b)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}class Solution {
public int minSwap(int[] nums1, int[] nums2) {
int n = nums1.length, a = 0, b = 1;
for (int i = 1; i < n; i++) {
int la = a, lb = b;
a = b = n;
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la;
b = lb + 1;
}
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
a = Math.min(a, lb);
b = Math.min(b, la + 1);
}
}
return Math.min(a, b);
}
}public class Solution {
public int MinSwap(int[] nums1, int[] nums2) {
int n = nums1.Length, a = 0, b = 1;
for (int i = 1; i < n; i++) {
int la = a, lb = b;
a = b = n;
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la;
b = lb + 1;
}
if (nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1]) {
a = Math.Min(a, lb);
b = Math.Min(b, la + 1);
}
}
return Math.Min(a, b);
}
}#define MIN(a, b) (a < b ? a : b)
int minSwap(int* nums1, int nums1Size, int* nums2, int nums2Size){
int a = 0, b = 1;
for (int i = 1; i < nums1Size; i++) {
int la = a, lb = b;
a = b = nums1Size;
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la;
b = lb + 1;
}
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
a = MIN(a, lb);
b = MIN(b, la + 1);
}
}
return MIN(a, b);
}class Solution {
public:
int minSwap(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), a = 0, b = 1;
for (int i = 1; i < n; i++) {
int la = a, lb = b;
a = b = n;
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = la;
b = lb + 1;
}
if (nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1]) {
a = min(a, lb);
b = min(b, la + 1);
}
}
return min(a, b);
}
};class Solution:
def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
n, a, b = len(nums1), 0, 1
for i in range(1, n):
la, lb = a, b
a, b = n, n
if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]: a, b = la, lb + 1
if nums2[i] > nums1[i - 1] and nums1[i] > nums2[i - 1]: a, b = min(a, lb), min(b, la + 1)
return min(a, b)