[LeetCode] 801. Minimum Swaps To Make Sequences Increasing 最少交换使得序列递增
2024-10-21 09:54:41
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.
Note:
A, B
are arrays with the same length, and that length will be in the range[1, 1000]
.A[i], B[i]
are integer values in the range[0, 2000]
.
给两个长度相等的数组A和B,可在任意位置i交换A[i]和B[i]的值,使得数组A和B变成严格递增的数组,求最少需要交换的次数。
解法:dp
Java:
class Solution {
public int minSwap(int[] A, int[] B) {
int swapRecord = 1, fixRecord = 0;
for (int i = 1; i < A.length; i++) {
if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) {
// In this case, the ith manipulation should be same as the i-1th manipulation
// fixRecord = fixRecord;
swapRecord++;
} else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) {
// In this case, the ith manipulation should be the opposite of the i-1th manipulation
int temp = swapRecord;
swapRecord = fixRecord + 1;
fixRecord = temp;
} else {
// Either swap or fix is OK. Let's keep the minimum one
int min = Math.min(swapRecord, fixRecord);
swapRecord = min + 1;
fixRecord = min;
}
}
return Math.min(swapRecord, fixRecord);
}
}
Python:
class Solution(object):
def minSwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
dp_no_swap, dp_swap = [0]*2, [1]*2
for i in xrange(1, len(A)):
dp_no_swap[i%2], dp_swap[i%2] = float("inf"), float("inf")
if A[i-1] < A[i] and B[i-1] < B[i]:
dp_no_swap[i%2] = min(dp_no_swap[i%2], dp_no_swap[(i-1)%2])
dp_swap[i%2] = min(dp_swap[i%2], dp_swap[(i-1)%2]+1)
if A[i-1] < B[i] and B[i-1] < A[i]:
dp_no_swap[i%2] = min(dp_no_swap[i%2], dp_swap[(i-1)%2])
dp_swap[i%2] = min(dp_swap[i%2], dp_no_swap[(i-1)%2]+1)
return min(dp_no_swap[(len(A)-1)%2], dp_swap[(len(A)-1)%2])
C++:
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<int> swap(n, n), noSwap(n, n);
swap[0] = 1; noSwap[0] = 0;
for (int i = 1; i < n; ++i) {
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
swap[i] = swap[i - 1] + 1;
noSwap[i] = noSwap[i - 1];
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
swap[i] = min(swap[i], noSwap[i - 1] + 1);
noSwap[i] = min(noSwap[i], swap[i - 1]);
}
}
return min(swap[n - 1], noSwap[n - 1]);
}
};
C++:
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
int n1 = 0, s1 = 1, n = A.size();
for (int i = 1; i < n; ++i) {
int n2 = INT_MAX, s2 = INT_MAX;
if (A[i - 1] < A[i] && B[i - 1] < B[i]) {
n2 = min(n2, n1);
s2 = min(s2, s1 + 1);
}
if (A[i - 1] < B[i] && B[i - 1] < A[i]) {
n2 = min(n2, s1);
s2 = min(s2, n1 + 1);
}
n1 = n2;
s1 = s2;
}
return min(n1, s1);
}
};
类似题目:
Best Time to Buy and Sell Stock with Transaction Fee
All LeetCode Questions List 题目汇总
最新文章
- 关于MJRefresh的下拉加载数据bug
- Java基础-输入输出-3.编写BinIoDemo.java的Java应用程序,程序完成的功能是:完成1.doc文件的复制,复制以后的文件的名称为自己的学号姓名.doc。
- 【hbase0.96】基于hadoop搭建hbase的心得
- 贪心算法 hdu 1009
- windows 编程中的常见bug
- Word Search [LeetCode]
- C# String.Format大全 去 decimal 后面的 0
- hdu 2988 Dark roads
- Unity中Instantiate一个prefab时需要注意的问题
- 使用Java原生代理实现数据注入
- oracle删掉重复数据的语法
- Python学习 1 一 Python2.75的安装及环境配置教程
- android listview 三种适配器设置
- C#中ISpostback
- CSS的box-sizing属性
- nginx的ngx_http_realip_module模块和http头X-Forwarded-For、X-Real-IP
- bzoj千题计划136:bzoj3931: [CQOI2015]网络吞吐量
- golang 小知识-持续更新中
- JQuery鼠标移到小图显示大图效果的方法
- Python学习之路8 - 内置方法
热门文章
- python assert 在正式产品里禁用的手法 直接-O即可
- selenium与webdriver驱动与firefox、 chrome匹配版本
- 微信小程序~页面跳转和路由
- C#中的WinForm的消息机制简述,及消息机制下Invoke,和BeginInvoke的使用和区别
- expect工具实现脚本的自动交互
- 微信小程序转百度小程序代码
- javascript Object and new object() object --构造函数
- jQuery中的text()、html()和val()以及javaScript中的innerText、innerHTML和value
- Spring框架的JDBC模板技术和事物
- FFT/NTT [51Nod 1028] 大数乘法 V2