12/22/2022 Two Leetcode Problems

box-lin commented 1 year ago

Instruction: Participant please comment with your solutions provided with your explanation below! Go leetcode.

137thphxx commented 1 year ago

超时

class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    x = len(nums1)
    y = len(nums2)

    result = 0
    index = [[0]*(y+1) for _ in range(x + 1)]

    for i in range(1, x+1):
        for j in range(1, y+1):
            if nums1[i-1] == nums2[j-1]:
                index[i][j] = index[i-1][j-1] + 1
            else:
                index[i][j] = 0

            result = max(result, index[i][j])

    return result

class Solution:
def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
    length = len(nums)
    if length <(firstLen+secondLen):
        return 0
    #get the prefix
    for i in range(1,length):
        nums[i] += nums[i-1]

    res,maxF,maxS = nums[firstLen + secondLen-1], nums[firstLen-1],nums[secondLen-1]

    for i in range(firstLen + secondLen, length):
        maxF = max(maxF, nums[i - secondLen] - nums[i - firstLen - secondLen])
        res = max(res, maxF + nums[i] - nums[i - secondLen])

    # window  | --- M --- | --- L --- |
    for i in range(firstLen + secondLen, length):
        maxS = max(maxS, nums[i - firstLen] - nums[i - firstLen - secondLen])
        res = max(res, maxS + nums[i] - nums[i - firstLen])

    return res

box-lin commented 1 year ago

# [718. Maximum Length of Repeated Subarray] 
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        # dp[i][j] is the length of Repeated Subarray end with nums1[i] and nums2[j]
        dp = [ [0]*n2 for _ in range(n1) ]
        ans = 0
        for i in range(n1):
            for j in range(n2):
                # here is the base case.
                if i == 0 or j == 0:
                    if nums1[i] == nums2[j]:
                        dp[i][j] = 1 
                else:
                    if nums1[i] == nums2[j]:
                        dp[i][j] = dp[i-1][j-1] + 1
                ans = max(dp[i][j], ans )
        return ans

# [1031. Maximum Sum of Two Non-Overlapping Subarrays] 
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], a: int, b: int) -> int:
        prefix = [0]
        maxa = maxb = summ = 0
        for x in A:
            prefix.append(prefix[-1] + x)
        # b after a
        for i in range(a, len(prefix) - b):
            maxa = max(maxa, prefix[i] - prefix[i - a])
            summ = max(summ, maxa + prefix[i + b] - prefix[i])
        # a after b
        for i in range(b, len(prefix) - a):
            maxb = max(maxb, prefix[i] - prefix[i - b])
            summ = max(summ, maxb + prefix[i + a] - prefix[i])
        return summ

box-lin / miniblog

12/22/2022 Two Leetcode Problems #8