MinimumSwapsToMakeSequencesIncreasing [source code]

public class MinimumSwapsToMakeSequencesIncreasing {
static
/******************************************************************************/
class Solution {
    public int minSwap(int[] _A, int[] _B) {
        int[] A = Arrays.copyOf (_A, _A.length), B = Arrays.copyOf (_B, _B.length);
        int res1 = 0, res2 = 0;
        // System.out.printf ("i:(%d)\nA:%s\nB:%s\n\n", 0, Printer.array (A), Printer.array (B));///
        for (int i = 1; i < A.length; i++) {
            if (!(A[i] > A[i - 1] && B[i] > B[i - 1])) {
                swap (A, B, i);
                // System.out.printf ("i:(%d)\nA:%s\nB:%s\n\n", i, Printer.array (A), Printer.array (B));///
                res1++;
            }
        }
        A = Arrays.copyOf (_A, _A.length);
        B = Arrays.copyOf (_B, _B.length);
        for (int i = 0; i < A.length - 1; i ++) {
            if (!(A[i] < A[i + 1] && B[i] < B[i + 1])) {
                swap (A, B, i);
                // System.out.printf ("i:(%d)\nA:%s\nB:%s\n\n", i, Printer.array (A), Printer.array (B));///
                res2++;
            }
        }
        return Math.min (res1, res2);
    }

    void swap (int[] A, int[] B, int idx) {
        int tmp = A[idx];
        A[idx] = B[idx];
        B[idx] = tmp;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinimumSwapsToMakeSequencesIncreasing.Solution tester = new MinimumSwapsToMakeSequencesIncreasing.Solution();
        int[][] inputs = {
            {1,3,5,4}, {1,2,3,7}, {1},
            {3,3,8,9,10}, {1,7,4,6,8}, {1},
            {0,4,4,5,9}, {0,1,6,8,10}, {1},
            {0,7,8,10,10,11,12,13,19,18}, {4,4,5,7,11,14,15,16,17,20}, {4},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println (Printer.separator ());
            int[] A = inputs[3 * i], B = inputs[3 * i + 1];
            String input_str = Printer.array (A) + "and\n" + Printer.array (B);
            int ans = inputs[3 * i + 2][0], output = tester.minSwap (A, B);
            System.out.printf ("%s\n%s, expected: %d\n", 
                input_str, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

最后没有做出来, 感觉还是想的太简单了: 我的想法是只要有顺序不对的地方, 就直接swap就行了, 后来看了一下contest其他人的代码, 这题是一个DP题目;

editorial

contest:

class Solution {  
    public int minSwap(int[] A, int[] B) {  
        int n=A.length;  
        int f[][]=new int[n][2];  
        f[0][1]=1;  
        for (int i=1;i<n;i++)  
        {  
            f[i][0]=f[i][1]=100000000;  
            if (A[i]>A[i-1] && B[i]>B[i-1])  
            {  
                f[i][0]=Math.min(f[i][0],f[i-1][0]);  
                f[i][1]=Math.min(f[i][1],f[i-1][1]+1);  
            }  
            if (A[i]>B[i-1] && B[i]>A[i-1])  
            {  
                f[i][0]=Math.min(f[i][0],f[i-1][1]);  
                f[i][1]=Math.min(f[i][1],f[i-1][0]+1);  
            }  
        }  
        return Math.min(f[n-1][0],f[n-1][1]);  
    }  
}

UNFINISHED

Problem Description

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: 1  
Explanation:   
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].

Difficulty:Medium
Total Accepted:2.9K
Total Submissions:11.9K
Contributor:ngoc_lam
Companies
facebookamazon
Related Topics
dynamic programming