提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode笔记：Weekly Contest 270

笔记 代码
2023-04-18 14:48:09 时间

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)]

相关文章