刷题打卡，第 二十七 天
题目、801. 使序列递增的最小交换次数
1.`题目描述`：
2.`解题思路`：
3.`提交代码`：
4.`提交结果`：
题目、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.提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
