[LeetCode周赛复盘补] 第 第 90 场双周赛20221015

• • 一、本周周赛总结
  • 二、 [Easy] 6225. 差值数组不同的字符串
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、[Medium] 6228. 距离字典两次编辑以内的单词
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、[Medium] 6226. 摧毁一系列目标
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 五、[Hard] 6227. 下一个更大元素 IV
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、参考链接

一、本周周赛总结

• 都挺难的，幸好没打。
• T1遍历，分别哈希。
• T2遍历，贪心
• T3取模哈希计算最多的模。
• T4离线+有序集合+队列+二分。

二、 [Easy] 6225. 差值数组不同的字符串

链接: 6225. 差值数组不同的字符串

1. 题目描述

2. 思路分析

按题意模拟。

• 由于是补题，没写的特别暴力。
• 纵向比较，对每一位的差，计数所有单词中这个位置的差，如果有不同的，显然单独那个就是答案。
• wa了一次因为n和m写错了。

3. 代码实现

class Solution:def oddString(self, words: List[str]) -> str:m,n = len(words),len(words[0])ans = 0for i in range(n-1):s = defaultdict(list)for j in range(m):y = ord(words[j][i]) - ord(words[j][i+1])s[y].append(j)# print(s)if len(s)>1:for k,v in s.items():if len(v)==1:return words[v[0]]

三、[Medium] 6228. 距离字典两次编辑以内的单词

链接: 6228. 距离字典两次编辑以内的单词

1. 题目描述

2. 思路分析

• 一开始想到了搜索，然后琢磨优化建图，于是把dic中所有字符串都加上了单个变*的版本。
• 最后发现根本不需要，直接计算差异距离<=2即可。可52ms通过。

3. 代码实现

class Solution:def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:# 1072 ms# d = set(dictionary)  # 储存dic和dic每个单词枚举每个字符变*，最多共2*n个元素# n = len(queries[0])# for s in dictionary:  # 复杂度n*n#     p = list(s)#     for i in range(n):#         t = p[i]#         p[i]='*'#         d.add(''.join(p))#         p[i]=t# def calc_dis(a,b): # 计算a和b的距离,复杂度n#     d = 0#     for x, y in zip(a,b):#         if x == y or y == '*':#             continue#         d += 1#         if d>=2:  # 2以上都没用，提前返回#             return d #     return d            # def calc_min_dis_less_than_2(s):  # 查询是否存在一个目标元素的编辑距离距s小于2（最大是1）#     for b in d:#         if calc_dis(s,b)<2:#             return True #     return False# return [q for q in queries if calc_min_dis_less_than_2(q)]            def calc_dis(a,b):d = 0for x,y in zip(a,b):if x == y:continued += 1if d >=3:return dreturn d def calc_min_dis_less_than_3(s):for b in dictionary:if calc_dis(s,b) < 3:return True return False return [q for q in queries if calc_min_dis_less_than_3(q)]

四、[Medium] 6226. 摧毁一系列目标

链接: 6226. 摧毁一系列目标

1. 题目描述

2. 思路分析

• 观察题意公式中的c是任取的，因此对于某个nums[i]，能摧毁的目标就是nums[i]向后移动所有space的倍数。他们的统一特征就是取模=nums[i]%space。
• 因此按取模分组，然后最长的组取组内最小即可。
• 注意多个组长度相同，要min一下组内最小。

3. 代码实现

class Solution:def destroyTargets(self, nums: List[int], space: int) -> int:d = defaultdict(list)for x in nums:d[x%space].append(x)mx = 0ans = inffor k,v in d.items():if len(v)>mx:mx = len(v)ans = min(v)elif len(v) == mx:ans = min(ans,min(v))return ans

五、[Hard] 6227. 下一个更大元素 IV

链接: 6227. 下一个更大元素 IV

1. 题目描述

2. 思路分析

• 想了很久，一开始试图用堆没搞定，换用了SortedList。
• 我们发现每个数计算答案只依赖于它右边比它大的数。
• 因此先考虑从右开始遍历，但这样的话向左递推时，寻找当前数字t右边比t大的数，则要维护右边所有值，但可能存在多个值，这时难以处理下标最小的两个。
• 那么换种思路。
• 我们把查询离线，从大的数开始遍历。由于每个数仅依赖比它大的数，因此每次计算时，它所需要的数都在我们维护的数据结构中。
• 我们用h=SortedList来维护已遍历的数的下标。那么只要找到当前下标在h中的位置p，那么p后边第二个下标就是目标下标。
• 注意，由于数据中可能出现相同的数，而这些数是不符合条件的（题目要求必须严格大于）。因此我们数据入h之前先存放在一个队列中，每次处理答案之前先看看队列中的数据是否可以入h（不相同就能入，否则不入，用之前的h）。

3. 代码实现

class Solution:def secondGreaterElement(self, nums: List[int]) -> List[int]:n = len(nums)ans = [-1]*n a = sorted(zip(nums,range(n)),reverse=True)from sortedcontainers import SortedListh = SortedList()t = deque()for x,i in a:while t and t[0][0] != x:h.add(t.popleft()[1])p = h.bisect_left(i)if p + 1