★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10547598.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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].
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例: 输入: A = [1,3,5,4], B = [1,2,3,7] 输出: 1 解释: 交换 A[3] 和 B[3] 后，两个数组如下: A = [1, 3, 5, 7] ， B = [1, 2, 3, 4] 两个数组均为严格递增的。
注意:
A, B两个数组的长度总是相等的，且长度的范围为[1, 1000]。A[i], B[i]均为[0, 2000]区间内的整数。
1 class Solution { 2 func minSwap(_ A: [Int], _ B: [Int]) -> Int { 3 var n1:Int = 0 4 var s1:Int = 1 5 var n:Int = A.count 6 for i in 1..<n 7 { 8 var n2:Int = Int.max 9 var s2:Int = Int.max 10 if A[i - 1] < A[i] && B[i - 1] < B[i] 11 { 12 n2 = min(n2, n1) 13 s2 = min(s2, s1 + 1) 14 } 15 if A[i - 1] < B[i] && B[i - 1] < A[i] 16 { 17 n2 = min(n2, s1) 18 s2 = min(s2, n1 + 1) 19 } 20 n1 = n2 21 s1 = s2 22 } 23 return min(n1, s1) 24 } 25 }
76ms
1 class Solution { 2 func minSwap(_ A: [Int], _ B: [Int]) -> Int { 3 var swapRecord = 1, fixRecord = 0 4 for i in 1..<A.count { 5 if A[i-1] >= B[i] || B[i-1] >= A[i] { 6 swapRecord += 1 7 } 8 else if A[i - 1] >= A[i] || B[i - 1] >= B[i] { 9 let temp = swapRecord 10 swapRecord = fixRecord + 1 11 fixRecord = temp 12 } 13 else { 14 let minv = min(swapRecord, fixRecord) 15 swapRecord = minv + 1 16 fixRecord = minv 17 } 18 } 19 return min(swapRecord, fixRecord) 20 } 21 22 func minSwapDP(_ A: [Int], _ B: [Int], _ i: Int, _ sum: Int) -> Int { 23 24 if i >= A.count { 25 return sum 26 } 27 28 if i == 0 { return minSwapDP(A, B, i+1, sum) } 29 30 if A[i] > A[i-1] && B[i] > B[i-1] { 31 return minSwapDP(A, B, i+1, sum) 32 } 33 34 var canSwapPre = (A[i-1] < B[i] && B[i-1] < A[i]) 35 if canSwapPre { 36 for k in 0..<i-1 { 37 if A[i-1] <= B[k] || B[i-1] <= A[k] { 38 canSwapPre = false 39 break 40 } 41 } 42 } 43 let canSwapCur = (B[i] > A[i-1] && A[i] > B[i-1]) 44 45 var A2 = A, B2 = B 46 let tmp2 = A2[i-1] 47 A2[i-1] = B2[i-1] 48 B2[i-1] = tmp2 49 50 var A1 = A, B1 = B 51 let tmp = A1[i] 52 A1[i] = B1[i] 53 B1[i] = tmp 54 if canSwapPre && canSwapCur { 55 return min(minSwapDP(A2, B2, i, sum+1), minSwapDP(A1, B1, i+1, sum+1)) 56 } 57 else if canSwapCur { 58 return minSwapDP(A1, B1, i+1, sum+1) 59 } 60 else { 61 return minSwapDP(A2, B2, i, sum+1) 62 } 63 } 64 }
请发表评论