【Day27】 LeetCode算法刷题（思路+注释）[801. 使序列递增的最小交换次数 ]
【Day27】 LeetCode算法刷题（思路+注释）[801. 使序列递增的最小交换次数 ]
刷题打卡，第 二十七 天
题目、801. 使序列递增的最小交换次数
原题链接：801. 使序列递增的最小交换次数
1.题目描述：
我们有两个长度相等且不为空的整型数组 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[i-1] < nums1[i] 且 nums2[i-1] < nums2[i]， ②nums1[i-1] < nums2[i] 且 nums2[i-1] < nums1[i]。
1.满足① 也 满足② 2.满足①但不满足② 3.不满足①也不满足②
我们创建一个二维数组int[][] arr = new int[nums1.length][2];
arr[i][0]记录不进行交换操作累计的操作次数
arr[i][1]记录进行交换而累计的操作次数
当我们遇到情况一： 选择交换，则操作次数+1，且前一个位置可以是交换的也可以是不交换的,那我们就次数较少的。 选择不交换，前一个位置依旧可以是交换的也可以是不交换的，选择同上。
当我们遇到情况二：
选择交换，操作次数+1，前一个位置必须也是交换的,即：arr[i-1][1]
选择不交换，前一个位置也是不交换的,即：arr[i-1][0]
当遇到情况三：
选择交换，操作次数+1，前一个位置是不交换的，即：arr[i-1][0]
选择不交换，前一个位置是交换了的，即：arr[i-1][1]
当我们按照上面的操作遍历完，返回较小的操作数即可，这边代表了使序列递增的最小交换次数 .
3.提交代码：
class Solution {
public int minSwap(int[] nums1, int[] nums2) {
int len = nums1.length; //获取数组长度
//创建一个二维数组，每个元素数组存放两个值 arr[][0] 和 arr[][1];
//其中arr[][0]代表当前位置不发生交换时，累计操作的次数
//其中arr[][1]代表当前位置发生交换时，累计操作的次数
int[][] arr = new int[len][2];
//数组第一个位置的元素操作
arr[0][0] = 0; //不发生交换，累计次数0
arr[0][1] = 1; //若发生交换，累计次数1
for(int i = 1;i <len;++i){
int a1 = nums1[i-1],a2 = nums1[i]; //a系列代表nums1数组前后位置元素
int b1 = nums2[i-1],b2 = nums2[i]; //b系列代表nums2数组前后位置元素
//当前位置不交换，前面位置的元素可交换也可不交换，若交换亦然
if(a1 < a2 && b1 < b2 && (a1 < b2 && b1 < a2)){
arr[i][0] = Math.min(arr[i-1][0],arr[i-1][1]); //当前不交换，前面可任选，选最少的
arr[i][1] = arr[i][0] + 1; //交换，次数+1
}
//当前位置交换，前面的位置必须交换；当前位置不交换，前面位置也是不交换的
else if(a1 < a2 && b1 < b2){
arr[i][0] = arr[i-1][0]; //不交换，前置必须是不进行操作
arr[i][1] = arr[i-1][1] + 1;//交换,次数+1，前置必须是交换操作
}
//当前元素若交换，前置是不操作的；当前位置不交换，前置是交换操作的
else{
arr[i][0] = arr[i-1][1]; //当前不见换，前面是交换操作
arr[i][1] = arr[i-1][0] + 1; //交换，次数+1，前面是不进行操作的
}
}
return Math.min(arr[len-1][0],arr[len-1][1]); //返回最小的操作次数
}
}4.提交结果：
腾讯云开发者
