有两个具有相同非零长度的整数序列A和B。可以交换它们的一些元素A[i]和B[i]。 注意，两个可交换的元素在它们各自的序列中处于相同的索引位置。进行一些交换之后，A和B需要严格递增。 （当且仅当A[0] < A[1] < A[2] < ... < A[A.length - 1]时，序列严格递增。）
给定A和B，返回使两个序列严格递增的最小交换次数。 保证给定的输入经过交换可以满足递增的条件。
minimum-swaps-to-make-sequences-increasing
样例
样例 1:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释: 交换A[3] and B[3]. 两个序列变为:
A = [1,3,5,7] 和 B = [1,2,3,4],
此时它们都是严格递增的。
样例 2:
输入: A = [2,4,5,7,10], B = [1,3,4,5,9]
输出: 0
题目是保证有解的
思路1、使用动态规划
index 0 1 2 3 4
A 1 3 5 4 9
B 1 2 3 7 10
dp[index][0] 0 0 0 2 1
dp[index][1] 1 1 2 1 2
思路2 跟思路1 差不多
index 0 1 2 3 4
A 1 3 5 4 9
B 1 2 3 7 10
swapRecord 1 1 2 1 2
fixRecord 0 0 0 2 1
记录 swapRecord fixRecord的值
具体代码试下如下
public class Solution {
/**
* @param a: an array
* @param b: an array
* @return: the minimum number of swaps to make both sequences strictly increasing
*/
public int minSwap(int[] a, int[] b) {
// Write your code here
if(a.length == 0){
return 0;
}
int[][] dp = new int[a.length][2];
dp[0][0] = 0;
dp[0][1] = 1;
for (int i = 1; i < dp.length; i++) {
if (a[i - 1] >= b[i] || b[i - 1] >= a[i]) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1] + 1;
} else if (a[i - 1] >= a[i] || b[i - 1] >= b[i]) {
dp[i][1] = dp[i - 1][0] + 1;
dp[i][0] = dp[i - 1][1];
} else {
int min = Math.min(dp[i - 1][0], dp[i - 1][1]);
dp[i][0] = min;
dp[i][1] = min + 1;
}
}
return Math.min(dp[dp.length - 1][0], dp[dp.length - 1][1]);
}
}
public class Solution {
public int minSwap(int[] a, int[] b) {
int swapRecord = 1;
int fixRecord = 0;
for (int i = 1; i < a.length; i++) {
if (a[i - 1] >= b[i] || b[i - 1] >= a[i]) {
swapRecord++;
} else if (a[i - 1] >= a[i] || b[i - 1] >= b[i]) {
int temp = swapRecord;
swapRecord = fixRecord + 1;
fixRecord = temp;
} else {
int min = Math.min(swapRecord, fixRecord);
swapRecord = min + 1;
fixRecord = min;
}
}
return Math.min(swapRecord, fixRecord);
}
}
