数据结构与算法|【算法】力扣第 266场周赛算法|动态规划|leetcode

5918. 统计字符串中的元音子字符串看数据范围，暴力过

class Solution: def countVowelSubstrings(self, word: str) -> int: res=0 n=len(word) for a in range(n): for b in range(a+5,n+1): i=word[a:b] if any(x not in 'aeiou' for x in i):continue if 'a' in i and 'e' in i and 'i' in i and 'o' in i and 'u' in i: res+=1 return res

5919. 所有子字符串中的元音第一次考虑前缀和做，子字符串word[a:b]内的元音字符数为pre[b+1]-pre[a]

class Solution: def countVowels(self, word: str) -> int: n=len(word) res=0 dic=[0]*n for i in range(n): if word[i] in ('a','e','i','o','u'): dic[i]=1pre=[0,*accumulate(dic)]for a in range(n): for b in range(a,n): res+=pre[b+1]-pre[a] return res

果然超时，找一下规律，可以发现pre[i]的个数为2*i-n

class Solution: def countVowels(self, word: str) -> int: n=len(word) res=0 dic=[0]*n for i in range(n): if word[i] in 'aeiou': dic[i]=1pre=[0,*accumulate(dic)]for i in range(n+1): res+=(2*i-n)*pre[i] return res

整理下变成python二行

class Solution: def countVowels(self, word: str) -> int: pre=[0,*accumulate([1 if word[i] in 'aeiou' else 0for i in range(len(word))])] return sum((2*i-len(word))*pre[i] for i in range(len(word)+1))

5921. 最大化一张图中的路径价值这次的T4比较简单，看下数据范围：

n == values.length
1 <= n <= 1000
10 <= timej, maxTime <= 100
每个节点至多有四条边

直接暴搜+回溯

class Solution: def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int: n=len(values) dic={i:list() for i in range(n)} for e in edges: a,b,c=e dic[a].append([b,c]) dic[b].append([a,c])def dfs(cur,tc,res,nodes): if tc>maxTime: return if cur==0: vc=0 for i in set(nodes): vc+=values[i] res[0]=max(res[0],vc)for x in dic[cur]: nodes.append(x[0]) dfs(x[0],tc+x[1],res,nodes) nodes.pop()res=[0] dfs(0,0,res,[0])return res[0]

5920. 分配给商店的最多商品的最小值最小化最大值问题，首先可见是贪心，其次可以注意到单调性，而后二分求解

class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: l,r=1,max(quantities) while l<=r: mid=l+(r-l>>1) need=sum(ceil(q/mid) for q in quantities) if need>n: l=mid+1 elif need<=n: r=mid-1 return l

875. 爱吃香蕉的珂珂周赛P3换皮题，用来巩固下二分板子

class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: l,r=1,max(piles) while l<=r: mid=l+(r-l>>1) need=sum(ceil(p/mid) for p in piles) if need>h: l=mid+1 elif need<=h: r=mid-1 return l

复盘总结学习一下六弦爷的最短写法！
P1 统计字符串中的元音子字符串

class Solution: def countVowelSubstrings(self, word: str) -> int: return sum(set(word[i: j + 1]) == set('aeiou') for i in range(len(word)) for j in range(i + 1, len(word)))

P2 所有子字符串中的元音

class Solution: def countVowels(self, word: str) -> int: return sum((i + 1) * (len(word) - i) for i, c in enumerate(word) if c in 'aeiou')

【数据结构与算法|【算法】力扣第 266场周赛】P3 分配给商店的最多商品的最小值

class Solution: def minimizedMaximum(self, n: int, Q: List[int]) -> int: class A: def __getitem__(self, x): return sum(q // x + (1 if q % x else 0) for q in Q) <= n return bisect_left(A(), True, 1, max(Q) + 1)