Skip to main content

周赛 Weekly Contest 411

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

3258. Count Substrings That Satisfy K-Constraint I​

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        ans = 0
        for i in range(len(s)):
            curZ = 0
            curO = 0
            for j in range(i, len(s), 1):
                if s[j] == "0":
                    curO += 1
                else:
                    curZ += 1
                if curO <= k or curZ <= k:
                    ans += 1
        return ans

3259. Maximum Energy Boost From Two Drinks​

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        n = len(energyDrinkA)
        f = [[0, 0] for _ in range(n+1)]
        f[1][0], f[1][1] = energyDrinkA[0], energyDrinkB[0]
        for i in range(1, n, 1):
            f[i+1][0] = max(f[i][0], f[i-1][1]) + energyDrinkA[i]
            f[i+1][1] = max(f[i][1], f[i-1][0]) + energyDrinkB[i]
        return max(f[n][0], f[n][1])

3260. Find the Largest Palindrome Divisible by K​

hasn't been run yet

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        #4,8,12,16,20,24,28
        #5,
        d = {}
        for i in range(1, 10, 1):
            d[i] = []
            x = 1
            while (i * x)%10 not in d[i]:
                d[i].append((i * x)%10)
                x += 1
            d[i].sort(reverse=True)
            print(d[i])

        return ""

3261. Count Substrings That Satisfy K-Constraint II​

MLE

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        # dp(i, j) = dp(i, j)
        @cache
        def dp(i, j):
            if i > j: return 0, 0
            cnt = 1
            zCnt = 0
            oCnt = 0
            if s[j] == "0": zCnt +=1
            else: oCnt += 1
            retZCnt = zCnt
            retOCnt = oCnt
            if i < j:
                nCnt, nzCnt = dp(i, j-1)
                nOCnt = (j-1 - i) + 1 - nzCnt # SLE
                retZCnt += nzCnt
                retOCnt += nOCnt
                cnt += nCnt
                if retZCnt <= k or retOCnt <= k:
                    cnt += 1
                # for i2 in range(i+1, j, 1): 
                for i2 in range(j-1, i, -1):
                    _, lZ = dp(i2, j-1)
                    lO = (j-1-i2) + 1 -lZ
                    curO = lO + oCnt 
                    curZ = lZ + zCnt
                    if curZ <= k or curO <= k:
                        cnt += 1
                    if curO > k  and curZ > k: # TLE
                        break
            # print(i, j, cnt, retZCnt, retOCnt)
            return cnt, retZCnt 

        res = []
        for qi in range(len(queries)):
            cnt, _ = dp(queries[qi][0], queries[qi][1])
            res.append(cnt)
        return res