LeetCode笔记：Weekly Contest 240 比赛记录
LeetCode笔记：Weekly Contest 240 比赛记录
0. 赛后总结
连着两周都只做出来两题，我还能说什么呢……
唉，桑心……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
第一题其实就是一个累加列表，分别在每个人的出生和死亡年份加1和减1，然后求个累计和就能够得到每个年份下的人口数，然后求最大值即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
cnt = [0 for _ in range(101)]
for b, d in logs:
cnt[b-1950] += 1
cnt[d-1950] -= 1
for i in range(100):
cnt[i+1] += cnt[i]
_max = max(cnt)
for idx in range(101):
if cnt[idx] == _max:
return idx + 1950提交代码评测得到：耗时40ms，占用内存14.3MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
考虑i， j指针的变化，不难看出，两者都是单向滑动的，当j逐渐增大时，i也是逐渐增大的，当出现第一个不大于nums2[j]时的i的位置，就是对应的j位置下可以取到最大间隔的i的位置。
因此，我们单调维护两个指针的位置即可。整体的算法复杂度为 O ( N ) O(N) O(N)。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
i, j, n, m = 0, 0, len(nums1), len(nums2)
res = 0
while j < m:
while i < n and i <= j and nums1[i] > nums2[j]:
i += 1
if i >= n:
break
if i <= j:
res = max(j-i, res)
j += 1
return res提交代码评测得到：耗时1160ms，占用内存31.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这题比赛的时候完全没有想到正确的思路，想着用堆排或者是有序列表啥的，目的是为了单调地获取下一个可能的窗口位置，结果发现这个思路有问题，怎么样算法复杂度都没法减下来。
结果看了一下别人的解法，发现他们的思路是考察对每一个元素，当这个元素作为区间内的最小元素时，其可以取到的最大的区域范围，而这个区域的边界，可以通过两个单调序列分别进行获取。
这样，整体的算法复杂度就能够控制在 O ( N ) O(N) O(N)了。
2. 代码实现
给出python代码实现如下：
import numpy
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
MOD = 10**9 + 7
n = len(nums)
s = [0 for _ in range(n+1)]
for i in range(n):
s[i+1] = s[i] + nums[i]
stack = []
right = [n-1 for _ in range(n)]
for i in range(n):
while stack != [] and nums[i] < nums[stack[-1]]:
idx = stack.pop()
right[idx] = i-1
stack.append(i)
# print(right)
stack = []
left = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
while stack != [] and nums[i] < nums[stack[-1]]:
idx = stack.pop()
left[idx] = i+1
stack.append(i)
# print(left)
res = max(nums[i]*(s[right[i]+1]-s[left[i]]) for i in range(n))
return res % MOD提交代码评测得到：耗时1616ms，占用内存50.6MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这题比赛的时候没能搞定，赛后倒是给出了一种解法不过超时严重，最后是看的官方解法才想出来的解法。
这题的核心考察点是拓扑结构，核心就一句话：
- 对于有向无环图，前序节点永远出现在后序节点的前方。
因此，我们需要记录下图中每一个点的如下信息：
- 入/出度数；
- 下/上游节点集合；
这里，我们采用倒序的方式，考察出度数目还有上游节点数目，从每一条路径的尾部向上遍历，直到遍历完成。
每访问一个节点，其上游节点的出度都会减1，如果图中存在环结构，那么到某个时间节点，向上游遍历已经完成，但是还有许多节点的出度依然不为0。
而对于某一个具体的节点v，经过这个节点的所有路径中，colors[v]的计数都会加上一，而考虑其上游节点u，经过节点u的所有路径的某个颜色的节点数目就会变成max(cnt[u][c], cnt[v][c])，前者是不经过节点v时的路径中颜色c的最大数目，后者为经过了节点v时的路径中颜色c的最大数目。
综上，我们即可给出完整的代码。
2. 代码实现
给出完整的python代码如下：
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
deg = [0 for _ in range(n)]
graph = defaultdict(list)
for u, v in edges:
deg[u] += 1
graph[v].append(u)
endpoints = [u for u in range(n) if deg[u] == 0]
cnt = [[0 for _ in range(26)] for _ in range(n)]
while endpoints:
v = endpoints.pop(0)
color = ord(colors[v]) - ord('a')
cnt[v][color] += 1
for u in graph[v]:
deg[u] -= 1
for i in range(26):
cnt[u][i] = max(cnt[u][i], cnt[v][i])
if deg[u] == 0:
endpoints.append(u)
if any(v != 0 for v in deg):
return -1
return max(max(c) for c in cnt)提交代码评测得到：耗时3092ms，占用内存88.1MB。