[LeetCode周赛复盘] 第 306 场周赛20220814

一、本周周赛总结

• 几乎全是模拟题，除了第二题是一道同向双指针。
• 第二次打力扣周赛就ak了，这周的题好水啊。
• 前排的大佬真就做阅读理解呗，读完题=会了。
  

二、 [Easy] 6148. 矩阵中的局部最大值

链接: 6148. 矩阵中的局部最大值

1. 题目描述

2. 思路分析

定级Easy。
按题意暴力模拟即可。

3. 代码实现

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        m,n = len(grid),len(grid[0])
        ans = [[0]* n for _ in range(m)]
        for i in range(1,m-1):
            for j in range(1,n-1):
                ans[i][j] = max(grid[i-1][j-1:j+2]+grid[i][j-1:j+2]+grid[i+1][j-1:j+2])
        
        return [ans[i][1:n-1] for i in range(1,m-1)]
1
2
3
4
5
6
7
8
9

三、[Medium] 6149. 边积分最高的节点

链接: 6149. 边积分最高的节点

1. 题目描述

2. 思路分析

一开始看成所有路径指向它的点，其实是直接指向，看邻边累加即可。

编程比赛三大赛制介绍（ACM赛制、OI赛制、IOI赛制）-2020.11.07.pdf

pdf 0星 超过10%的资源 103KB

下载

3. 代码实现

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)
        f = [0] * n
        vis = [0] * n
        for u,v in enumerate(edges):
            f[v] += u
        # print(f)
        ans = 0
        for i in range(1,n):
            if f[i]>f[ans]:
                ans = i
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

四、[Medium] 6150. 根据模式串构造最小数字

链接: 6150. 根据模式串构造最小数字

1. 题目描述

2. 思路分析

定级Medium。

• dp预处理一个r数组，r[i]代表数i右边有多少个D。
• 遇到I则直接置0.
• 然后用有序集合维护剩余的数字，如果当前位置右边有x个D，则代表它最小只能取当前第x小的数字。

3. 代码实现

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)+1
        from sortedcontainers import SortedList
        s = SortedList(range(1,n+1))
        
        r = [0]*n
        for i in range(n-2,-1,-1):
            if pattern[i] == 'D':
                r[i] = r[i+1] +1
            else:
                r[i] = 0
        ans=[0]*n
        for i in range(n):
            if r[i]<=0:
                ans[i] = s.pop(0)
                # s.popleft()
            else:
                ans[i] = s.pop(r[i])
        return ''.join(map(str,ans))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

五、[Hard] 6151. 统计特殊整数

链接: 6151. 统计特殊整数

1. 题目描述

2. 思路分析

定级Hard。
数位dp，参考力扣 357. 统计各位数字都不同的数字个数.

3. 代码实现

class Solution:
    def countSpecialNumbers(self, x: int) -> int:
        f = [[0]*10 for _ in range(10)]
        for i in range(1,10):
            for j in range(1,10):
                cur = 1
                for k in range(i,j+1):
                    cur *= k
                f[i][j] = cur
        
        t = x
        nums = []
        while t:
            nums.append(t%10)
            t //= 10
        n = len(nums)
        if n<=1:
            return x
        ans = 0
        p = 1
        s = 0
        for i in range(n-1,-1,-1):
            cur = nums[i]
            cnt = 0
            for j in range(cur-1,-1,-1):
                if i == n-1 and j == 0:
                    continue
                if ((s>>j)&1) == 0:
                    cnt += 1
            a = 10-p
            b = a-(n-p)+1
            ans +=  (cnt * f[b][a] if b<=a else cnt)
            if ((s>>cur)&1) == 1:
                break
            s |= 1<<cur
            if i == 0:
                ans += 1            
            
            p+=1
            
        ans += 10
        last = 9
        for i in range(2,n):
            cur = last*(10-i+1)
            ans += cur
            last = cur
        return ans-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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47