力扣第 450 场周赛

本文最后更新于 2 分钟前,文中所描述的信息可能已发生改变。

3550. 数位和等于下标的最小下标 - 力扣(LeetCode)

解题思路

遍历,按要求求数位和,满足条件返回下标

示例代码

python
class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, x in enumerate(nums):
            s = sum(map(int, str(x)))
            if s == i:
                return i
        return -1

3551. 数位和排序需要的最小交换次数 - 力扣(LeetCode)

解题思路

排序,找循环节个数,每个循环节交换次数为节的长度 - 1

示例代码

python
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        a = sorted(range(n), key=lambda p: nums[p])
        b = sorted(a, key=lambda p: (sum(map(int, str(nums[p])))))
        vis = [False] * n
        for i in range(n):
            if i != b[i] and not vis[i]:
                while i != b[i] and not vis[b[i]]:
                    vis[i] = True
                    i = b[i]
                    ans += 1
        return ans

3552. 网格传送门旅游 - 力扣(LeetCode)

解题思路

01BFS,不能重新建图套最短路模板,会超时;传送门使用一次后,全部清空,防止再次使用

示例代码

python
class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        n, m = len(matrix), len(matrix[0])
        d = defaultdict(list)
        for i, row in enumerate(matrix):
            for j, c in enumerate(row):
                if c in ascii_uppercase:
                    d[c].append((i, j))
        q = deque([(0, 0)])
        dis = [[inf] * m for _ in range(n)]
        dis[0][0] = 0
        while q:
            x, y = q.popleft()
            if x == n - 1 and y == m - 1:
                return dis[n - 1][m - 1]
            c = matrix[x][y]
            if c in ascii_uppercase and d[c]:
                for nx, ny in d[c]:
                    if x != nx or y != ny and dis[nx][ny] > dis[x][y]:
                        dis[nx][ny] = dis[x][y]
                        q.appendleft((nx, ny))
                del d[c]
            for dx, dy in (1, 0), (0, 1), (-1, 0), (0, -1):
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] != '#' and dis[x][y] + 1 < dis[nx][ny]:
                    dis[nx][ny] = dis[x][y] + 1
                    q.append((nx, ny))
        return -1

3553. 包含给定路径的最小带权子树 II - 力扣(LeetCode)

解题思路

lca 模板题,由于是在树内,三个节点必存在交点,最小子树权值其实也就是交点到三个节点的路径上的权值之和

赛时没做

参考:3553. 包含给定路径的最小带权子树 II - 力扣(LeetCode)

示例代码

python
class Solution:
    def minimumWeight(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        lca = LcaWithWeight(edges)
        return [(lca.get_dis(a, b) + lca.get_dis(b, c) + lca.get_dis(a, c)) // 2 for a, b, c in queries]
py
from typing import List


class LowestCommonAncestor:
    __slots__ = ['depth', 'pa']

    def __init__(self, edges: List[List[int]]) -> None:
        n = len(edges) + 1
        m = n.bit_length()
        g = [[] for _ in range(n)]
        self.depth = depth = [0] * n
        self.pa = pa = [[-1] * m for _ in range(n)]
        for x, y in edges:  # 节点编号从 0 开始
            g[x].append(y)
            g[y].append(x)

        def dfs(x: int, fa: int) -> None:
            pa[x][0] = fa
            for y in g[x]:
                if y != fa:
                    depth[y] = depth[x] + 1
                    dfs(y, x)
        dfs(0, -1)

        for i in range(m - 1):
            for x in range(n):
                if (p := pa[x][i]) != -1:
                    pa[x][i + 1] = pa[p][i]

    def get_kth_ancestor(self, node: int, k: int) -> int:
        """返回 node 的第 k 个祖先"""
        for i in range(k.bit_length()):
            if k >> i & 1:
                node = self.pa[node][i]
        return node

    def get_lca(self, x: int, y: int) -> int:
        """返回 x 和 y 的最近公共祖先(节点编号从 0 开始)"""
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x]) # 使 y 和 x 在同一深度
        if y == x:
            return x
        for i in range(len(self.pa[x]) - 1, -1, -1):
            px, py = self.pa[x][i], self.pa[y][i]
            if px != py:
                x, y = px, py  # 同时上跳 2**i 步
        return self.pa[x][0]

class LcaWithWeight:
    __slots__ = ['depth', 'dis', 'pa']

    def __init__(self, edges: List[List[int]]) -> None:
        n = len(edges) + 1
        m = n.bit_length()
        g = [[] for _ in range(n)]
        self.depth = depth = [0] * n
        self.dis = dis = [0] * n
        self.pa = pa = [[-1] * m for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
            g[y].append((x, w))

        def dfs(x: int, fa: int) -> None:
            pa[x][0] = fa
            for y, w in g[x]:
                if y != fa:
                    depth[y] = depth[x] + 1
                    dis[y] = dis[x] + w
                    dfs(y, x)

        dfs(0, -1)

        for i in range(m - 1):
            for x in range(n):
                if (p := pa[x][i]) != -1:
                    pa[x][i + 1] = pa[p][i]

    def get_kth_ancestor(self, node: int, k: int) -> int:
        """返回 node 的第 k 个祖先"""
        for i in range(k.bit_length()):
            if k >> i & 1:
                node = self.pa[node][i]
        return node

    def get_lca(self, x: int, y: int) -> int:
        """返回 x 和 y 的最近公共祖先(节点编号从 0 开始)"""
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
        if y == x:
            return x
        for i in range(len(self.pa[x]) - 1, -1, -1):
            px, py = self.pa[x][i], self.pa[y][i]
            if px != py:
                x, y = px, py
        return self.pa[x][0]

    def get_dis(self, x: int, y: int) -> int:
        """返回 x 和 y 之间的距离"""
        return self.dis[x] + self.dis[y] - self.dis[self.get_lca(x, y)] * 2
LeetCode Biweekly Contest 157
Classification of LeetCode Weekly Competition Questions