LeetCode笔记：Weekly Contest 270
LeetCode笔记：Weekly Contest 270
codename_cys
发布于 2021-12-08 14:19:27
发布于 2021-12-08 14:19:27
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
题目一的解题思路我这边就很暴力的直接枚举了一下全部排列，然后拍了个序。
不过事实上可以优化一下，因为数字最多也就3位数，因此重复超过3的都可以忽略，由此可以大幅减少枚举的个数，不过这里就不多做展开了。
2. 代码实现
给出python代码实现如下：
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
res = set()
for a, b, c in permutations(digits, 3):
if a != 0 and c % 2 == 0:
res.add(100*a + 10*b + c)
return sorted(res)提交代码评测得到：耗时4496ms，占用内存14.4MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题感觉是这次的4题当中最简单的一题，只要先数出数组的总长度，然后找到中心位置，然后删除对应的点即可。
唯一需要注意一下的就是考虑一下结点数特别少的边界情况即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
cnt, p = 0, head
while p:
p = p.next
cnt += 1
if cnt == 1:
return None
elif cnt == 2:
head.next = None
return head
cnt = cnt // 2
p = head
for _ in range(cnt-1):
p = p.next
p.next = p.next.next
return head提交代码评测得到：耗时1896ms，占用内存61.1MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实也不复杂，首先通过一个遍历搜索找到所有节点的上下游关系。
然后，我们只要分别将src与tgt进行上游回溯，找到第一个公共父节点，即可确定最终的路线。
2. 代码实现
给出python代码实现如下：
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
nodes ={}
def dfs(root, p):
nonlocal nodes
if root is None:
return
nodes[root.val] = (p, root.left, root.right)
dfs(root.left, root)
dfs(root.right, root)
return
dfs(root, None)
s, val = [startValue], startValue
while True:
u, l, r = nodes[val]
if u is None:
break
s.append(u.val)
val = u.val
s = {v:idx for idx, v in enumerate(s)}
t, path = destValue, ""
while t not in s:
u, l, r = nodes[t]
if u.left and u.left.val == t:
path = "L" + path
else:
path = "R" + path
t = u.val
return "U" * s[t] + path提交代码评测得到：耗时1316ms，占用内存160.2MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题坦率地说没有搞定，不过看了答案之后发现巨简单，就是一个简单的dfs。
不过这个思路我其实想到过，感觉无法解决多个环存在的情况，看着答案也没有香的很清楚，所以这里就不多说了，只把网上大佬的code放在下面，有兴趣的读者可以自行研读一下。
2. 代码实现
网上大佬的解答如下：
from collections import defaultdict
class Solution(object):
def validArrangement(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: List[List[int]]
"""
deg = defaultdict(int)
adj = defaultdict(list)
for u, v in pairs:
adj[u].append(v)
deg[u] += 1
deg[v] -= 1
_, src = max((v, k) for k, v in deg.iteritems())
ans = []
def _f(u):
while adj[u]:
v = adj[u].pop()
_f(v)
ans.append(u)
_f(src)
n = len(ans)
return [[ans[n-i-1], ans[n-i-2]] for i in xrange(n-1)]本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/12/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
