Skip to main content

周赛 Weekly Contest 402

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

https://www.bilibili.com/video/BV1T1421k7Hi/?spm_id_from=333.999.0.0&vd_source=66a0b89065d7f04805223fd7f2d613a6

521. Longest Uncommon Subsequence I​

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return -1 if a == b else max(len(a), len(b))

100301. Count Pairs That Form a Complete Day II​

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        d = dict()
        for i in range(25):
            d[i] = 0
        for i in range(len(hours)):
            if hours[i] % 24 == 0:
                d[24] += 1
            else:
                d[hours[i] % 24] += 1
        
        def sum_n_to_1(n):
            if n < 1:
                return 0
            return n * (n + 1) // 2

        print(d)
        cnt = 0
        for i in range(1, 25, 1):
            if i == 24:
                cnt += sum_n_to_1(d[i]-1)
            elif i == 12:
                cnt += sum_n_to_1(d[i]-1)
            else:
                if i < 12:
                    cnt += d[i] * d[24-i]
        return cnt




        # def sum_n_to_1(n):
        #     if n < 1:
        #         return 0
        #     return n * (n + 1) // 2

        # d = dict()
        # d[24] = 0
        # for i in range(len(hours)):
        #     if hours[i] % 24 == 0:
        #         hours[i] = 24
        #         d[24] += 1
        #     else:
        #         if hours[i] not in d:
        #             d[hours[i]] = 1
        #         else:
        #             d[hours[i]] += 1

        # hours = list(set(hours))
        # cnt = 0
        # for i in range(len(hours)):
        #     if ((hours[i]) % 24 == 0 or (hours[i]+hours[i]) % 24 == 0) and d[hours[i]] > 1:
        #         cnt += sum_n_to_1(d[hours[i]]-1) 
        #     for j in range(i+1, len(hours), 1):
        #         if (hours[i] + hours[j]) % 24 == 0:
        #             cnt += d[hours[i]] * d[hours[j]]
        # return cnt

100316. Maximum Total Damage With Spell Casting​

  • DP，记忆化搜索
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        power = sorted(power)
        # d = dict()
        # for p in power:
        #     if p not in d:
        #         d[p] = True
        @cache
        def dfs(i):
            if i >= len(power): return 0
            cnt = 0
            num = power[i]
            while i < len(power) and num == power[i]:
                i += 1
                cnt += 1

            # choose, skip next and next next
            j = i
            while j < len(power) and (power[j] == num+1 or power[j] == num+2):
                j += 1
            ans = cnt * num + dfs(j)
            
            # won't choose, skip same
            ans = max(ans, dfs(i))
            return ans
        
        return dfs(0)

100317. Peaks in Array​

  • 树状数组