Topic describes

Method 1 Dynamic programming

Let’s talk about the underlying logic. The state transition equation in this problem is interesting, and it’s not easy for me to think about. You can also skip to the analysis of fault solutions and navigate directly to the positive solutions section

Original version (error example)

A[I]>A[I -1] &&B [I]>B[I -1] A[I]>A[I -1] &&B [I]>B[I -1] A[I]>A[I -1] &&B [I]>B[I -1] This scheme is relatively simple, and then consider the conditions are not comprehensive, we will give an example to explain; Here’s a look at this version of the code

Class Solution {public int minSwap(int[] A, int[] B) {int[] dp = new int[A]; dp[0] = 0; for(int i = 1; i<A.length; i++){ if(A[i]>A[i-1] && B[i]>B[i-1]){ dp[i] = dp[i-1]; }else{ int t = A[i]; A[i] = B[i]; B[i] = t; dp[i] = dp[i-1] + 1; } } return dp[A.length - 1]; }}

What’s wrong with this version? For example:

A = [0,4,4,5,9]
B = [0,1,6,8,10]



Follow the logic of this version of the code in the traversal toi=2Determine when toA[i]>A[i-1] //A[2]=4 > A[1]=4It didn’t work, so it did it againA[2]andB[2]After the exchange of,A =,4,6,5,9 [0], B =,1,4,8,10 [0], same traversali=3Because when theA[3]=5 < A[2]=6I’m going to do one swap, so I’m going to do two swaps;

But actually, what we’re going to find is that in this case, we can just swapi=1Location to Purpose

So in fact, it’s because our state transition conditions and equations are not sufficiently considered that this leads to this kind of leakage. In fact, we can sense a little bit of a breakthrough here. In some cases, we can choose to switch the I position, or we can choose to switch the I -1 position! .

Corrected version

Firstly, the problem guarantees that all input use cases are valid. In other words, there must be some commutative method that makes A[I] and B[I] eventually increase strictly. Therefore, for any position I, the following three conditions must be satisfied: > 1, A [I] A [I – 1] && B [I] > B] [I – 1, 2 A [I] > [] I – 1 B & B > [I] A [I – 1] 3, at the same time satisfy conditions 1 and 2

Condition 2 can be simply understood as the disordered to ordered sequence of {i-1, I} can be realized after the position exchange of I


For example,
A = (3, 2], B = [1, 4]This is an example of condition 2


(That is to say, if we satisfy condition 1, we exclude condition 2, if we satisfy condition 2, we exclude condition 1, and condition 3 is both satisfied)

So there is a state transition equation as follows:

  • Satisfy condition 1(local sequence order) :

    • I have to swap I minus 1 when I swap I
    • You have to not swap I minus 1 without swapping I

  • Satisfy condition 2(local sequence disorder, exchange once can become ordered) :

    • I just swap the I and not the I minus one
    • I just swap I minus 1 and I don’t swap I

  • Satisfy condition 3:

    • Swap I, I minus one can swap or not swap, choose the best case
    • I don’t swap the I position, I minus one can swap or not swap, choose the best case

Here are some examples of condition 1 and condition 2 for readers to see for themselves


Condition 1:
A =,4,8,5 [1], B =,7,6,9 [4]


Condition 2:
A =,4,6,5 [1], B =,7,8,9 [4]

Armed with the state transition equation, the rest is a matter of looking at the code, the key parts commented

class Solution { public int minSwap(int[] A, int[] B) { int n = A.length; Int [] keep = new int[n]; int[] keep = new int[n]; //swap[I] = new int[n]; //swap[I] = new int[n]; keep[0] = 0; swap[0] = 1; for(int i = 1; i<n; I++) {/ / 3 if meet the conditions ((A > [I] A [I - 1] && B [I] > B] [I - 1) && (A [I] > [] I - 1 B & B > [I] A [] I - 1)) {/ / I don't exchange, Math.min(keep[I] = Math.min(keep[I -1],swap[I -1]); Math. Min (keep[I -1],swap[I -1]) + 1; }else if(A[I] > A[I -1] &&b [I] > B[I -1]){// if(A[I] > A[I -1] &&b [I] > B[I -1]){// if(A[I] > A[I -1] &&b [I] > B[I -1]){// if(A[I] > A[I -1] &&b [I] > B[I -1]){ Keep [I] = keep[I -1]; // swap[I] = swap[I -1] + 1; }else{// void I, void I, void I, void I, void I, void I, void I; // I = 1; // I = 1; // I = 1; }} // return Math.min(keep[n-1],swap[n-1]); }}