leetcode：801. 使序列递增的最小交换次数【线性dp + 考虑当前和前一位 + java】

分析

只能交换nums1[i]和nums2[i]
保证nums1和nums2严格递增
对于每一个i，我们可以交换或者不交换
因此我们考虑四种情况，分别是前一位交换or不交换 + 当前位交换or不交换
设上一层f0, f1，当前tmp0, tmp1
1.i - 1不交换，i不交换：满足原来顺序，tmp0 = min(tmp0, f0)
2.i - 1交换, i不交换：满足交换后的顺序, tmp0 = min(tmp0, f1)
3.i - 1不交换, i交换: 满足交换后的顺序, tmp1 = min(tmp1, f0 + 1)
4.i - 1交换， i交换：满足原来顺序，tmp1 = min(tmp1, f1 + 1)

java

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        // 考虑i - 1 和 i
        // 考虑换与不换
        int n = nums1.length;
        // 初始状态
        // f0不换, f1换
        int f0 = 0, f1 = 1;
        for (int i = 1; i < n; i++) {
            int tmp0 = Integer.MAX_VALUE, tmp1 = Integer.MAX_VALUE;
            // i - 1不换，i也不换
            if (f0 != Integer.MAX_VALUE && nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tmp0 = Math.min(tmp0, f0);
            }
            // i - 1换, i不换
            if (f1 != Integer.MAX_VALUE && nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                tmp0 = Math.min(tmp0, f1);
            }
            // i - 1不换, i换
            if (f0 != Integer.MAX_VALUE && nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                tmp1 = Math.min(tmp1, f0 + 1);
            }
            // i - 1换, i换
            if (f1 != Integer.MAX_VALUE && nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tmp1 = Math.min(tmp1, f1 + 1);
            }

            // 下一层dp
            f0 = tmp0;
            f1 = tmp1;
        }

        return Math.min(f0, f1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

java总结

1.函数类型，数组，类型 和 分号
2.数组长度 int n = nums.length;
3.Integer.MAX_VALUE
4.Math.min