-
LeetCode笔记:Weekly Contest 359
-
1. 题目一
- 1. 解题思路
- 2. 代码实现
-
2. 题目二
- 1. 解题思路
- 2. 代码实现
-
3. 题目三
- 1. 解题思路
- 2. 代码实现
-
4. 题目四
- 1. 解题思路
- 2. 代码实现
-
1. 题目一
- 比赛链接:https://leetcode.com/contest/weekly-contest-359
1. 题目一
给出题目一的试题链接如下:
- 2828. Check if a String Is an Acronym of Words
1. 解题思路
这一题倒是没啥好多说的,把题意翻译成代码语言即可。
2. 代码实现
给出python代码实现如下:文章来源:https://www.toymoban.com/news/detail-664742.html
class Solution:
def isAcronym(self, words: List[str], s: str) -> bool:
if len(words) != len(s):
return False
return all(word[0] == ch for word, ch in zip(words, s))
提交代码评测得到:耗时62ms,占用内存16.3MB。
2. 题目二
给出题目二的试题链接如下:
- 2829. Determine the Minimum Sum of a k-avoiding Array
1. 解题思路
这一题我的做法多少也有点暴力,就是从1开始枚举,每增加一个元素的同时block掉它的成对元素,然后直到取满n个元素即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def minimumSum(self, n: int, k: int) -> int:
block = set()
i, cnt = 1, 0
res = 0
while cnt < n:
if i not in block:
res += i
block.add(k-i)
cnt += 1
i += 1
return res
提交代码评测得到:耗时49ms,占用内存16.4MB。
3. 题目三
给出题目三的试题链接如下:
- 2830. Maximize the Profit as the Salesman
1. 解题思路
这一题说来惭愧,没有一下子搞出来,一开始的思路跑偏了,想了分段树和greedy的方式,但是怎么也想不到可行的解法,然后看了一下其他大佬们的思路,发现就是一个简单的动态规划的算法,没能自力做出来真的是委实有些丢脸……
2. 代码实现
给出python代码实现如下:
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
locs = defaultdict(list)
for st, ed, gold in offers:
locs[st].append([ed, gold])
@lru_cache(None)
def dp(idx):
if idx >= n:
return 0
res = dp(idx+1)
for ed, gold in locs[idx]:
res = max(res, gold + dp(ed+1))
return res
return dp(0)
提交代码评测得到:耗时1732ms,占用内存191MB。
4. 题目四
给出题目四的试题链接如下:
- 2831. Find the Longest Equal Subarray
1. 解题思路
这一题我的思路上就是首先记录下每一个元素出现的位置,然后考察以每一个元素作为Equal Subarray的核心元素的话,在至多删除k个字符的情况下可以组成的最大长度并记录下来,最后,我们返回这些最大长度的最大值即可。
而考察对于任意给定的字符在至多删除k个字符的情况下可以组成的最大长度的过程,我们用一个滑动窗口即可进行实现。
2. 代码实现
给出python代码实现如下:
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
locs = defaultdict(list)
for i, x in enumerate(nums):
locs[x].append(i)
cnt = {}
for vals in locs.values():
i, j, n = 0, 0, len(vals)
while j < n:
while vals[j]-vals[i] - (j-i) > k:
i += 1
s, d = j-i+1, vals[j]-vals[i] - (j-i)
cnt[s] = min(cnt[s], vals[j]-vals[i] - (j-i)) if s in cnt else vals[j]-vals[i] - (j-i)
j += 1
return max(cnt.keys())
提交代码评测得到:耗时1647ms,占用内存39.2MB。文章来源地址https://www.toymoban.com/news/detail-664742.html
到了这里,关于LeetCode笔记:Weekly Contest 359的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!