-
LeetCode笔记:Weekly Contest 354
-
1. 题目一
- 1. 解题思路
- 2. 代码实现
-
2. 题目二
- 1. 解题思路
- 2. 代码实现
-
3. 题目三
- 1. 解题思路
- 2. 代码实现
-
4. 题目四
- 1. 解题思路
- 2. 代码实现
-
1. 题目一
- 比赛链接:https://leetcode.com/contest/weekly-contest-354/
1. 题目一
给出题目一的试题链接如下:
- 2778. Sum of Squares of Special Elements
1. 解题思路
这一题思路很直接,就是找到对应的几个能够被n整除的位置然后将对应元素的平方相加即可。
2. 代码实现
给出python代码实现如下:文章来源:https://www.toymoban.com/news/detail-571043.html
class Solution:
def sumOfSquares(self, nums: List[int]) -> int:
res = 0
n = len(nums)
for i in range(1, n+1):
if n % i == 0:
res += nums[i-1] * nums[i-1]
return res
提交代码评测得到:耗时85ms,占用内存16.4MB。
2. 题目二
给出题目二的试题链接如下:
- 2779. Maximum Beauty of an Array After Applying Operation
1. 解题思路
这一题由于不要求连续,因此就和顺序无关,我们只需要先对所有元素进行排序,然后遍历一下滑动窗口,使得左右距离不超过 2 k 2k 2k即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
i, j, n = 0, 0, len(nums)
res = 0
while j < n:
while nums[j] - nums[i] > 2 * k:
i += 1
res = max(res, j-i+1)
j += 1
return res
提交代码评测得到:耗时1210ms,占用内存30.4MB。
3. 题目三
给出题目三的试题链接如下:
- 2780. Minimum Index of a Valid Split
1. 解题思路
这一题思路上也非常直接,就是先找出dominate的元素以及其对应的个数,然后遍历一下分隔点,找出最早能够符合条件的切分位置即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def minimumIndex(self, nums: List[int]) -> int:
n = len(nums)
def find_dominate(nums):
cnt = Counter(nums)
res = [x for x in cnt if cnt[x] * 2 > n]
dominate = res[0]
return dominate, cnt[dominate]
domi, dcnt = find_dominate(nums)
cnt = defaultdict(int)
for i, x in enumerate(nums):
cnt[x] += 1
if cnt[domi] * 2 > i+1 and (dcnt - cnt[domi]) * 2 > n-i-1:
return i
return -1
提交代码评测得到:耗时748ms,占用内存32MB。
4. 题目四
给出题目四的试题链接如下:
- 2781. Length of the Longest Valid Substring
1. 解题思路
这次的最后一题是一个字典树(trie树)的变体。
我们首先用forbidden数组构造一个字典树,然后从后往前考虑每一个点作为终点时可以取到的最长的subarray,此时我们只需要不断地滑动遍历开始的位置,直到存在某一个位置使得这个subarray以某个forbidden当中的词作为开头。此时,我们更新终止节点为这个词的倒数第二个字符位置即可。
而关于字典树的相关内容,我在之前一个博客【经典算法:Trie树结构简介】已经有过介绍了,这里就不进行展开了。
2. 代码实现
给出python代码实现如下:
class Trie:
def __init__(self):
self.trie = {}
def add_word(self, word):
trie = self.trie
for c in word:
trie = trie.setdefault(c, {})
trie["eos"] = word
return
def find(self, s):
trie = self.trie
for ch in s:
if ch not in trie:
return ""
trie = trie[ch]
if "eos" in trie:
return trie["eos"]
return ""
class Solution:
def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
trie = Trie()
for w in forbidden:
trie.add_word(w)
s = ""
res = 0
for ch in word[::-1]:
s = ch + s
w = trie.find(s)
if w != "":
s = w[:-1]
res = max(res, len(s))
return res
提交代码评测得到:耗时2358ms,占用内存194.3MB。文章来源地址https://www.toymoban.com/news/detail-571043.html
到了这里,关于LeetCode笔记:Weekly Contest 354的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!