做一个在线支付网站,成都微网站公司,品牌展示型网站有哪些,做游戏下载网站赚钱1. 题目
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后#xff0c;数组 A 和 B 都应该是严格递增的#xff08;数组严格递增的条件仅为A[0] A[1] …1. 题目
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后数组 A 和 B 都应该是严格递增的数组严格递增的条件仅为A[0] A[1] A[2] … A[A.length - 1]。
给定数组 A 和 B 请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例:
输入: A [1,3,5,4], B [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后两个数组如下:
A [1, 3, 5, 7] B [1, 2, 3, 4]
两个数组均为严格递增的。注意:
A, B 两个数组的长度总是相等的且长度的范围为 [1, 1000]。
A[i], B[i] 均为 [0, 2000]区间内的整数。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
每一个位置有两种状态换 or 不换dp[i][0]表示不换dp[i][1]表示换数值存储最少次数初始化dp[0][0] 0;、dp[0][1] 1;A[i]A[i-1] B[i]B[i-1] 都是升序的不换dp[i][0] dp[i-1][0]换dp[i][1] dp[i-1][1]1(前面i-1换过位置那我也要跟着过去1)A[i]B[i-1] B[i]A[i-1] 跟对方前一个组成升序我不换那要取前面换的状态dp[i][0] dp[i-1][1]我换一下前面取不换的状态dp[i][1] dp[i-1][0]1上面重叠的状态都取最小值min返回min(dp[n-1][0], dp[n-1][1])
class Solution {
public:int minSwap(vectorint A, vectorint B) {int i, n A.size();vectorvectorint dp(n,vectorint(2,INT_MAX));dp[0][0] 0;dp[0][1] 1;for(i 1; i n; i){if(A[i]A[i-1] B[i]B[i-1]){dp[i][0] min(dp[i][0], dp[i-1][0]);dp[i][1] min(dp[i][1], dp[i-1][1]1);}if(A[i]B[i-1] B[i]A[i-1]){dp[i][0] min(dp[i][0], dp[i-1][1]);dp[i][1] min(dp[i][1], dp[i-1][0]1);}}return min(dp[n-1][0], dp[n-1][1]);}
};36 ms 15.7 MB
