[LeetCode周赛复盘] 第 332 场周赛20230212

一、本周周赛总结

• 刷新个人历史最佳64名，希望别re。
• T1 对向双指针/deque模拟。
• T2 排序+二分。
• T3 哈希表+位运算暴力枚举。
• T4 dp前后缀分解子序列+二分/双指针。
  

二、 [Easy] 6354. 找出数组的串联值

链接: 6354. 找出数组的串联值

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def findTheArrayConcVal(self, nums: List[int]) -> int:ans = 0q = deque(nums)while q:if len(q)>=2:ans += int(str(q.popleft()) + str(q.pop()))elif len(q)==1:ans += q.pop()return ans

三、[Medium] 6355. 统计公平数对的数目

链接: 6355. 统计公平数对的数目

1. 题目描述

2. 思路分析

比赛时无脑用了SortedList，其实排序就行了。常数低很多。

• 由于要求的数对和顺序无关，因此可以直接排序。
• 对每个数查找是否存在对应的边界，二分这两个边界即可。
• 注意hi=i，因为每个数只能从前边的数取，否则会取两次。

3. 代码实现

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:ans = 0nums.sort()for i,v in enumerate(nums):ans += bisect_right(nums,upper-v,hi=i) - bisect_left(nums,lower-v,hi=i)          return ans 

四、[Medium] 6356. 子字符串异或查询

链接: 6356. 子字符串异或查询

1. 题目描述

2. 思路分析

• 首先题目的公式可以转化成val = first^second。求val是否存在于s中，且找最短那段。
• 由于数据量是10**9,即30位，那么可以暴力枚举长为1到30的所有子串，也就3e5。
• 用哈希表记录每个子串数字对应的下标范围，且记录最短那段即可。
• 我这里用了切片，其实可以累积，且可以枚举长度，这样不用比较更新，会更快。

3. 代码实现

class Solution:def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:n = len(s)qs = set([x^y for x,y in queries])ans = {}for r in range(n):for d in range(31):l = r-dif l >= 0:x = int(s[l:r+1],2)if x in qs:if x not in ans:ans[x] = (l,r)else:a,b = ans[x]if b-a>r-l:ans[x] = [l,r]return [ ans.get(x^y,(-1,-1)) for x,y in queries]

五、[Hard] 6357. 最少得分子序列

链接: 6357. 最少得分子序列

1. 题目描述

2. 思路分析

• pre[i] = x 表示t对应前缀可以匹配到s[:x+1]。
• suf[i] = y 表示t对应后缀可以匹配到s[y:]。
• 那么当我们处理suf[r]时，pre中r之前的数pre[l]只要小于suf[r]，我们就可以删除(l,r)之间的数字，实现t的前后缀分别匹配s的前后缀。
• 注意前后缀只有1种的情况。

3. 代码实现

class Solution:def minimumScore(self, s: str, t: str) -> int:m,n = len(s),len(t)pre = [m]*nj = 0for i,c in enumerate(t):while j < m and s[j] != c:j += 1if j == m:break pre[i] = jj += 1suf = [-1]*nj = m-1for i in range(n-1,-1,-1):while j >=0 and s[j] != t[i]:j -= 1if j < 0:break suf[i] = j j -= 1if pre[0] == n and suf[-1] == -1:return n# print(pre)# print(suf)ans = min(n - bisect_left(pre,m),bisect_right(suf,-1))  # 没有前缀或后缀的情况    j = 0for i,v in enumerate(suf):while j<i and pre[j] < v:j += 1if j and v > pre[j-1]:ans = min(ans,i-j)                   return ans       

六、参考链接