[LeetCode周赛复盘] 第 315 场周赛20221016

一、本周周赛总结

• T2下标j写成iwa一次。
• T4回文数不熟练wa一次，然后题目卡常数tle两次。
• T2暴力。
• T3bfs+模拟。
• T4 两个dp。
  

二、 [Easy] 6233. 温度转换

链接: 6233. 温度转换

1. 题目描述

2. 思路分析

签到。

3. 代码实现

class Solution:
    def convertTemperature(self, c: float) -> List[float]:
        return [c+273.15,c*1.80+32]
1
2
3

三、[Medium] 6234. 最小公倍数为 K 的子数组数目

链接: 6234. 最小公倍数为 K 的子数组数目

1. 题目描述

2. 思路分析

• 由于lcm具有继承性，因此遍历即可。
• 枚举固定左端点，向右扩展右端点，符合lcm就ans+1。
• 这里可以优化，由于lcm不会减小，因此如果遇到大的就break。

3. 代码实现

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        ans = 0
        n = len(nums)
        q = deque()
        for i in range(n):
            p = nums[i]
            for j in range(i,n):
                p = lcm(p,nums[j])
                if p == k:
                    # print(i,j,p)
                    ans += 1
                elif p > k:
                    break
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

四、[Medium] 6235. 逐层排序二叉树所需的最少操作数目

链接: 6235. 逐层排序二叉树所需的最少操作数目

1. 题目描述

2. 思路分析

• 显然层序遍历，分别处理每一层然后加起来即可。
• 问题转化成对每层的数组，求最小的交换次数使数组有序。
• 方案是对照每个数sort后该在的位置p，向p交换，换下来的数继续找对应位置，直到匹配了，再看下一个数。

3. 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def calc(a):
    t = sorted(a)
    p = {x:i for i,x in enumerate(t)}
    n = len(a)
    ans = 0
    for i in range(n):
        while a[i] != t[i]:
            ans += 1
            j = p[a[i]]
            a[i],a[j] = a[j],a[i]
    return ans                   
        
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        ans = 0
        while q:
            nq = []
            for _ in range(len(q)):
                o = q.popleft()
                if o.left:
                    q.append(o.left)
                    nq.append(o.left.val)
                if o.right:
                    q.append(o.right)
                    nq.append(o.right.val)
            if nq:
                ans += calc(nq)
        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
24
25
26
27
28
29
30
31
32
33
34
35
36

五、[Hard] 6236. 不重叠回文子字符串的最大数目

链接: 6236. 不重叠回文子字符串的最大数目

1. 题目描述

2. 思路分析

• 这题要求不重叠，因此f[i]至少是f[i-1],其中f[i]是前缀答案。
• 那么我们如果可以快速求出某一段如[k…i]是否是回文，那么f[i] =f[k-1]+is_huiwen(k,i)
• 这里复杂度是O(n*n)。
• 至于回文段显然可以用n方预处理出来，然后查询时O(1)。比赛时不熟练，写错了一次，立刻改记忆化搜索了。

3. 代码实现

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        if k == 1:
            return n
        # f = [[0]*n for _ in range(n)]  # f[i][j]区间的值
        f = [0]*n  # 前缀答案
   
        @cache 
        def is_hui(l,r):
            if l == r:
                return 1
            if l>r:
                return 1
            if l+1 == r:
                return int(s[l]==s[r])
            return int(s[l]==s[r] and is_hui(l+1,r-1))
        
        f[k-1] = is_hui(0,k-1)
        # print(k)
        for i in range(k,n):
            f[i] = f[i-1]
            for l in range(i-k+1,-1,-1):
                if is_hui(l,i):
                    f[i] = max(f[i],f[l-1]+1 if l >= 0 else 1)
                    break
        # print(f)
        is_hui.cache_clear()
        return f[-1]            
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

六、参考链接