[LeetCode周赛复盘] 第 332 场周赛20230212
-
- 一、本周周赛总结
- 二、 [Easy] 6354. 找出数组的串联值
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、[Medium] 6355. 统计公平数对的数目
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、[Medium] 6356. 子字符串异或查询
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 五、[Hard] 6357. 最少得分子序列
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
一、本周周赛总结
- 刷新个人历史最佳64名，希望别re。
- T1 对向双指针/deque模拟。
- T2 排序+二分。
- T3 哈希表+位运算暴力枚举。
- T4 dp前后缀分解子序列+二分/双指针。
[LeetCode周赛复盘] 第 332 场周赛20230212
二、 [Easy] 6354. 找出数组的串联值
链接: 6354. 找出数组的串联值
1. 题目描述
2. 思路分析
按题意模拟即可。
3. 代码实现
class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
ans = 0
q = 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 = 0
nums.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-d
if 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]*n
j = 0
for i,c in enumerate(t):
while j < m and s[j] != c:
j += 1
if j == m:
break
pre[i] = j
j += 1
suf = [-1]*n
j = m-1
for i in range(n-1,-1,-1):
while j >=0 and s[j] != t[i]:
j -= 1
if j < 0:
break
suf[i] = j
j -= 1
if 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 = 0
for i,v in enumerate(suf):
while j<i and pre[j] < v:
j += 1
if j and v > pre[j-1]:
ans = min(ans,i-j)
return ans