作者推荐

【动态规划】【广度优先搜索】【状态压缩】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 <= 10⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 10⁵

动态规划

动态规划的状态

vPre	vPre[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]);
}
};