LeetCode-801. Minimum Swaps To Make Sequences Increasing

LeetCode-801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences ​​A​​​ and ​​B​​ of the same non-zero length.

We are allowed to swap elements ​​A[i]​​​ and ​​B[i]​​.  Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, ​​A​​​ and ​​B​​ are both strictly increasing.  (A sequence is strictly increasing if and only if ​​A[0] < A[1] < A[2] < ... < A[A.length - 1]​​.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.

Example:Input: A = [1,3,5,4], B = [1,2,3,7]Output: 1Explanation: Swap A[3] and B[3]. Then the sequences are:A = [1, 3, 5, 7] and B = [1, 2, 3, 4]which are both strictly increasing.

Note:

​​A, B​​​ are arrays with the same length, and that length will be in the range​​[1, 1000]​​.​​A[i], B[i]​​​ are integer values in the range​​[0, 2000]​​.

题解：

dp1代表不交换A[i]和B[i]情况下，保持前i个数有序的最小交换次数，dp2代表每次尽可能交换的情况。

其实每次决策只用到了dp[i-1]的值，因此可以用4个变量完成而不是两个数组。

func min(a, b int) int { if a > b { return b } return a}func minSwap(A []int, B []int) int { n := len(A) if len(A) != len(B) { return 0 } dp1, dp2 := make([]int, n), make([]int, n) dp1[0] = 0 dp2[0] = 1 for i := 1; i < n; i++ { dp1[i] = n dp2[i] = n } for i := 1; i < n; i++ { if A[i] > A[i - 1] && B[i] > B[i - 1] { dp1[i] = dp1[i - 1] dp2[i] = dp2[i - 1] + 1 } if A[i] > B[i - 1] && B[i] > A[i - 1] { dp1[i] = min(dp1[i], dp2[i - 1]) dp2[i] = min(dp2[i], dp1[i - 1] + 1) } } return min(dp1[n - 1], dp2[n - 1])}

4变量版：

class Solution {public: int minSwap(vector& A, vector& B) { int l1 = A.size(), l2 = B.size(); if (l1 != l2) { return 0; } int usp = INT_MAX, preusp = 0, sp = INT_MAX, presp = 1; for (int i = 1; i < l1; i++) { sp = l1; usp = l1; if (A[i] > A[i - 1] && B[i] > B[i - 1]) { usp = preusp; sp = presp + 1; } if (A[i] > B[i - 1] && B[i] > A[i - 1]) { usp = min(usp, presp); sp = min(sp, preusp + 1); } presp = sp; preusp = usp; } return min(sp, usp); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。