LeetCode笔记：Weekly Contest 359

• LeetCode笔记：Weekly Contest 359
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-359

1. 题目一

给出题目一的试题链接如下：

• 2828. Check if a String Is an Acronym of Words

1. 解题思路

这一题倒是没啥好多说的，把题意翻译成代码语言即可。

2. 代码实现

给出python代码实现如下：

class Solution:def isAcronym(self, words: List[str], s: str) -> bool:if len(words) != len(s):return Falsereturn 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, 0res = 0while cnt < n:if i not in block:res += iblock.add(k-i)cnt += 1i += 1return 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 0res = dp(idx+1)for ed, gold in locs[idx]:res = max(res, gold + dp(ed+1))return resreturn 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 += 1s, 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 += 1return max(cnt.keys())

提交代码评测得到：耗时1647ms，占用内存39.2MB。