LeetCode笔记：Biweekly Contest 82
LeetCode笔记：Biweekly Contest 82
codename_cys
发布于 2022-07-11 18:17:35
发布于 2022-07-11 18:17:35
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题本质上就是一个二叉树的后序遍历而已，倒是没啥难度，套路化的求一下就行了。
2. 代码实现
给出python代码实现如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def evaluateTree(self, root: Optional[TreeNode]) -> bool:
if root.val == 0:
return False
elif root.val == 1:
return True
elif root.val == 2:
return self.evaluateTree(root.left) or self.evaluateTree(root.right)
else:
return self.evaluateTree(root.left) and self.evaluateTree(root.right)提交代码评测得到：耗时77ms，占用内存14.6MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题稍微复杂一点，我的思路来说的话就是首先找到每一辆车上上去的人到达的时间，然后倒着找回去，找到第一个能够坐上去且不会和别人重复的时间点就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
m, n = len(buses), len(passengers)
buses = sorted(buses)
passengers = sorted(passengers)
record = [[] for _ in buses]
idx = 0
for i, t in enumerate(buses):
while len(record[i]) < capacity and idx < n and passengers[idx] <= t:
record[i].append(passengers[idx])
idx += 1
if len(record[i]) < capacity:
record[i].append(t+1)
passengers = set(passengers)
for i in range(m-1, -1, -1):
for t in record[i][::-1]:
if t-1 not in passengers:
return t-1
return -1提交代码评测得到：耗时1541ms，占用内存45.5MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题由于每一次操作可以加一也可以减一，所以事实上操作在那个数组没有太大的区别，因此我们只要整合起来考察差值，然后将其尽量平均减小即可。
唯一比较繁琐的就是找到这个临界值以及关于这个临界值附近的边界条件。
2. 代码实现
给出python代码实现如下：
class Solution:
def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
delta = sorted([abs(x-y) for x, y in zip(nums1, nums2)], reverse=True)
n = len(delta)
k = k1 + k2
if sum(delta) <= k:
return 0
tot = 0
for i in range(n):
tot += delta[i]
flag = delta[i+1] if i < n-1 else 0
if tot - (i+1) * flag >= k:
avg = math.ceil((tot - k) / (i+1))
for j in range(i+1):
k -= delta[j] - avg
res = avg*avg*(i+1 - k) + (avg-1)**2 * k
# print(avg, i, k, res)
for j in range(i+1, n):
res += delta[j] * delta[j]
return res
return -1提交代码评测得到：耗时2509ms，占用内存31.9MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题其实我其实参考了其他大佬们的解答。
思路上来说，就是不断地找寻以某一个数位最小值时其附近所能够扩展得到的最长的子串长度，然后看这个子串能否满足条件。
如果可以，我们返回这个子串的长度即可。
至于如何实现找到以某个元素为最小值时其附近所能构成的最长子串，我们可以使用DSU进行实现，具体关于DSU的内容网上很多文章都有介绍，我自己也写过一篇关于DSU的博客【经典算法：并查集（DSU）结构简介】。
2. 代码实现
给出python代码实现如下：
class DSU:
def __init__(self, N):
self.root = [i for i in range(N)]
self.size = [1 for _ in range(N)]
def find(self, k):
if self.root[k] == k:
return k
self.root[k] = self.find(self.root[k])
return self.root[k]
def union(self, a, b):
x = self.find(a)
y = self.find(b)
if x != y:
self.root[y] = x
self.size[x] += self.size[y]
return
def get_size(self, x):
x = self.find(x)
return self.size[x]
class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
n = len(nums)
dsu = DSU(n)
record = defaultdict(list)
for i, x in enumerate(nums):
record[x].append(i)
keys = sorted(record.keys(), reverse=True)
for k in keys:
for idx in record[k]:
if idx+1 < n and nums[idx+1] >= nums[idx]:
dsu.union(idx, idx+1)
if idx-1 >= 0 and nums[idx-1] >= nums[idx]:
dsu.union(idx, idx-1)
if k > threshold / dsu.get_size(idx):
return dsu.get_size(idx)
return -1提交代码评测得到：耗时4663ms，占用内存32.8MB。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录