LeetCode笔记：Biweekly Contest 64
LeetCode笔记：Biweekly Contest 64
codename_cys
发布于 2021-11-02 16:50:30
发布于 2021-11-02 16:50:30
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题我们的思路是非常的简单粗暴的，即简单地先做一个数量统计，然后找出只出现过一次的item，最后返回第k个。
2. 代码实现
给出python代码实现如下：
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
cnt = Counter(arr)
distinct = [s for s in cnt if cnt[s] == 1]
return distinct[k-1] if len(distinct) >= k else ""提交代码评测得到：耗时74ms，占用内存14.7MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题我们借助了滑动窗口的思路。
我们首先按照时间对events进行排序，我们考察每一个event作为靠后的event的情况下可用的前序的event，显然只要ed小于当前event的st时间即可全部用于第一个event，但是这部分event当中，我们又只需要保留一个val最大的event即可。
综上，我们即可借助滑动窗口的思路对其进行实现。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
events = sorted(events, key=lambda x: (x[1], x[0], -x[2]))
res = max(x[2] for x in events)
i, j, n = 0, 0, len(events)
while j < n:
while i < j and events[i][1] < events[j][0]:
if i > 0 and events[i][2] <= events[i-1][2]:
events[i] = events[i-1]
res = max(res, events[i][2] + events[j][2])
i += 1
if i > 0:
i -= 1
j += 1
return res提交代码评测得到：耗时2006ms，占用内存55.8MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我们的思路是首先找到所有的candle的位置，然后统计每一个candle位置之前的所有的plate数目，然后，我们只要对每一个query的区间，找到这个区间起点后方的第一个candle以及终点前的最后一个candle，计算两者之间的plate数目差值即可得到最终的结果。
2. 代码实现
给出python代码实现如下：
class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
gaps = []
cnt = 0
for i, ch in enumerate(s):
if ch == "*":
cnt += 1
elif ch == "|":
gaps.append((i, cnt))
m = len(gaps)
res = []
for bg, ed in queries:
i = bisect.bisect_left(gaps, (bg, 0))
j = bisect.bisect_left(gaps, (ed, 0))
if j >= m or gaps[j][0] > ed:
j -= 1
res.append(max(gaps[j][1] - gaps[i][1], 0))
return res提交代码评测得到：耗时2180ms，占用内存53.9MB。
4. 题目四
给出题目四的试题链接如下：
这一题没啥好的思路，先放弃了，后面有机会再看看吧。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-10-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录