LeetCode笔记：Weekly Contest 289
LeetCode笔记：Weekly Contest 289
codename_cys
发布于 2022-05-07 10:39:53
发布于 2022-05-07 10:39:53
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题思路上也是比较简单的，就是一个迭代就完事了。
2. 代码实现
给出python代码实现如下：
class Solution:
def digitSum(self, s: str, k: int) -> str:
n = len(s)
if n <= k:
return s
i = 0
res = ""
while i < n:
sub = s[i:i+k]
sub = sum(int(ch) for ch in sub)
res += str(sub)
i += k
return self.digitSum(res, k)提交代码评测得到：耗时34ms，占用内存14MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题思路也简单，首先就是统计一下各个难度的频次，显然如果有难度的频次为1，那么它永远无法被完成，返回-1就行了。
而对于剩下的可能频次，我们对3求余上取整就是所需的最少次数。
因此，我们就可以快速得到最终的结果了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumRounds(self, tasks: List[int]) -> int:
cnt = Counter(tasks)
res = 0
for x in cnt.values():
if x == 1:
return -1
res += math.ceil(x / 3)
return res提交代码评测得到：耗时1035ms，占用内存28.4MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我们的思路就是针对所有的拐点可能性进行一下统计，而对于每一个拐点，我们只需要考察一下4种可能的拐向分布即可。
而对于具体每一种图像的结果计算，我们通过两个二维的累积矩阵进行加速计算即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxTrailingZeros(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
twos = [[0 for _ in range(m+1)] for _ in range(n+1)]
fives = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
for j in range(m):
x = grid[i][j]
cnt2, cnt5 = 0, 0
while x % 2 == 0:
x = x // 2
cnt2 += 1
while x % 5 == 0:
x = x // 5
cnt5 += 1
twos[i+1][j+1] = twos[i+1][j] + twos[i][j+1] - twos[i][j] + cnt2
fives[i+1][j+1] = fives[i+1][j] + fives[i][j+1] - fives[i][j] + cnt5
def get_horionzal(matrix, row, i, j):
if i > j:
return 0
return matrix[row+1][j+1] - matrix[row+1][i] - (matrix[row][j+1] - matrix[row][i])
def get_vertical(matrix, col, i, j):
if i > j:
return 0
return matrix[j+1][col+1] - matrix[i][col+1] - (matrix[j+1][col] - matrix[i][col])
res = 0
for i in range(n):
for j in range(m):
s1 = min(get_vertical(twos, j, 0, i-1) + get_horionzal(twos, i, 0, j), get_vertical(fives, j, 0, i-1) + get_horionzal(fives, i, 0, j))
s2 = min(get_vertical(twos, j, i+1, n-1) + get_horionzal(twos, i, 0, j), get_vertical(fives, j, i+1, n-1) + get_horionzal(fives, i, 0, j))
s3 = min(get_vertical(twos, j, 0, i-1) + get_horionzal(twos, i, j, m-1), get_vertical(fives, j, 0, i-1) + get_horionzal(fives, i, j, m-1))
s4 = min(get_vertical(twos, j, i+1, n-1) + get_horionzal(twos, i, j, m-1), get_vertical(fives, j, i+1, n-1) + get_horionzal(fives, i, j, m-1))
res = max(res, s1, s2, s3, s4)
return res提交代码评测得到：耗时8274ms，占用内存57.6MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题坦率来说不太明白为啥被放到了最后一题，因为就是一个树当中最大路径的求取问题的一个变种。
这里感觉就不需要多做展开了，直接给出代码实现即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
n = len(parent)
childrens = defaultdict(list)
for i in range(1, n):
childrens[parent[i]].append(i)
res = 1
def dfs(u):
nonlocal res
paths = []
for v in childrens[u]:
l = dfs(v)
if s[u] != s[v]:
paths.append(l)
paths = sorted(paths, reverse=True)
if len(paths) == 0:
return 1
elif len(paths) == 1:
res = max(res, paths[0]+1)
else:
res = max(res, paths[0]+1+paths[1])
return 1 + paths[0] if paths != [] else 1
dfs(0)
return res提交代码评测得到：耗时1987ms，占用内存156.5MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
