周赛 Weekly Contest 404

https://leetcode.cn/contest/weekly-contest-404/ranking/

100340. Maximum Height of a Triangle

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def getHeight(f, s):
            c = 0
            while True:
                if c % 2 == 0:
                    if f < c + 1:
                        return c
                    c += 1
                    f -= c
                else:
                    if s < c + 1:
                        return c
                    c += 1
                    s = s - c
            return c
        return max(getHeight(red, blue), getHeight(blue, red))

100357. Find the Maximum Length of Valid Subsequence I

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        k = 2
        @cache
        def dp(i, target, preMod):
            if i >= len(nums):
                return 0
            if preMod == -1:
                return max(dp(i+1, target, nums[i] % k) + 1, dp(i+1, target, preMod))
            if (preMod + nums[i]) % k == target:
                return dp(i+1, target, nums[i] % k) + 1
            else:
                return dp(i+1, target, preMod)
        return max([dp(0, i, -1) for i in range(k)])

100358. Find the Maximum Length of Valid Subsequence II

我的 dp 尝试，不是超时就是超出空间

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        @cache
        def dp(i, target, preMod):
            # if i == 1:
            #     print(i, target, preMod)
            if i >= len(nums):
                return 0
            # if preMod == -1:
            #     return max(dp(i+1, target, nums[i] % k) + 1, dp(i+1, target, preMod))
            if (preMod + nums[i]) % k == target:
                # print(i, target, preMod, nums[i] % k)
                return dp(i+1, target, nums[i] % k) + 1
            else:
                return dp(i+1, target, preMod)
        # def dp(i, preMod):
        #     # if i == 1:
        #     #     print(i, target, preMod)
        #     if i >= len(nums):
        #         return 0
        #     # if preMod == -1:
        #     #     return max(dp(i+1, target, nums[i] % k) + 1, dp(i+1, target, preMod))
        #     if (preMod + nums[i]) % k == 0:
        #         # print(i, target, preMod, nums[i] % k)
        #         return dp(i+1, nums[i] % k ) + 1
        #     else:
        #         return dp(i+1, preMod)
        ans = 1
        # for target in range(k):
        #     for i in range(len(nums)):
        #         if nums[i] % k == target:
        #             # ans = max(ans, dp(i+1, abs(nums[i] % k ) + 1)
        #             ans = max(ans, max([dp(i+1, abs(nums[i] % k - j)) for j in range(k)]) + 1)
        #             # ans = max(ans, max([dp(i+1, j, nums[i] % k) for j in range(k)]) + 1)
        #             break
        # for i in range(len(nums)):
            # for j in range(k):
                # if j >= nums[i] % k:
                #     ans = max(ans, dp(i+1, k -(j - nums[i] % k))+1)
                # else:
                #     ans = max(ans, dp(i+1, abs(nums[i] % k - j))+1) 
            # ans = max(ans, max([dp(i+1, abs(nums[i] % k - j)) for j in range(k)]) + 1)
        for i in range(len(nums)):
            for j in range(i+1, len(nums), 1):
                ans = max(ans, dp(j+1, (nums[i]+nums[j])%k, nums[j]%k)+2)
        return ans

解决方案

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [[0 for j in range(k)] for i in range(k)]
        for x in nums:
            x %= k 
            for y in range(k):
                # 找到 f 以 y 结尾的最大长度加一得到当前 f 以 x 结尾的最大长度
                f[y][x] = f[x][y] + 1
        return max(map(max, f))

100318. Find Minimum Diameter After Merging Two Trees

• Calculating the minDiameter starting from one node of a tree
• Calculating the maxDiameter of each trees
• return max(minD1 + minD2 + 1, maxD1, maxD2)

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        def appendNodeToTree(tree, fromNode, toNode):
            if fromNode not in tree:
                tree[fromNode] = [toNode]
            else:
                tree[fromNode].append(toNode)
        tree1 = dict()
        for e in edges1:
            appendNodeToTree(tree1, e[0], e[1])
            appendNodeToTree(tree1, e[1], e[0])
        tree2 = dict()
        for e in edges2:
            appendNodeToTree(tree2, e[0], e[1])
            appendNodeToTree(tree2, e[1], e[0])

        print(tree1, tree2)
        @cache
        def dfs1(fromNode, toNode):
            ans = 0
            # if toNode not in tree1: return ans
            for to2 in tree1[toNode]:
                if to2 != fromNode:
                    ans = max(ans, dfs1(toNode, to2)+1)
            return ans
        minD1 = inf
        maxD1 = -1
        for fromNode in tree1:
            currentMax = 0
            for toNode in tree1[fromNode]:
                currentMax = max(currentMax, dfs1(fromNode, toNode)+1)
            if currentMax < minD1:
                print(fromNode, currentMax)
            minD1 = min(minD1, currentMax)
            maxD1 = max(maxD1, currentMax)
        print(minD1)

        @cache
        def dfs2(fromNode, toNode):
            ans = 0
            # if toNode not in tree2: return ans
            for to2 in tree2[toNode]:
                if to2 != fromNode:
                    ans = max(ans, dfs2(toNode, to2)+1)
            return ans
        minD2 = inf
        maxD2 = -1 
        for fromNode in tree2:
            currentMax = 0
            for toNode in tree2[fromNode]:
                currentMax = max(currentMax, dfs2(fromNode, toNode)+1)
            minD2 = min(minD2, currentMax)
            maxD2 = max(maxD2, currentMax)
        print(minD2)
        if minD1 == inf:
            return minD2 + 1 if minD2 != inf else 1
        if minD2 == inf:
            return minD1 + 1 if minD1 != inf else 1
        return max(minD1 + minD2 + 1, maxD1, maxD2)