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

2022-08-15
2

一、本周周赛总结

  • 几乎全是模拟题,除了第二题是一道同向双指针。
  • 第二次打力扣周赛就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)]

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

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

1. 题目描述

在这里插入图片描述

2. 思路分析

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

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

四、[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))

五、[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                                                                      

相关信息

    评论