LeetCode笔记：Weekly Contest 341
- LeetCode笔记：Weekly Contest 341
- 比赛链接：https://leetcode.com/contest/weekly-contest-341/
1. 题目一
给出题目一的试题链接如下：
- 2643. Row With Maximum Ones
1. 解题思路
这一题挺直接的，就是按照题意翻译一下，对每一行都计算一下其中1元素的个数，然后找出最大的一行的位置以及其中1元素的个数进行返回即可。
2. 代码实现
给出python代码实现如下：
class Solution:def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:res, cnt = -1, -1for i, line in enumerate(mat):s = sum(line)if s > cnt:cnt = sres = ireturn (res, cnt)
提交代码评测得到：耗时1070ms，占用内存14.3MB。
2. 题目二
给出题目二的试题链接如下：
- 2644. Find the Maximum Divisibility Score
1. 解题思路
这一题也没想到啥好的思路，就是按照题目翻译了一下，用了一个二重循环硬解了一下。
2. 代码实现
给出python代码实现如下：
class Solution:def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:divisors = sorted(divisors)status = [0 for _ in divisors]n = len(divisors)res, cnt = math.inf, -1for i, d in enumerate(divisors):if status[i] == 1:continuefor j in range(i, n):if divisors[j] % d == 0:status[j] = 1s = len([x for x in nums if x % d == 0])if s > cnt:cnt = sres = dreturn res
提交代码评测得到：耗时6982ms，占用内存14.2MB。
3. 题目三
给出题目三的试题链接如下：
- 2645. Minimum Additions to Make Valid String
1. 解题思路
这一题由于只能添加元素，因此我们只需要依序分类讨论一下即可。
2. 代码实现
给出python代码实现如下：
class Solution:def addMinimum(self, word: str) -> int:a, b = 0, 0res = 0for ch in word:if ch == "a":if a == 1 and b == 0:res += 2elif a == 1 and b == 1:res += 1a, b = 1, 0elif ch == "b":if a == 0 and b == 0:res += 1elif a == 1 and b == 1:res += 2a, b = 1, 1else:if a == 0 and b == 0:res += 2elif a == 1 and b == 0:res += 1a, b = 0, 0if a == 1 and b == 1:res += 1elif a == 1 and b == 0:res += 2return res
提交代码评测得到：耗时46ms，占用内存13.8MB。
4. 题目四
给出题目四的试题链接如下：
- 2646. Minimize the Total Price of the Trips
1. 解题思路
这一题思路还是挺简单的，就是先看一下每一条路线要经过哪些点，然后就能得到所有的点被经过的次数，乘以原本的price之后我们就能获得所有点所需的成本。
然后就是一个dfs来考察不同情况下各个点如果被除二会带来的影响。
不过问题就在于时间复杂度，还是需要经过一些剪枝才能够通过测试样例，就比较无聊……
2. 代码实现
给出python代码实现如下：
class Solution:def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:graph = defaultdict(set)for u, v in edges:graph[u].add(v)graph[v].add(u)cnt = defaultdict(int)def trip(u, v):nonlocal graph, cntif u == v:cnt[u] += 1return [u]q = [(u, [u])]while q:u, path = q.pop(0)for w in graph[u]:if len(path) >= 2 and path[-2] == w:continueif w == v:for w in path:cnt[w] += 1cnt[v] += 1return path + [v]q.append((w, path + [w]))return for u, v in trips:path = trip(u, v)s = [(p*cnt[u], u) for u, p in enumerate(price) if cnt[u] != 0]s = sorted(s, reverse=True)t = [x[0]//2 for x in s]m = len(s)for i in range(m-1):t[m-1-i-1] += t[m-1-i] res = math.infdef dfs(idx, prev, banned):nonlocal resif idx >= m:if prev < res:res = prevreturnif prev + t[idx] >= res:returnscore, u = s[idx]if u not in banned:new_banned = banned | graph[u]dfs(idx+1, score//2 + prev, new_banned)dfs(idx+1, score+prev, banned)returndfs(0, 0, set())return res
提交代码评测得到：耗时807ms，占用内存14.5MB。
3. 算法优化
看了一下当前最快的解法，耗时237ms，几乎是我们的1/4。
它的思路和我们看起来是一样的，不过实现上更加优雅，这里就简单摘录大佬的code如下，有兴趣的读者可以自行研究一下。
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)coef = [0] * nfor s, e in trips:path = []def dfs(v: int, p: int) -> bool:path.append(v)if v == e:return Truefor u in g[v]:if u != p:if dfs(u, v):return Truepath.pop()return Falsedfs(s, s)for v in path:coef[v] += 1def dfs(v: int, p: int) -> tuple[int, int]:wov = coef[v] * price[v]wv = wov // 2for u in g[v]:if u != p:wu, wou = dfs(u, v)wov += min(wu, wou)wv += woureturn wv, wovreturn min(dfs(0, 0))