LeetCode笔记：Biweekly Contest 73
LeetCode笔记：Biweekly Contest 73
codename_cys
发布于 2022-04-13 16:26:13
发布于 2022-04-13 16:26:13
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题还是很简单的，就是按照题目意思遍历计数一下就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def mostFrequent(self, nums: List[int], key: int) -> int:
cnt = defaultdict(int)
n = len(nums)
for i in range(n-1):
if nums[i] == key:
cnt[nums[i+1]] += 1
res = sorted(cnt.items(), key=lambda x: -x[1])
return res[0][0]提交代码评测得到：耗时107ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题其实就是一个排序问题，自己实现其实也可以，不过直接调用语言中自带的排序算法会更快一点。
我们要做的就是根据题意给出大小判断函数而已，这个其实就是按照题意翻译一下就行，也不是很复杂。
2. 代码实现
给出python代码实现如下：
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def fn(num):
if num < 10:
return mapping[num]
else:
return 10 * fn(num // 10) + fn(num % 10)
res = sorted([(fn(x), i, x) for i, x in enumerate(nums)])
return [x[-1] for x in res]提交代码评测得到：耗时1752ms，占用内存22.6MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实就是一个拓扑连接图的问题，我们只需要从每一个节点依次遍历其所有的子节点以及子节点的子孙，然后给他们的父节点记录当中记录下其本身即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
graph = defaultdict(list)
for u,v in edges:
graph[u].append(v)
res = [[] for _ in range(n)]
def dfs(u):
nonlocal res
seen = set(graph[u])
s = deepcopy(graph[u])
while s:
v = s.pop(0)
res[v].append(u)
for w in graph[v]:
if w not in seen:
s.append(w)
seen.add(w)
return
for u in range(n):
dfs(u)
return res提交代码评测得到：耗时1485ms，占用内存31.4MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题做的时候我用的是贪心算法，成功地得到了结果并且通过了所有的测试样例，不过后来仔细想的时候发现，我只能证明这是一个可行的构造方法，但是却很难说明其最小的性质，就有点尴尬……
这里就姑且介绍一下我给出的贪心算法吧，至于最小性的证明，如果大家有能够想明白的还请务必在评论区里面告知一二，不胜感激。
关于这里的临位交换过程，易知对于任意一个元素进行任意次移动，都不会改变其他所有元素的相对位置。
因此，我们很快可以给出一种贪心移动方式如下：
- 每次考察最后一个字符（第一个字符也一样，只需将后续所有的操作反向即可），然后从头开始找到第一个与之相同的字符：
- 如果这个字符不是它本身，那么将其移动到第一个字符的位置就能够成回文，移动距离就是其位置下标，然后只需要考察剩余的中间字符串即可；
- 如果这个字符是他本身，那么这个字符最后一定会移动到中心位置，此时我们先不考虑这个字符，只需要将除这个字符以外的全部文本先处理成回文字符串，然后把这个字符移动到其中心即可，其移动距离为剩余字符长度的1/2；
由此，我们就可以获得一个贪婪算法的回文构造方式。
2. 代码实现
给出python代码实现如下：
class Solution:
def minMovesToMakePalindrome(self, s: str) -> int:
n = len(s)
s = list(s)
res = 0
while n >= 2:
idx = s.index(s[-1])
if idx == n-1:
res += n // 2
s.pop()
continue
res += idx
s.pop()
s.pop(idx)
n -= 2
return res提交代码评测得到：耗时147ms，占用内存13.9MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/03/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
