本文主要是介绍[LeetCode周赛复盘] 第 325 场周赛20221225,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
[LeetCode周赛复盘] 第 325 场周赛20221225
- 一、本周周赛总结
- 二、 [Easy] 6269. 到目标字符串的最短距离
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、[Medium] 6270. 每种字符至少取 K 个
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、[Medium] 6271. 礼盒的最大甜蜜度
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 五、[Hard] 6272. 好分区的数目
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
一、本周周赛总结
- T1暴力。
- T2滑窗。
- T3二分。
- T4背包。
二、 [Easy] 6269. 到目标字符串的最短距离
链接: 6269. 到目标字符串的最短距离
1. 题目描述
2. 思路分析
两种遍历,找最短的写。
3. 代码实现
class Solution:def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:n = len(words)if target not in words:return -1# a = 0# for i in range(n):# if words[(i+startIndex)%n] == target:# a = i# break# b = 0# for i in range(n):# if words[(startIndex-i)%n] == target:# b = i# break# return min(a,b)ans = nfor i,w in enumerate(words):if w == target:ans = min(ans,(i-startIndex)%n,(startIndex-i)%n)return ans
三、[Medium] 6270. 每种字符至少取 K 个
链接: 6270. 每种字符至少取 K 个
1. 题目描述
2. 思路分析
- 把s翻倍,然后在中间位置滑窗,即有效的答案窗口必须包含n-1或者n的位置。
- 灵神的思路是,先从后缀找到最小合法串,然后尝试增加前缀,减小后缀。
- 还有一种滑窗思路,从中间去掉最长一段,使剩下的abc个数满足题意;即中间段的abc个数需要<=原数-k
3. 代码实现
翻倍滑窗
class Solution:def takeCharacters(self, s: str, k: int) -> int:c = Counter(s)if any(c[x]<k for x in 'abc'):return -1if k == 0:return 0ss = s + sn = len(s)c = Counter()q = deque()ans = inffor r,v in enumerate(ss):c[v] += 1q.append(r)while q and c[ss[q[0]]] > k:c[ss[q.popleft()]] -= 1# print(c,q)if len(q)<ans and len(q)>=3*k and q[0]<=n and q[-1]>=n-1 and c['a']>=k and c['b']>=k and c['c']>=k:ans = len(q)return ans)
前后双指针
class Solution:def takeCharacters(self, s: str, k: int) -> int:c = Counter(s)if any(c[x]<k for x in 'abc'):return -1if k == 0:return 0j = n = len(s)c = Counter() q = deque()while c['a']<k or c['b']<k or c['c']<k: j -= 1q.appendleft(j)c[s[j]] += 1ans = len(q)for i,v in enumerate(s):c[v] += 1while q and c[s[q[0]]] > k:c[s[q.popleft()]] -= 1# print(c,q)ans = min(ans,len(q)+i+1)return ans
四、[Medium] 6271. 礼盒的最大甜蜜度
链接: 6271. 礼盒的最大甜蜜度
1. 题目描述
2. 思路分析
- 最小值最大化,又是二分。
- ok(x)代表任意差不小于x时,能否找出k类糖果;显然x越小,越能满足。单调的。
- ok函数内部贪心,由于要尽可能多去多选,因此可以必选最小的,然后向后尽可能取最近的满足超过x的糖果。计数能否满足k个即可。
3. 代码实现
class Solution:def maximumTastiness(self, price: List[int], k: int) -> int:n = len(price)mx = max(price) - min(price)if k == 2:return mxprice.sort()def ok(x):# 二分判断模板,越小的x满足要求,则yes=0 no=1,答案应是最后一个0的位置即bisect_left(range(xxx),1,key=ok)-1yes,no = 0,1c = 1 # 计数pre = price[0]for p in price[1:]:if p-pre>=x:c += 1pre = pif c>=k:return yes # 足够了return noreturn bisect_left(range(mx+1),1,key=ok)-1
五、[Hard] 6272. 好分区的数目
链接: 6272. 好分区的数目
1. 题目描述
2. 思路分析
- 这题目一看像背包,但又发现要>=k的数量,不好写。
- 因此反着算,求<k的方案数,再计算总体方案数,相减即可。
- 比赛时由于不会特判错误情况,只能最后判断大小,导致中途不能取模,很可能TLE,但是赛后造了下数据没有TLE,很怪。可能力扣的数据量还是不够极限。
- 定义f[j]为取任意数求和为j的方案数,由于两边是对称的且不会重(提前特判了非法的重复),因此我们可以sum(f)*2来计算总的<k的方案数。
3. 代码实现
MOD = 10**9 + 7
class Solution:def countPartitions(self, nums: List[int], k: int) -> int: # 特判很关键,代表任意分组都无法让两边同时满足;这样就会剔除背包计算出来的一边小于k,但另一边也小于k的重复数据# 即:背包的结果一定是一边小于k,而剩下的不小于k,对称无重复,可以放心乘2if k*2>sum(nums): return 0f = [0]*kf[0] = 1for x in nums:for j in range(k-1,x-1,-1):f[j] = (f[j] + f[j-x]) % MODreturn (pow(2, len(nums), MOD) - sum(f)*2%MOD) %MOD# # # #以下是错误答案,由于不会上边那个特判,因此只能最后判断大小,导致中途不敢取模,大数据必TLE# n = len(nums)# f = [0]*k# f[0] = 1# for x in nums:# for j in range(k-1,x-1,-1):# f[j] += f[j-x]# print(n)# a = 2**n# b = sum(f)*2# if a <= b:# return 0# return (2**n - sum(f)*2)%MOD
六、参考链接
这篇关于[LeetCode周赛复盘] 第 325 场周赛20221225的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!