[LeetCode周赛复盘] 第 326 场周赛20230101

一、本周周赛总结

• 这周白打了o(╥﹏╥)o，-5。
• T1 模拟。
• T2 模拟。
• T3 层先法BFS。
• T4 dfs求路径+树上DP。
  

二、 6333. 查询网格图中每一列的宽度

链接: 6333. 查询网格图中每一列的宽度

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def findColumnWidth(self, grid: List[List[int]]) -> List[int]:m,n = len(grid),len(grid[0])ans = [1]*n for i,row in enumerate(grid):for j,v in enumerate(row):ans[j] = max(ans[j],len(str(v)))return ans 

三、6350. 找出可整除性得分最大的整数

链接: 6350. 找出可整除性得分最大的整数

1. 题目描述

2. 思路分析

• 排序后暴力模拟，和T1一样。
• 这个log可以优化掉，毕竟就是求mx，但懒得写。

3. 代码实现

class Solution:def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:divisors.sort()mx = -1ans = 0for x in divisors:cnt = sum(y%x == 0 for y in nums)if cnt>mx:mx = cnt ans = x return ans 

四、6375. 构造有效字符串的最少插入数

链接: 6375. 构造有效字符串的最少插入数

1. 题目描述

2. 思路分析

这个数据量，其实最好的方式是暴力构造s，判断子序列。

• 假设我们有一个abc无限循环的串s，找最短的前缀，可以包含word作为子序列。
• 那么直接双指针找就可以了。
• 注意外层枚举长的那个串。

3. 代码实现

class Solution:def addMinimum(self, word: str) -> int:n = len(word)i = j = 0while True:c = 'abc'[i%3]if j < n and c == word[j]:j += 1if j == n:breaki += 1d = (i+1+3-1)//3return d * 3  - n

五、 6378. 最小化旅行的价格总和

链接: 6378. 最小化旅行的价格总和

1. 题目描述

2. 思路分析

dfs求路径+树形DP（打家劫舍3）。

• 首先多次旅程实际上是对有的点可以访问多次，点之间是独立的。最后把点价值乘次数加起来即可。
• 那么预处理所有旅程，求每个旅程经过哪些点，次数累计。
  • 求路径直接用dfs回溯即可。
• 接下来用树形dp，如果本节点要折半，那么孩子不能折半；如果本节点不折半，那么孩子折半不折半都可以，取最小值。
  • 注意每个节点累计价值还得*cnt。

3. 代码实现

class Solution:def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:g = [[]for _ in range(n)]for u,v in edges:g[u].append(v)g[v].append(u)            def find(start,end):  # 求start-end的路径上所有点d = []  # 记录路径上的点def dfs(u,fa):d.append(u)if u == end:  # 找到结尾return Truefor v in g[u]:if v == fa:continue if dfs(v,u):return Trued.pop()return Falsedfs(start,-1)return dcnt = Counter()  # 计算每个点被访问的次数for start,end in trips:cnt += Counter(find(start,end))@cachedef dfs(u,fa,half=True):ans = price[u] * cnt[u]  # 这个点对答案的贡献if half:ans = price[u]//2 *cnt[u]  # 是否要除以2                        for v in g[u]:if v == fa:continue if half:  # 如果本点被减半，邻居不能减半ans += dfs(v,u,False)else:ans += min(dfs(v,u,True),dfs(v,u,False))  # 否则邻居都可以return ans# ok = list(cnt.keys())ans = min(dfs(0,-1,True),dfs(0,-1,False))return ans       

六、参考链接