周赛 Weekly Contest 406

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

3216. Lexicographically Smallest String After a Swap

class Solution:
    def getSmallestString(self, s: str) -> str:
        res = ""
        i = 0
        while i < len(s)-1:
            left = int(s[i])
            right = int(s[i+1])
            if left % 2 == right %2 and int(s[i]) > int(s[i+1]):
                res += s[i+1]
                res += s[i]
                i+=2
                break
            else:
                res += s[i]
                i+=1
        if i < len(s):
            res += s[i:]
        return res

3217. Delete Nodes From Linked List Present in Array

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        numDict = dict()
        for n in nums:
            numDict[n] = True
        
        dummy = ListNode(next=head)
        start = dummy
        while start.next:
            if start.next.val in numDict:
                start.next = start.next.next
            else:
                start = start.next
        return dummy.next
        

3218. Minimum Cost for Cutting Cake I

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        @cache
        def dp(si, sj, ei, ej):
            if si == ei and sj == ej:
                return 0
            res = float("inf")
            for i in range(si, ei, 1):
                # print(si, sj, ei, ej, i)
                res = min(res, dp(si, sj, i, ej) + dp(i+1, sj, ei, ej) + horizontalCut[i])
            for j in range(sj, ej, 1):
                # print(si, sj, ei, ej, j)
                res = min(res, dp(si, sj, ei, j) + dp(si, j+1, ei, ej)+ verticalCut[j])
            return res
        return dp(0, 0, m-1, n-1)

100367. Minimum Cost for Cutting Cake II