前言

前前后后也刷了200多道题了，今天参加了一下这周（2022-8-14）的周赛，前三道题做的还可以，虽然磕磕碰碰但是后面都写出来了。最后一题比较难，因为之前没写过数位DP的题目，所以有点懵逼。这里记录一下…

希望以后可以坚持打打周赛。

我对自己的要求，就是每次必须作对前三道。第四道 hard 有时候会很变态，不强求。

一、Leetcode6148. 矩阵中的局部最大值（easy）

Leetcode6148. 矩阵中的局部最大值

遍历就可以

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

二、Leetcode6149. 边积分最高的节点（Middle）

Leetcode6149. 边积分最高的节点

也是遍历就可以

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)   # n个节点  edges[i]表示i->edges[i]
        # 统计指向某个节点i的节点编号总合和
        res = [0 for _ in range(n)]   # res[i]表示节点i的入度编号总和
        max_v = 0
        for i in range(n):
            res[edges[i]] += i
            max_v = max(res[edges[i]], max_v)
        for i in range(len(res)):
            if res[i] == max_v: return i
1
2
3
4
5
6
7
8
9
10
11

三、Leetcode6150. 根据模式串构造最小数字（Middle）

Leetcode6150. 根据模式串构造最小数字

dfs，这道题有点复杂

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        def dfs(path, idx, mapp):
            if idx == len(pattern):
                a = ''.join(path)
                # print(a)
                if len(self.res) == 0: self.res = a
                else:
                    if a < self.res: self.res = a
                return 
            for num in mapp:
                if pattern[idx] == 'I':
                    if num > int(path[-1]):
                        path.append(str(num))
                        mapp.remove(num)
                        dfs(path, idx+1, mapp)
                        mapp.add(num)
                        path.pop()
                elif pattern[idx] == 'D':
                    if num < int(path[-1]):
                        path.append(str(num))
                        mapp.remove(num)
                        dfs(path, idx+1, mapp)
                        mapp.add(num)
                        path.pop()
        n = len(pattern)
        path, self.res = [], ""
        mapp = set()
        for i in range(1, 10): mapp.add(i)
            
        for k in range(1, 10):
            mapp.remove(k)
            path.append(str(k))
            dfs(path, 0, mapp)
            path.pop()
            mapp.add(k)
        return self.res
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

四、Leetcode6151. 统计特殊整数（hard）

Leetcode6151. 统计特殊整数

数位DP，这道题我没做出来，之前没做过数位DP的内容，拿到题有点懵逼

讲道理这种题这种题面试是不太可能出的，笔试有可能。有点难…

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        # 数位DP
        s = str(n)  
        @cache
        def f(i, mask, is_limit, is_num):
            if i == len(s): return int(is_num)
            res = 0
            if not is_num:
                res = f(i+1, mask, False, False)
            up = int(s[i]) if is_limit else 9
            for d in range(1-int(is_num), up+1):
                if mask >> d & 1==0:
                    res += f(i+1, mask|(1<<d), is_limit and d == up, True)
            return res
        return f(0, 0, True, False)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Reference

【力扣周赛 306】数位 DP | LeetCode 算法刷题