LeetCode笔记：Biweekly Contest 90
LeetCode笔记：Biweekly Contest 90
codename_cys
发布于 2022-11-12 14:09:50
发布于 2022-11-12 14:09:50
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的题目难度感觉全在读题上面，看懂了题目基本就是按照题意翻译一下就行。
找到每一个单词的pattern，然后将唯一一个pattern不同string挑选出来返回即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def oddString(self, words: List[str]) -> str:
def fn(word):
res = []
n = len(word)
for i in range(n-1):
res.append(ord(word[i+1]) - ord(word[i]))
return tuple(res)
cnt = defaultdict(int)
for w in words:
cnt[fn(w)] += 1
for w in words:
if cnt[fn(w)] == 1:
return w提交代码评测得到：耗时76ms，占用内存13.9MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题由于题目设置的题目限制比较低，因此我们直接使用了比较暴力的实现方法，即一个二次循环然后注意判断两两单词之间的相似度，看是否符合变换条件。
2. 代码实现
给出python代码实现如下：
class Solution:
def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
def match(w1, w2):
cnt = 0
for ch1, ch2 in zip(w1, w2):
if ch1 != ch2:
cnt += 1
if cnt > 2:
return False
return True
res = []
for query in queries:
for word in dictionary:
if match(query, word):
res.append(query)
break
return res提交代码评测得到：耗时61ms，占用内存14.1MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题考察的其实就是同余，所有对于space余数相同的数都可以被一次性detroy，因此，我们只需要考察space的余数当中个数最多的余数，然后找到原序列中第一个余数为该值的数返回即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def destroyTargets(self, nums: List[int], space: int) -> int:
cnt = defaultdict(int)
for x in nums:
cnt[x % space] += 1
_max = max(cnt.values())
res = math.inf
for x in nums:
if cnt[x % space] == _max:
res = min(res, x)
return res提交代码评测得到：耗时1270ms，占用内存33.8MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题我的实现思路是倒序加入，我们将原数据从大到小排序，然后依次将其idx加到一个新的数组当中，此时，对于某一时刻的任意一个数，新的index数组当中只存在比这个数更大的元素，因此，我们只要通过二分插入，然后看看其后方是否存在两个或两个以上的元素即可，如果有，反而第二个值即可。
需要注意的是，如果有一些值大小相同，那么我们需要将其按照原顺序加入，这样才能保证每一个数在加入时后方所有的数字均大于这个数。
2. 代码实现
给出python代码实现如下：
class Solution:
def secondGreaterElement(self, nums: List[int]) -> List[int]:
s = [(x, -i) for i, x in enumerate(nums)]
s = sorted(s, reverse=True)
cnums = []
res = [-1 for _ in nums]
for x, i in s:
i = -i
idx = bisect.bisect_left(cnums, i)
if idx + 1 < len(cnums):
res[i] = nums[cnums[idx+1]]
bisect.insort(cnums, i)
return res提交代码评测得到：耗时3485ms，占用内存34.9MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录