動機
這個真的想不到!!
- 用dp紀錄狀態
- 從dp(swap)找出另一個dp(fix)
Problem
You are given two integer arrays of the same length nums1
and nums2
. In one operation, you are allowed to swap nums1[i]
with nums2[i]
.
- For example, if
nums1 = [1,2,3,8]
, andnums2 = [5,6,7,4]
, you can swap the element ati = 3
to obtainnums1 = [1,2,3,4]
andnums2 = [5,6,7,8]
.
Return the minimum number of needed operations to make nums1
and nums2
strictly increasing. The test cases are generated so that the given input always makes it possible.
An array arr
is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1]
.
Example 1:
Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7]Output: 1Explanation: Swap nums1[3] and nums2[3]. Then the sequences are:nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4]which are both strictly increasing.
Example 2:
Input: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]Output: 1
Constraints:
2 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 105
Sol
fix是這一點沒有被swap的情況下成為increasing需要幾次swap swap是這一點被swap後的情況下成為increasing需要幾次swap
class Solution:
def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
fix = 0
swap = 1
for i in range(1,len(nums1)):
fixa = fixb = swapa = swapb = len(nums1)
if nums1[i-1] < nums1[i] and nums2[i-1] < nums2[i]:
fixa = fix
swapa = swap+1
if nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i]:
fixb = swap
swapb = fix+1
fix, swap = min(fixa,fixb), min(swapa,swapb)
return min(fix,swap)