LeetCode Weekly Contest 458

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

3612. 用特殊操作处理字符串 I - 力扣（LeetCode） ​

解题思路 ​

模拟

示例代码 ​

python
class Solution:
    def processStr(self, s: str) -> str:
        ans = []
        for c in s:
            if c.isalpha():
                ans.append(c)
            elif c == '*':
                if ans:
                    ans.pop()
            elif c == '#':
                ans.extend(ans)
            else:
                ans.reverse()
        return ''.join(ans)

3613. 最小化连通分量的最大成本 - 力扣（LeetCode） ​

解题思路 ​

并查集，边集按权值排序，并查集不断合并为连通分量，当连通分量小于 k 时退出

示例代码 ​

python
class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        uf = UnionFind(n)
        edges.sort(key=lambda p: p[-1])
        cnt = n
        ans = 0
        for u, v, w in edges:
            if uf.connected(u, v):
                continue
            uf.union_rank(u, v)
            cnt -= 1
            if cnt < k:
                break
            ans = w
        return ans
py
class UnionFind:
    def __init__(self, n: int) -> None:
        self.n = n
        self.parent = list(range(n))
        self.rank = [1] * n
        self.size = [1] * n

    def find(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union_by_size(self, x: int, y: int) -> None:
        x_root, y_root = self.find(x), self.find(y)
        if x_root != y_root:
            if self.size[y_root] <= self.size[x_root]:
                self.parent[y_root] = x_root
                self.size[x_root] += self.size[y_root]
            else:
                self.parent[x_root] = y_root
                self.size[y_root] += self.size[x_root]

    def union_rank(self, x: int, y: int) -> None:
        x_root, y_root = self.find(x), self.find(y)
        if x_root != y_root:
            if self.rank[y_root] <= self.rank[x_root]:
                self.parent[y_root] = x_root
            else:
                self.parent[x_root] = y_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

3614. 用特殊操作处理字符串 II - 力扣（LeetCode） ​

解题思路 ​

模拟，正序计算最终字符串长度，再逆序判断即可

示例代码 ​

python
class Solution:
    def processStr(self, s: str, k: int) -> str:
        k += 1
        n = len(s)
        f = [0] * (n + 1)
        for i, c in enumerate(s):
            if c.isalpha():
                f[i + 1] = f[i] + 1
            elif c == '*':
                f[i + 1] = max(f[i] - 1, 0)
            elif c == '#':
                f[i + 1] = f[i] * 2
            else:
                f[i + 1] = f[i]
        if f[-1] < k:
            return '.'
        for i in range(n - 1, -1, -1):
            c = s[i]
            if c == '#':
                if f[i] < k:
                    k -= f[i]
            elif c == '%':
                k = f[i + 1] - k + 1
            elif c != '*' and f[i + 1] == k:
                return c
        return ''

3615. 图中的最长回文路径 - 力扣（LeetCode） ​

解题思路 ​

记忆化搜索，数位 DP，通过中心扩展实现回文字符串，分别计算奇数和偶数长度

参考：[中心扩展法 + 状压 DP（Python/Java/C++/Go）](https://leetcode.cn/problems/longest-palindromic-path-in-graph/solutions/3722469/zhong-xin-kuo-zhan-fa-zhuang-ya-dp-by-en-ai9s/

示例代码 ​

python
fmax = lambda x, y: x if x > y else y

class Solution:
    def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:
        ans = 0
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        @cache
        def dfs(u, v, msk):
            res = msk.bit_count()
            for nu in g[u]:
                if msk >> nu & 1:
                    continue
                for nv in g[v]:
                    if nu == nv or (msk >> nv & 1) or label[nu] != label[nv]:
                        continue
                    if nu > nv:
                        nu, nv = nv, nu
                    res = fmax(res, dfs(nu, nv, msk | (1 << nu) | (1 << nv)))
            return res

        for u in range(n):
            ans = fmax(ans, dfs(u, u, 1 << u))
            for v in g[u]:
                if u < v and label[u] == label[v]:
                   ans = fmax(ans, dfs(u, v, (1 << u) | (1 << v)))
        dfs.cache_clear()
        return ans
Material Calculation Common Steps
LeetCode Weekly Contest 457