23.05.11 Today’s Leetcode

1035. Uncrossed Lines (medium)

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        dp = {}
        
        def dfs(i, j):
            if (i, j) in dp:
                return dp[(i, j)]
            if i >= n1 or j >= n2:
                return 0
            
            a, b = i, j
            while b < n2 and nums1[i] != nums2[b]:
                b += 1
            while a < n1 and nums1[a] != nums2[j]:
                a += 1
                
            temp = dfs(i + 1, j + 1)
            if b < n2 and nums1[i] == nums2[b]:
                temp = max(temp, 1 + dfs(i + 1, b + 1))
            if a < n1 and nums1[a] == nums2[j]:
                temp = max(temp, 1 + dfs(a + 1, j + 1))
            
            dp[(i, j)] = temp
            return temp
        
        return dfs(0, 0)
            

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        if n < m:
            return self.maxUncrossedLines(nums2, nums1)
        
        dp = [0] * (m + 1)
        for i in range(1, n + 1):
            prev = 0
            for j in range(1, m + 1):
                curr = dp[j]
                if nums1[i-1] == nums2[j-1]:
                    dp[j] = prev + 1
                else:
                    dp[j] = max(dp[j-1], curr)
                prev = curr
        
        return dp[m]

888. Fair Candy Swap (easy)

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        sum_alice = sum(aliceSizes)
        sum_bob = sum(bobSizes)
        diff = (sum_alice - sum_bob) // 2
        print(diff)
        
        aliceSizes.sort()
        bobSizes.sort()
        i = j = 0
        while True:
            p = aliceSizes[i] - bobSizes[j]
            if p < diff:
                i += 1
            elif p > diff:
                j += 1
            else:
                return [aliceSizes[i], bobSizes[j]]

        return [-1]