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

一、本周周赛总结

• 都挺难的，幸好没打。
• 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 = 0
        for 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]]
                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、[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 = 0
            for x,y in zip(a,b):
                if x == y:
                    continue
                d += 1
                if d >=3:
                    return d
            return 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)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

四、[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 = 0
        ans = inf
        for 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

1. 题目描述

2. 思路分析

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

---

• 补充：这题可以用两个单调栈把复杂度优化到O(n)。
• 我们知道如果这题求下一个更大的数，用一个单调栈即可。如果要第二个，那就2个单调栈。
• 单个单调栈时，出栈时，出栈元素就找到了右边第一个比它大的数。那么我们把这个出栈的数放到一个新的栈，再次遇到更大的数时，出栈就是第二个比它大的数。
• 注意，元素从第一个单调栈到第二个单调栈时要保持元素下标顺序。

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 SortedList
        h = 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 <len(h):
                ans[i] = nums[h[p+1]]
                
            t.append((x,i))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

单调栈

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1]*n 
        s,t = [],[]
        for i,v in enumerate(nums):            
            while t and nums[t[-1]] < v:
                ans[t.pop()] = v
            x = []
            while s and nums[s[-1]] < v:
                x.append(s.pop())
            t += x[::-1]
            s.append(i)
        
        return ans   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六、参考链接