【leetcode】801. Minimum Swaps To Make Sequences Increasing
题目如下:
We have two integer sequences
A
andB
of the same non-zero length.We are allowed to swap elements
A[i]
andB[i]
. Note that both elements are in the same index position in their respective sequences.At the end of some number of swaps,
A
andB
are both strictly increasing. (A sequence is strictly increasing if and only ifA[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]
.
解题思路:每个下标对应的元素只有交换和不交换两种选择,记dp[i][0]为在[0~i]这个区间内,在第i个元素不交换时使得[0~i]区间子数组严格递增时总的交换次数,而dp[i][0]为在[0~i]这个区间内,在第i个元素交换时使得[0~i]区间子数组严格递增时总的交换次数。要使得数组严格递增,第i个元素是否需要交换取决于与(i-1)元素的值的大小情况,总得来说分为可能性如下,
1. A[i] > A[i - 1] and B[i] > B[i - 1] and A[i] > B[i - 1] and B[i] > A[i - 1] ,这种情况下,第i个元素可以交换或者不交换,并且和i-1是否交换没有任何关系,那么可以得出: 在第i个元素不交换的情况下,dp[i][0] 应该等于第i-1个元素交换与不交换两种情况下的较小值,有 dp[i][0] = min(dp[i][0], dp[i - 1][0], dp[i - 1][1]) ,如果第i个元素非要任性的交换,那么结果就是第i-1个元素交换与不交换两种情况下的较小值加上1,有dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1, dp[i - 1][1] + 1) 。
2. A[i] > A[i - 1] and B[i] > B[i - 1] ,这种情况是i和i-1之间要么都交换,要么都不交换。有 dp[i][0] = min(dp[i][0], dp[i - 1][0]) ,dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1)
3. A[i] > B[i - 1] and B[i] > A[i - 1] and (A[i] <= A[i - 1] or B[i] <= B[i - 1]),这种情况是要么i交换,要么i-1交换。有 dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1),dp[i][0] = min(dp[i][0], dp[i - 1][1])
4.其他情况则表示无论i交换或者不交换都无法保证严格递增。
代码如下:
class Solution(object):
def minSwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
dp = [[float('inf')] * 2 for _ in A]
dp[0][0] = 0
dp[0][1] = 1
for i in range(1, len(A)):
if (A[i] > A[i - 1] and B[i] > B[i - 1]) and (A[i] > B[i - 1] and B[i] > A[i - 1]):
dp[i][0] = min(dp[i][0], dp[i - 1][0], dp[i - 1][1])
dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1, dp[i - 1][1] + 1)
elif A[i] > A[i - 1] and B[i] > B[i - 1]:
dp[i][0] = min(dp[i][0], dp[i - 1][0])
dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1)
elif A[i] > B[i - 1] and B[i] > A[i - 1] and (A[i] <= A[i - 1] or B[i] <= B[i - 1]):
dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1)
dp[i][0] = min(dp[i][0], dp[i - 1][1]) #print dp
return min(dp[-1]) if min(dp[-1]) != float('inf') else -1
最新文章
- 浅谈Nginx负载均衡和F5的区别
- LeetCode Closest Binary Search Tree Value
- android中的TextView控件
- 基于css制作轮播图的部分效果
- Altium designer 10如何设置标题栏
- BZOJ 1739: [Usaco2005 mar]Space Elevator 太空电梯
- hadoop Yarn运行机制
- Spring基础篇——Spring容器和应用上下文理解
- [转]Setting Keystone v3 domains
- CentOS7搭建配置SVN服务器
- 转 flowcanvas
- 【微信公众号开发】【13】批量导出公众号所有用户信息到Excel
- sh脚本学习之:变量
- State Threads 回调终结者
- 微信小程序,开发中几个重要的知识点(加密解密,转发,进入场景,session_key)
- idea中git git pull push需要反复输入密码
- 流媒体服务器+EasyDarwin+EasyPusher+VLC+Red5+OBS+Unity+RTSP+RTMP+FFMPEG
- ES6 箭头函数 this 指向
- linux(centOs)下memcached安装
- 数据结构之排序技术:快速排序、归并排序、堆排序(C++版)