周赛笔记266

一、统计字符串中的元音子字符串

子字符串 是字符串中的一个连续（非空）的字符序列。

元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含 全部五种 元音。

给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        n = len(word)
        res = 0
        for l in range(n-1):
            for r in range(l+1, n+1):
                d = Counter(word[l:r])
                #print(d)
                if all([i in "aeiou"  for i in d.keys()]) and len(set(d.keys()))==5:
                    res += 1
        return res

刚开始不太清醒，在那双指针，后面反应过来第一题都是暴力

二、所有子字符串中的元音

返回 word 的所有子字符串中 元音的总数

class Solution:
    def countVowels(self, word: str) -> int:
        mod = 2**32
        n = len(word)
        res = 0
        for i, c in enumerate(word):
            if c in "aeiou":
                res += (i+1)*(n-i)
                
        return res

以为要取模，wa了一次…

三、分配给商店的最多商品的最小值⭐

将 quantities 数组中的数字分给 n 个桶， 求所有桶中最大值，的最小值

class Solution:
    def minimizedMaximum(self, n: int, q: List[int]) -> int:
        total = sum(q)
        l = ceil(total/n)  #最小可能的值
        r = max(q)   #最大可能的值
        
        while l < r:
            mid = (l+r)//2
            k = sum([ceil(num/mid) for num in q])   #该情况下总桶数
            if k <= n:
                r = mid
            else:
                l = mid + 1
        return l

贪心 + 二分， 666

参考题目：410. 分割数组的最大值

四、最大化一张图中的路径价值

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        d = {i:v for i,v in enumerate(values)}
        res = 0
        #print(d)
        
        f = defaultdict(list)
        for a, b, t in edges:
            f[a].append((b,t))
            f[b].append((a,t))
        
        
        def dfs(node1, time, val, vis):
            #print((node1, time, val, vis))
            nonlocal res
            if time < 0: return
            if node1 == 0:
                res = max(res, val)
            
            for node2, t in f[node1]:
                if node2 not in vis:
                    vis.add(node2)
                    dfs(node2, time-t, val+d[node2], vis)
                    vis.remove(node2)
                else:
                    dfs(node2, time-t, val, vis)
        
        dfs(0, maxTime, d[0], set([0]))
        return res

暴力回溯，哈希优化