Keshawn_lu's Blog

Leetcode 801. 使序列递增的最小交换次数

动态规划
字数统计: 614阅读时长: 3 min
2022/10/10 Share

题目简介：

我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。

  • 例如，如果 nums1 = [1,2,3,8] ， nums2 = [5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。

返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

数组 arr 严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。

注意：

  • 用例保证可以实现操作。

示例 1:

1
2
3
4
5
6
输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出: 1
解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

提示:

  • 2 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 2 * 10^5

思路：

动态规划，dp[i][0]代表到i为止，能使nums1, nums2满足严格递增且位置i不进行交换操作的最小操作数；

dp[i][1]代表到i为止，能使nums1, nums2满足严格递增且位置i进行交换操作的最小操作数。

由于题目保证题目用例可以实现操作，所以位置i必满足以下两种情况之一：

  1. nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]
  2. nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]

当满足1不满足2时：

  • dp[i][0] = dp[i - 1][0]
  • dp[i][1] = dp[i - 1][1] + 1

当满足2不满足1时：

  • dp[i][0] = dp[i - 1][1]
  • dp[i][1] = dp[i - 1][0] + 1

同时满足1,2时：

  • dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
  • dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 1)

代码如下：

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
36
37
38
39
40
41
42
class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {

        vector<vector<int>> dp(nums1.size(), vector<int>(2));

        dp[0][1] = 1;

        int flag1, flag2;
        for(int i = 1; i < nums1.size(); i++){

            flag1 = 0;
            flag2 = 0;

            if(nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1])
                flag1 = 1;

            if(nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1])
                flag2 = 1;
            
            if(flag1 == 1 && flag2 == 1){

                dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
                dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
            }

            else if(flag1 == 1){

                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1] + 1;
            }

            else if(flag2 == 1){

                dp[i][0] = dp[i - 1][1];
                dp[i][1] = dp[i - 1][0] + 1;
            }
        }

        return min(dp[nums1.size() - 1][0], dp[nums1.size() - 1][1]);
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网