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: 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.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

有两个if时，为了防止两个if都不满足的情况，swap not_swap太小而搅屎棍干扰结果，初始值每次都设置成最大N

［思维问题］：

对dp很恐惧，没做过不知道交换以后应该怎么检查，但是后续检查其实没有必要

［英文数据结构或算法，为什么不用别的数据结构或算法］：

数个数的dp需要新建数组

两个变量赋值相等，可以用连等号～

not_swap[i] = swap[i] = N;

［一句话思路］：

头一回做：递增可能不能换能换可能不递增，所以需要把两步分开

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

有两个if时，为了防止两个if都不满足的情况，swap not_swap太小而搅屎棍干扰结果，初始值每次都设置成最大N

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：递归/分治/贪心］：贪心

［关键模板化代码］：

坐标型：不存在前0位（没意义），第0位就能用返回f[n - 1]

1- n位在循环中用，第0位直接在定义中用

swap[0] = 1;

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {

    public int minSwap(int[] A, int[] B) {

        //ini: swap[1000], not_swap[1000]

        int N = A.length;

        int[] swap = new int[1000];

        int[] not_swap = new int[1000];

        swap[0] = 1;

        not_swap[0] = 0;

        //for loop 1 < n

        for (int i = 1; i < N; i++) {

            swap[i] = N; not_swap[i] = N;

            //compare normal or not

            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {

                not_swap[i] = Math.min(not_swap[i], not_swap[i - 1]);

                swap[i] = Math.min(swap[i], swap[i - 1] + 1);

            }

            //compare exchangeable or not

            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {

                not_swap[i] = Math.min(not_swap[i], swap[i - 1]);

                swap[i] = Math.min(swap[i], not_swap[i - 1] + 1);

            }

        }

        return Math.min(swap[N - 1], not_swap[N - 1]);

    }

}

巴特西

801. Minimum Swaps To Make Sequences Increasing 为使两个数组严格递增，所需要的最小交换次数

最新文章

热门文章