LeetCode Solutions
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
vector<int> keepAt(A.size(), INT_MAX);
vector<int> swapAt(A.size(), INT_MAX);
keepAt[0] = 0;
swapAt[0] = 1;
for (int i = 1; i < A.size(); ++i) {
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt[i] = keepAt[i - 1];
swapAt[i] = swapAt[i - 1] + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt[i] = min(keepAt[i], swapAt[i - 1]);
swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1);
}
}
return min(keepAt.back(), swapAt.back());
}
};
|
class Solution {
public int minSwap(int[] A, int[] B) {
final int n = A.length;
int[] keepAt = new int[n];
int[] swapAt = new int[n];
Arrays.fill(keepAt, Integer.MAX_VALUE);
Arrays.fill(swapAt, Integer.MAX_VALUE);
keepAt[0] = 0;
swapAt[0] = 1;
for (int i = 1; i < n; ++i) {
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
keepAt[i] = keepAt[i - 1];
swapAt[i] = swapAt[i - 1] + 1;
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
keepAt[i] = Math.min(keepAt[i], swapAt[i - 1]);
swapAt[i] = Math.min(swapAt[i], keepAt[i - 1] + 1);
}
}
return Math.min(keepAt[n - 1], swapAt[n - 1]);
}
}
|
class Solution:
def minSwap(self, A: List[int], B: List[int]) -> int:
keepAt = [math.inf] * len(A)
swapAt = [math.inf] * len(A)
keepAt[0] = 0
swapAt[0] = 1
for i in range(1, len(A)):
if A[i] > A[i - 1] and B[i] > B[i - 1]:
keepAt[i] = keepAt[i - 1]
swapAt[i] = swapAt[i - 1] + 1
if A[i] > B[i - 1] and B[i] > A[i - 1]:
keepAt[i] = min(keepAt[i], swapAt[i - 1])
swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1)
return min(keepAt[-1], swapAt[-1])
|
