刷题打卡，第 二十七 天
题目、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.提交代码：
classSolution{publicintminSwap(int[] nums1,int[] nums2){int len = nums1.length;//获取数组长度//创建一个二维数组，每个元素数组存放两个值 arr[][0] 和 arr[][1];//其中arr[][0]代表当前位置不发生交换时，累计操作的次数//其中arr[][1]代表当前位置发生交换时，累计操作的次数int[][] arr =newint[len][2];//数组第一个位置的元素操作
arr[0][0]=0;//不发生交换，累计次数0
arr[0][1]=1;//若发生交换，累计次数1for(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}//当前位置交换，前面的位置必须交换；当前位置不交换，前面位置也是不交换的elseif(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，前面是不进行操作的}}returnMath.min(arr[len-1][0],arr[len-1][1]);//返回最小的操作次数}}
4.提交结果：
⚽
求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，
收藏以及
关注是对作者最大的鼓励喔 ~~
版权归原作者 .29. 所有， 如有侵权，请联系我们删除。