Problem
题目大意：给你两个数组A, B。问最少需要多少次对应位置元素的交换才能使得A和B变成单调递增。
https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/description/
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, Bare 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].
Solution: Search/DFS (TLE)
Time complexity: O(2^n)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua // Running time: TLE 84/102 test cases passed. class Solution { public: int minSwap(vector<int>& A, vector<int>& B) { int ans = INT_MAX; dfs(A, B, 0, 0, ans); return ans; } private: void dfs(vector<int>& A, vector<int>& B, int i, int c, int& ans) { if (c >= ans) return; if (i == A.size()) { ans = min(ans, c); return; } if (i == 0 || A[i] > A[i - 1] && B[i] > B[i - 1]) dfs(A, B, i + 1, c, ans); if (i == 0 || A[i] > B[i - 1] && B[i] > A[i - 1]) { swap(A[i], B[i]); dfs(A, B, i + 1, c + 1, ans); swap(A[i], B[i]); } } }; |
Solution: DP
Time complexity: O(n)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua // Running time: 15 ms class Solution { public: int minSwap(vector<int>& A, vector<int>& B) { const int n = A.size(); vector<int> keep(n, INT_MAX); vector<int> swap(n, INT_MAX); keep[0] = 0; swap[0] = 1; for (int i = 1; i < n; ++i) { if (A[i] > A[i - 1] && B[i] > B[i - 1]) { // Good case, no swapping needed. keep[i] = keep[i - 1]; // Swapped A[i - 1] / B[i - 1], swap A[i], B[i] as well swap[i] = swap[i - 1] + 1; } if (B[i] > A[i - 1] && A[i] > B[i - 1]) { // A[i - 1] / B[i - 1] weren't swapped. swap[i] = min(swap[i], keep[i - 1] + 1); // Swapped A[i - 1] / B[i - 1], no swap needed for A[i] / B[i] keep[i] = min(keep[i], swap[i - 1]); } } return min(keep.back(), swap.back()); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 60 ms """ class Solution: def minSwap(self, A, B): n = len(A) dp = [[float('inf'), float('inf')] for _ in range(n)] dp[0][0], dp[0][1] = 0, 1 for i in range(1, n): if A[i] > A[i - 1] and B[i] > B[i - 1]: dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] + 1 if B[i] > A[i - 1] and A[i] > B[i - 1]: dp[i][0] = min(dp[i][0], dp[i - 1][1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1) return min(dp[-1]) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
DP的题每次总是差一点。这道题可以想到DFS，想到继续优化应该用DP。但是DP递推式确却想不出来最后正确的，这道题比如得考虑两个元素之间的关系。希望楼主大神可以分享下这个公式如何由一些经验去推导去思考。
自己总结了常见一维，二维，常见字符串，区间DP，DFS+记忆存储，不过碰到新题有些还是一时半会想不出来。
谢谢楼主的视频，讲解非常清晰。