[LeetCode周赛复盘] 第 311 场周赛20220918

一、本周周赛总结

• 这场很水！手速场，是我目前最好成绩了。
• T4模板不熟悉调了半天，要不然还能进两分钟
  

二、 [Easy] 6180. 最小偶倍数

链接: 6180. 最小偶倍数

1. 题目描述

。

2. 思路分析

定级Easy。
就是lcm，最小公倍数。
由于是和2取最小公倍：奇数的是2*x,偶数是x本身。
或者用库函数lcm也可以。

3. 代码实现

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        if n&1==0:
            return n
        else:
            return n*2
1
2
3
4
5
6

三、[Medium] 6091. 划分数组使最大差为 K

链接: 6091. 划分数组使最大差为 K

1. 题目描述

2. 思路分析

定级Medium。

• 裸DP了可以说是。
• 定义f[i]为以i为结尾的连续字符串长度。
• 显然每个位置至少是1.
• 如果当前字符和前一个字符连续，那么当前f[i] = f[i-1]+1
• 最后求max即可。

3. 代码实现

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        n = len(s)
        f = [1]*n
        for i in range(1,n):
            if ord(s[i])- ord(s[i-1]) == 1:
                f[i] = f[i-1]+1
        return max(f)
1
2
3
4
5
6
7
8

四、[Medium] 6182. 反转二叉树的奇数层

链接: 6182. 反转二叉树的奇数层

1. 题目描述

2. 思路分析

定级Medium。

• 一个较裸的层先。
• 由于是完全二叉树，每层节点数是偶数。
• 判断一下层数，翻转即可。

3. 代码实现

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        q = [root]
        depth = 0
        while q:
            nq = []
            
            for u in q:
                if u.left:
                    nq.append(u.left)
                if u.right:
                    nq.append(u.right)
            if depth & 1:
                n = len(q)
                for i in range(n//2):
                    q[i].val, q[n-i-1].val = q[n-i-1].val, q[i].val                       
            
            depth += 1
            q = nq
        return root
            
        
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

五、[Hard] 6183. 字符串的前缀分数和

链接: 6183. 字符串的前缀分数和

1. 题目描述

2. 思路分析

定级Hard。

• 字典树模板题。
• py写字典树就是方便，不用数组了!
• 建树的时候记录每层字符出现次数。
• 然后遍历每个字符串，在树中find的时候，累加每个字符对应的次数即可。

3. 代码实现

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        trie = {}
        for s in words:
            pos = trie
            for c in s:
                if c not in pos:
                    pos[c] = {}
                    pos[c]['cnt'] = 0
                pos = pos[c]
                pos['cnt'] += 1
            pos['end'] = s
        # print(trie)
        
        ans = []
        def find(s):
            pos = trie
            ret = 0
            for c in s:
                if c not in pos:
                    return ret
                ret += pos[c]['cnt']
                pos = pos[c]
                # if 'end' in pos:
                #     return
            return ret
                
        for s in words:
            ans.append(find(s))
        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

六、参考链接

• 链接: [python刷题模板] 字典树