【动态规划】【C++算法】801. 使序列递增的最小交换次数

2024-01-22 23:28
文章标签 算法 动态 规划 c++ 次数 最小 交换 递增 序列 801

本文主要是介绍【动态规划】【C++算法】801. 使序列递增的最小交换次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

本文涉及知识点

动态规划汇总
数组

LeetCode801使序列递增的最小交换次数

我们有两个长度相等且不为空的整型数组 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:
输入: 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 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1
提示:
2 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 105

动态规划

动态规划的状态

vPrevPre[0]前i个元素，最后一个元素没交换的最小交换次数。vPre[1] 最后一个元素交换的最小交换次数。
dp前i+1个元素的最小交换次数。
vPreNum{nums1[i-1],nums2[i-1]}

动态规划的转移方程

前一个元素有两种情况：交换 不交换
当前元素也有两种情况：交换 不交换
共4种情况：如果两个元素都大于前面的元素，则可以转移。

动态规划的填表顺序

下标从小到大枚举nums1和nums2，时间复杂度😮(n)

动态规划的初始状态

vector vPre = { 0,0 };
vector vPreNum = { -1,-1 };

动态规划的返回值

min(vPre[0], vPre[1]);

代码

核心代码

class Solution {
public:int minSwap(vector<int>& nums1, vector<int>& nums2) {vector<int> vPre = { 0,0 };	vector<int> vPreNum = { -1,-1 };for (int i = 0; i < nums1.size(); i++){vector<int> dp(2, nums1.size());for (int iPre = 0; iPre <= 1; iPre++){				//当前下标不交换if ((nums1[i] > vPreNum[iPre]) && (nums2[i] > vPreNum[(iPre + 1) % 2])){dp[0] = min(dp[0], vPre[iPre]);}//当前下标交换if ((nums2[i] > vPreNum[iPre]) && (nums1[i] > vPreNum[(iPre + 1) % 2])){dp[1] = min(dp[1], vPre[iPre]+1);}}vPre.swap(dp);vPreNum = { nums1[i],nums2[i] };}return min(vPre[0], vPre[1]);}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<int> nums1,  nums2;{Solution sln;nums1 = { 0, 3, 5, 8, 9 }, nums2 = { 2, 1, 4, 6, 9 };auto res = sln.minSwap(nums1, nums2);Assert(1, res);}{Solution sln;nums1 = { 1, 3, 5, 4 }, nums2 = { 1, 2, 3, 7 };auto res = sln.minSwap(nums1, nums2);Assert(1, res);} }

小技巧

iPre取值0或1时 iPre ^ 1 可以代替(iPre + 1) % 2

2023年1月

class Solution {
public:
int minSwap(vector& nums1, vector& nums2) {
vector pre(2);
if (nums1[0] >= nums2[0])
{
pre[0] = 0;
}
else
{
pre[0] = 1;
}
if (nums2[0] >= nums1[0])
{
pre[1] = 0;
}
else
{
pre[1] = 1;
}
for (int i = 1; i < nums1.size(); i++)
{
vector dp(2, INT_MAX);
const int iMaxPre = max(nums1[i - 1], nums2[i - 1]);
if (nums1[i] >= nums2[i])
{
dp[0] = pre[0];
if (nums2[i] > iMaxPre)
{
dp[0] = min(dp[0], pre[1]);
}
}
else
{
dp[0] = 1 + pre[0];
if (nums1[i] > iMaxPre)
{
dp[0] = min(dp[0], pre[1]+1 );
}
}
if (nums2[i] >= nums1[i])
{
dp[1] = pre[1];
if (nums1[i] > iMaxPre)
{
dp[1] = min(dp[1], pre[0]);
}
}
else
{
dp[1] = pre[1] + 1;
if (nums2[i] > iMaxPre)
{
dp[1] = min(dp[1], pre[0] + 1);
}
}
pre.swap(dp);
}
return *std::min_element(pre.begin(), pre.end());
}
};

2023年6月版

class Solution {
public:
int minSwap(vector& nums1, vector& nums2) {
vector pre(2);//确保nums1[i-1]小于nums2[i-1] ，且nums1,nums2前i个元素符号条件需要变换次数
if (nums1[0] < nums2[0])
{
pre[1] = 1;
}
else
{
pre[0] = 1;
}
for (int i = 1; i < nums1.size(); i++)
{
int iPreMin = min(nums1[i - 1], nums2[i - 1]);
int iPreMax = max(nums1[i - 1], nums2[i - 1]);
vector dp(2);
bool bMinMorePreMax = min(nums1[i], nums2[i]) > iPreMax;
bool bNums1Min = nums1[i] <= nums2[i];
if (bNums1Min)
{
dp[0] = pre[0];
dp[1] = pre[1]+1;
if (bMinMorePreMax)
{
dp[0] = min(dp[0], pre[1]);
dp[1] = min(dp[1], pre[0] + 1) ;
}
}
else
{
dp[1] = pre[1];
dp[0] = pre[0] + 1;
if (bMinMorePreMax)
{
dp[1] = min(dp[1], pre[0]);
dp[0] = min(dp[0], pre[1] + 1);
}
}
pre.swap(dp);
}
return min(pre[0], pre[1]);
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】【C++算法】801. 使序列递增的最小交换次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/634564。

相关文章

使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
关于最长递增子序列问题概述

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法：贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列，例如 nums = [10, 9, 2
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2