公司网站建设比较好的公司,常用的seo工具推荐,58同城深圳招聘网站,本地网站怎么做[LeetCode周赛复盘] 第 99 场双周赛20230304 一、本周周赛总结二、 [Easy] 2578. 最小和分割1. 题目描述2. 思路分析3. 代码实现三、[Medium] 2579. 统计染色格子数1. 题目描述2. 思路分析3. 代码实现四、[Medium] 2580. 统计将重叠区间合并成组的方案数1. 题目描述2. 思路分析…
[LeetCode周赛复盘] 第 99 场双周赛20230304 一、本周周赛总结二、 [Easy] 2578. 最小和分割1. 题目描述2. 思路分析3. 代码实现三、[Medium] 2579. 统计染色格子数1. 题目描述2. 思路分析3. 代码实现四、[Medium] 2580. 统计将重叠区间合并成组的方案数1. 题目描述2. 思路分析3. 代码实现五、[Hard] 2581. 统计可能的树根数目1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
T1 贪心。T2 数学/dp。T3 线段合并/快速幂取模。T4 换根DP。
二、 [Easy] 2578. 最小和分割
链接: 2578. 最小和分割
1. 题目描述 2. 思路分析
这题如果不写暴力枚举的话是个贪心想了好一会。排序后奇偶交错分配即可。枚举的话状压枚举可能写的更快一些。
3. 代码实现
class Solution:def splitNum(self, num: int) - int: s []for c in str(num):if c ! 0:s.append(c)s sorted(s)n len(s)h n // 2a []b []for i,c in enumerate(s):if i 1:b.append(c)else:a.append(c)x int(0.join(a))y int(0.join(b))return x y 三、[Medium] 2579. 统计染色格子数
链接: 2579. 统计染色格子数
1. 题目描述 2. 思路分析
数学能力已经退化比赛时肯定不优先推公式。
找规律dp。发现每次增加i*4个。
3. 代码实现
f [1]*(10**51)
x [1]*(10**51)
for i in range(2,10**51):x[i] (i-1)*4f[i] f[i-1] x[i]
class Solution:def coloredCells(self, n: int) - int:return f[n] 四、[Medium] 2580. 统计将重叠区间合并成组的方案数
链接: 2580. 统计将重叠区间合并成组的方案数
1. 题目描述 2. 思路分析
分析题意发现有交集的区间一定在一起那么划分完会变成x个集合这x个集合分别可以在左边或右边就互不影响了。因此答案就是2**x。
3. 代码实现
MOD 10 ** 9 7
class Solution:def countWays(self, ranges: List[List[int]]) - int:cnt 1ranges.sort()print(ranges)p ranges[0][1]for x,y in ranges:if x p:p max(p,y)else:cnt 1p yreturn pow(2,cnt,MOD)五、[Hard] 2581. 统计可能的树根数目
链接: 2581. 统计可能的树根数目
1. 题目描述 2. 思路分析
知道是换根DP之前学了max版的换根dp这次遇到加法的就不会了。学了一下。当然用模板也能做。
3. 代码实现
class Solution:def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) - int:n len(edges) 1g [[] for _ in range(n)]for u,v in edges:g[u].append(v)g[v].append(u)s set(tuple(x) for x in guesses)f [0]*ndef dfs(u,fa):for v in g[u]:if v ! fa:if (u,v) in s:f[0] 1dfs(v,u)def reroot(u,fa):for v in g[u]:if v ! fa:f[v] f[u] int((v,u) in s) - int((u,v) in s)reroot(v,u)dfs(0,-1)reroot(0,-1)return sum(x k for x in f) 六、参考链接
