周赛笔记270

一、找出 3 位偶数

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。

你需要找出 所有 满足下述条件且 互不相同 的整数：

• 该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
• 该整数不含 前导零
• 该整数是一个 偶数

例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。

将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        res = set()
        vis = set()
        for num in [i for i in permutations(digits, 3)]:
            if num in vis:
                continue
            vis.add(num)
            
            if num[0] == 0 or num[2]%2:
                continue
            else:
                res.add(num)
                        
        res = [num[0]*100+num[1]*10+num[2] for num in res]
        res.sort()
                        
        return res

一行的版本：

return sorted({i*100+j*10+k for i, j, k in itertools.permutations(digits, 3) if i != 0 and k%2 == 0})

一开始纯暴力超时了一次

二、删除链表的中间节点⭐

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head.next:
            return None
        
        p = head
        n = 0
        while p:
            n += 1
            p = p.next
        n = n - n//2   # fast指针需要先走的步数
        
        slow, fast = head, head
        while n:
            n -= 1
            fast = fast.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head

三、从二叉树一个节点到另一个节点每一步的方向⭐

请你返回从 s 到 t 最短路径 每一步的方向。

相关问题: LCA（Lowest Common Ancestor）问题

超时：

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        p = ""
        q = ""
        def dfs(node, path):
            nonlocal p, q
            if p and q:
                return 
            if node.val == startValue:
                p = path
            if node.val == destValue:
                q = path
            if node.left:
                dfs(node.left, path+"L")
            if node.right:
                dfs(node.right, path+"R")

        
        dfs(root, "")
        cnt = 0
        for x,y in zip(p, q):
            if x==y:
                cnt += 1
            else:
                break
        #print(p, q, cnt)
        n1, n2 = len(p), len(q)
        res = ""
        res += "U"*(n1-cnt)
        res += q[cnt:]

        return res

借鉴过来的，刚开始只找一个值，就不会超时了

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def vis(node = root, father = None):
            if not node:
                return 
            if node.val == startValue:
                self.start = node
            node.father = father
            vis(node.left, node)
            vis(node.right, node)
        vis()

        visited = set([startValue])
        to_vis = [[self.start, ""]]
        while to_vis:
            node, path = to_vis.pop(0)
            if node.val == destValue:
                return path
            if node.father and node.father.val not in visited:
                visited.add(node.father.val)
                to_vis.append([node.father, path+"U"])
            if node.left and node.left.val not in visited:
                visited.add(node.left.val)
                to_vis.append([node.left, path+"L"])
            if node.right and node.right.val not in visited:
                visited.add(node.right.val)
                to_vis.append([node.right, path+"R"])
        return None

四、合法重新排列数对⭐

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:

        # 开始建立图
        d = defaultdict(list)
        out = Counter()
        for u, v in pairs:
            d[u].append(v)
            out[u] += 1
            out[v] -= 1

        res = []
        def dfs(cur, pre = None):
            while d[cur]:
                tmp = d[cur].pop()
                dfs(tmp, cur)
            if pre is not None:
                res.append([pre, cur])
        
        # 找到 出度>入度 的点作为 begin
        for begin, f in out.items():
            if f == 1:
                break
        dfs(begin)
        return res[::-1]

参考 第332题