LeetCode笔记：Weekly Contest 332

• LeetCode笔记：Weekly Contest 332
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-332/

1. 题目一

给出题目一的试题链接如下：

• 2562. Find the Array Concatenation Value

1. 解题思路

这一题按照题意不断地取首尾元素合并求和一下即可。

2. 代码实现

给出python代码实现如下：

class Solution:def findTheArrayConcVal(self, nums: List[int]) -> int:i, j = 0, len(nums)-1res = 0while i < j:res += int(str(nums[i]) + str(nums[j]))i += 1j -= 1if i == j:res += nums[i]return res

提交代码评测得到：耗时56ms，占用内存13.9MB。

2. 题目二

给出题目二的试题链接如下：

• 2563. Count the Number of Fair Pairs

1. 解题思路

这一题我们只需要将原数组进行排序，然后找到上下限元素之间的区间即可，这个可以通过二分搜索来快速得到。

唯一需要注意的就是如果两倍自身也在范围内的话需要刨除自身。

2. 代码实现

给出python代码实现如下：

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:nums = sorted(nums)res = 0for i, x in enumerate(nums):lb = bisect.bisect_left(nums, lower - x)rb = bisect.bisect_right(nums, upper - x)if lower-x <= x <= upper-x:res += rb - lb -1else:res += rb - lbreturn res // 2 

提交代码评测得到：耗时908ms，占用内存29MB。

3. 题目三

给出题目三的试题链接如下：

• 2564. Substring XOR Queries

1. 解题思路

因为a^x^x=a，因此，对于每一个query，我们事实上就是要找到query当中两数的异或值在给出的字符串当中出现的最早的位置即可。

但是这个query会很繁琐，所以我们事先将字符串当中所有出现的有效字符串全部保存起来，从而加速检索速度。

2. 代码实现

给出python代码实现如下：

class Solution:def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:n = len(s)mem = {}for i in range(n):if s[i] == "0":if "0" not in mem:mem["0"] = [i, i]continuefor j in range(min(i+30, n), i, -1):sub = s[i:j]if sub in mem:breakmem[sub] = [i, j-1]res = [mem.get(bin(x^y)[2:], [-1, -1]) for x, y in queries]return res

提交代码评测得到：耗时1359ms，占用内存79.7MB。

4. 题目四

给出题目四的试题链接如下：

• 2565. Subsequence With the Minimum Score

1. 解题思路

这一题因为只考虑删除t中的字符的头尾位置，使得其为s的子串，而不需要考虑其中间的字符删除多少。

因此，我们就是要考察t当中头尾子串保留的长度即可。

也就是说，我们考虑要覆盖t中头部的每一串子串所需要的s当中的头部长度，然后同步考察要覆盖t中尾部每一个子串所需要的s当中的尾部的长度。

如果两者不交叠，那么两者之间的长度就是一组可行的删除方法，然后我们从中取出最小值即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumScore(self, s: str, t: str) -> int:n, m = len(s), len(t)l2r = [n for _ in range(m)]i = 0for j in range(m):while i < n and s[i] != t[j]:i += 1if i == n:breakl2r[j] = ii += 1r2l = [-1 for _ in range(m)]i = n-1for j in range(m-1, -1, -1):while i >= 0 and s[i] != t[j]:i -= 1if i == -1:breakr2l[j] = ii -= 1res = min(bisect.bisect_left(r2l, 0), m-bisect.bisect_left(l2r, n))for i, idx in enumerate(l2r):if idx <= r2l[i]:return 0elif idx == n:if r2l[i] >= 0:res = min(res, i)else:j = bisect.bisect_left(r2l, idx+1)if j > i:res = min(res, j-i-1)return res

提交代码评测得到：耗时209ms，占用内存19.6MB。