[LeetCode周赛复盘] 第 321 场周赛20221127

一、本周周赛总结

• 好难啊，但是怎么过的人这么多。
• T1暴力或者公式。
• T2子序列双指针。
• T3链表题。
• T4前缀和+哈希表，两种做法。
  

二、 [Easy] 6245. 找出中枢整数

链接: 6245. 找出中枢整数

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:
    def pivotInteger(self, n: int) -> int:
        s = (1+n)*n//2
        p = 0
        for i in range(1,n+1):
            p += i
            if p == s - p + i:
                return i 
        return -1
1
2
3
4
5
6
7
8
9

三、[Medium]6246. 追加字符以获得子序列

链接: 6246. 追加字符以获得子序列

1. 题目描述

2. 思路分析

按题意模拟即可。

• 和判断子序列很像，直接双指针扫描即可。
• 看s最多能匹配t前缀多长。

3. 代码实现

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        m,n = len(s),len(t)
        j = 0
        for i,c in enumerate(s):
            if j<n and t[j] == c:
                j += 1
            if j == n:
                return 0
        # print(n,j)
        return n - j
1
2
3
4
5
6
7
8
9
10
11

四、[Medium] 6247. 从链表中移除节点

链接: 6247. 从链表中移除节点

1. 题目描述

2. 思路分析

• 比赛时直接转数组然后dp做的，其实可以递归，下面给出递归写法。

3. 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """最后的结果，head一定是最大的，且后缀同样满足这个属性，因此可以递归
        """
        if not head :return head 
        nxt = self.removeNodes(head.next)
        if not nxt:return head 
        if nxt.val > head.val :return nxt 
        head.next = nxt
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

五、[Hard] 6248. 统计中位数为 K 的子数组

链接: 6248. 统计中位数为 K 的子数组

1. 题目描述

2. 思路分析

• 比赛时写了比较麻烦的左右前缀和，还wa一次。
• 注意题目，数据是1-n的排列。意味着k一定只出现一次。找到k的位置p。所有子数组都要包含p。
• k如果是中位数的话，这个数组里小于k的数less一定等于大于k的数big，或less+1=big(偶数长度情况)
• 于是我们从p出发向两侧扩展数组，使用前缀和统计两边子数组less和big的大小计数。
• 于是就可以用乘法原理乘起来即可。

---

• 更简单的方法可以转换，把原数组转化为：小于k记-1，大于k记1，等于k记10**6。
• 题目转化成有多少个子数组，子数组和=106或106+1。
• 这题就是普通的前缀和+哈希表。

3. 代码实现

转化为前缀和+哈希表

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        a = []
        mx =10**6
        for v in nums:
            if v < k:
                a.append(-1)
            elif v>k:
                a.append(1)
            else:
                a.append(mx)
        s = 0
        d = Counter()
        d[0] = 1
        ans = 0
        for i,v in enumerate(a):            
            s += v
            ans += d[s-mx]+d[s-mx-1]
            d[s] += 1            
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

左右前缀和

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        d = {(0,0,0):1}
        p = nums.index(k)
        ans = 1
        
        l,r = Counter(),Counter()
        s = 0
        for j in range(p+1,n):
            s += 1 if nums[j]>k else -1
            r[s] += 1
        ans += r[0]+r[1]
        s = 0
        for j in range(p-1,-1,-1):
            s += 1 if nums[j]>k else -1
            l[s] += 1
        ans += l[0]+l[1]
        
        ans += l[0]*r[0]
        for i in range(1,n):
            ans += l[i]*r[-i]+l[i]*r[-i+1]+r[i]*l[-i]+r[i]*l[-i+1]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

六、参考链接