Skip to main content

周赛 Weekly Contest 403

https://leetcode.cn/contest/weekly-contest-403/

  • 1
  • 2
  • 3
  • 4 (Late Submission, AC after competition finished)

4/4

今天11点才开始周赛，半小时ak前三题，然后花了一小时多才AC第四题， mark 第一次 ac 第四题

100342. Minimum Average of Smallest and Largest Elements​

Solution:

  • Array Traversal

第一题花了十分钟，属实不应该

todo:

  • python 数组删除元素不熟悉？应该不是，就是手搓太慢了而已
class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        ans = 200
        for i in range(len(nums)//2):
            minN = 100
            maxN = -1
            minI = 0
            maxI = 0
            for j in range(len(nums)):
                if nums[j] != -1:
                    if minN > nums[j]:
                        minI = j
                        minN = nums[j]
                    if maxN < nums[j]:
                        maxI = j
                        maxN = nums[j]
            nums[minI] = -1
            nums[maxI] = -1
            # print(minI, maxN, minI, maxI)
            ans = min(ans, (minN + maxN) / 2)
        return ans

100334. Find the Minimum Area to Cover All Ones I​

Solution:

  • Array Traversal
class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        upperI, lowerI = -1, -1
        leftJ, rightJ = -1, -1
        for i in range(len(grid)):
            if sum(grid[i]) > 0:
                if upperI == -1: upperI = i
                lowerI = i
        columnS = []
        for j in range(len(grid[0])):
            s = 0
            for i in range(len(grid)):
                s += grid[i][j]
                columnS.append(s)
            if s > 0:
                if leftJ == -1: leftJ = j
                rightJ = j
        return (lowerI - upperI + 1) * (rightJ - leftJ +1)

100337. Maximize Total Cost of Alternating Subarrays​

Solution:

  • Status DP

todo:

  • 状态压缩是什么，为什么叫状态压缩
class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        @cache
        def dp(i, positive):
            if i == len(nums):
                return 0
            if positive:
                return nums[i] + max(dp(i+1, False), dp(i+1, True))
            else:
                return -nums[i] + dp(i+1, True)
        return dp(0, True)

100332. Find the Minimum Area to Cover All Ones II​

Solution:

  • Array Traversal
  • Enumerate all possibilities

todo:

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        def findMinArea(i1, i2, j1, j2):
            if j1 > j2 or i1 > i2:
                return 0
            upperI, lowerI = -1, -1
            leftj, rightJ = -1, -1
            for i in range(i1, i2 + 1, 1):
                s = 0
                for j in range(j1, j2 + 1, 1):
                    s += grid[i][j]
                if s > 0:
                    if upperI == -1:
                        upperI = i
                    lowerI = i

            for j in range(j1, j2 + 1, 1):
                s = 0
                for i in range(i1, i2 + 1, 1):
                    s += grid[i][j]
                if s > 0:
                    if leftj == -1:
                        leftj = j
                    rightJ = j
            if lowerI == -1 or rightJ == -1:
                return 0
            return (lowerI - upperI + 1) * (rightJ - leftj + 1)

        def dp(lefti, i, leftj, j, times):
            if times == 1:
                return findMinArea(lefti, i, leftj, j)
            ans = float("inf")
            if times == 2:
                for i2 in range(lefti, i):
                    ans = min(ans, findMinArea(i2 + 1, i, leftj, j) + dp(lefti, i2, leftj, j, 1))
                for j2 in range(leftj, j):
                    ans = min(ans, findMinArea(lefti, i, j2 + 1, j) + dp(lefti, i, leftj, j2, 1))
                # for i1 in range(lefti, i):
                #     for j1 in range(leftj, j):
                #         a1 = findMinArea(lefti, i1, leftj, j1)
                #         a2 = findMinArea(i1 + 1, i, leftj, j1)
                #         a3 = findMinArea(lefti, i1, j1 + 1, j)
                #         a4 = findMinArea(i1 + 1, i, j1 + 1, j)
                #         count = (a1 > 0) + (a2 > 0) + (a3 > 0) + (a4 > 0)
                #         if count == 2:
                #             ans = min(ans, a1 + a2 + a3 + a4)
            if times == 3:
                for i2 in range(lefti, i):
                    ans = min(ans, findMinArea(i2 + 1, i, leftj, j) + dp(lefti, i2, leftj, j, 2))
                    ans = min(ans, dp(i2 + 1, i, leftj, j, 2) + findMinArea(lefti, i2, leftj, j))
                for j2 in range(leftj, j):
                    ans = min(ans, findMinArea(lefti, i, j2 + 1, j) + dp(lefti, i, leftj, j2, 2))
                    ans = min(ans, dp(lefti, i, j2 + 1, j, 2) + findMinArea(lefti, i, leftj, j2))
                for i1 in range(lefti, i):
                    for j1 in range(leftj, j):
                        a1 = findMinArea(lefti, i1, leftj, j1)
                        a2 = findMinArea(i1 + 1, i, leftj, j1)
                        a3 = findMinArea(lefti, i1, j1 + 1, j)
                        a4 = findMinArea(i1 + 1, i, j1 + 1, j)
                        count = (a1 > 0) + (a2 > 0) + (a3 > 0) + (a4 > 0)
                        # print(count, i1, j1, i, j)
                        if count == 3:
                            ans = min(ans, a1 + a2 + a3 + a4)
            return ans
        return dp(0, len(grid) - 1, 0, len(grid[0]) - 1, 3)