加快建设企业门户网站建,长沙百度提升排名,做网站需要域名,网站建设二级页面方案LeetCode笔记#xff1a;Biweekly Contest 99 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接#xff1a;https://leetcode.com/contest/biweekly-contest-99
1. 题目一…LeetCode笔记Biweekly Contest 99 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接https://leetcode.com/contest/biweekly-contest-99
1. 题目一
给出题目一的试题链接如下
2578. Split With Minimum Sum
1. 解题思路
这一题题目简直有毒题目强调了数字不会以0开头但是没想到分开的数字却可以以0为开头因此这道题事实上是被大幅简化了的我们只要把每一位数排序然后交错分成两个数字相加即可。
2. 代码实现
给出python代码实现如下
class Solution:def splitNum(self, num: int) - int:s str(num)s sorted([int(ch) for ch in s])n1, n2 0, 0for i, ch in enumerate(s):if i % 2 0:n1 n1 * 10 chelse:n2 n2 * 10 chreturn n1 n2提交代码评测得到耗时32ms占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下
2579. Count Total Number of Colored Cells
1. 解题思路
这一题其实也简单就是一个等差数列求和一道数学题罢了答案为
ans∑i1n(2i−1)∑i1n−1(2i−1)n2(n−1)2\begin{aligned} ans \sum\limits_{i1}^{n}(2i-1) \sum\limits_{i1}^{n-1}(2i-1) \\ n^2 (n-1)^2 \end{aligned} ansi1∑n(2i−1)i1∑n−1(2i−1)n2(n−1)2
2. 代码实现
给出python代码实现如下
class Solution:def coloredCells(self, n: int) - int:return n * n (n-1) * (n-1)提交代码评测得到耗时31ms占用内存13.7MB。
3. 题目三
给出题目三的试题链接如下
2580. Count Ways to Group Overlapping Ranges
1. 解题思路
这一题我们只需要将range进行一下排列就能够快速地得到所有的有overlapping的区间然后我们将这些区间分块就能够得到所有不含有overlapping的区间块总数nnn而我们的答案就是2n2^n2n。
2. 代码实现
给出python代码实现如下
class Solution:def countWays(self, ranges: List[List[int]]) - int:MOD 10**9 7groups 0ranges sorted(ranges)rb -1for a, b in ranges:if a rb:groups 1rb belse:rb max(rb, b)res 1for _ in range(groups):res res * 2 % MODreturn res提交代码评测得到耗时897ms占用内存53.1MB。
4. 题目四
给出题目四的试题链接如下
2581. Count Number of Possible Root Nodes
1. 解题思路
这一题感觉是这周的8道题里面最难的一题了一开始我也没啥思路中午的时候临机一动想到了答案还是蛮开心的。
这一题本质上就是遍历一下每一个点作为根节点时Bob提出的guess当中正确的猜测的个数统计其中能够大于k的情况。
单独对于某一个点作为根节点的情况下考察正确猜测的个数这件事其实是很简单的只需要用一个遍历即可实现但是要遍历所有的点作为根节点的情况这个对于计算效率的要求就比较高了肯定不都能用for循环对一个节点都单独计算。
我最开始的思路是想要通过动态规划来完成不过想了好久也没有想到好的解法后来转念一想是否可以通过之前已经计算过的结果快速得到其他节点作为根节点时猜测正确的guess个数呢
这个其实是可以的假设我们已知u作为根节点时的猜测正确的guess个数n且v是u的一个邻接节点那么以v作为根节点时其与u作为根节点时的边的关系仅仅只是将(u,v)换成了(v,u)因此我们就可以快速地得到以v作为根节点时猜测正确的guess个数。
我们同样使用一个遍历即可得到全部的答案了。
2. 代码实现
给出python代码实现如下
class Solution:def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) - int:n len(edges) 1graph defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)guesses {(u,v) for u, v in guesses}cnt 0q [0]seen set()while q ! []:u q.pop(0)seen.add(u)for v in graph[u]:if v in seen:continueif (u, v) in guesses:cnt 1q.append(v)seen set()res 0def dfs(u, cnt):nonlocal seen, resif u in seen:return if cnt k:res 1seen.add(u)for v in graph[u]:if (u, v) in guesses:if (v, u) in guesses:dfs(v, cnt)else:dfs(v, cnt-1)else:if (v, u) in guesses:dfs(v, cnt1)else:dfs(v, cnt)returndfs(0, cnt)return res提交代码评测得到耗时2205ms占用内存194.1MB。
