欢迎大家加QQ群:623375442。这周题目难度不大比较套路。

Q1. 特殊操作字符串 I

题目翻译

给定一个字符串 s,它由小写英文字母和特殊字符 *#% 组成。按照从左到右的顺序,处理字符串并构建新的字符串 result,处理规则如下:

  1. 如果当前字符是小写英文字母,则将该字母附加到 result 的末尾。
  2. 如果当前字符是 *,则删除 result 的最后一个字符(如果存在)。
  3. 如果当前字符是 #,则将当前的 result 复制一遍并追加到自身后面。
  4. 如果当前字符是 %,则将当前的 result 进行反转。

返回处理完所有字符后得到的最终字符串 result

示例:

输入:s = "a#b%*"
输出:"ba"

处理过程:
 i   s[i]   操作               当前 result
 0    'a'   附加 'a'           "a"
 1    '#'   复制自身            "aa"
 2    'b'   附加 'b'           "aab"
 3    '%'   反转                "baa"
 4    '*'   删除最后一个字符   "ba"

解题思路

使用一个 StringBuilder sb 来维护当前的 result

  • 遇到小写字母时,调用 sb.append(c)
  • 遇到 * 时,如果 sb 非空,则删除最后一个字符:sb.deleteCharAt(sb.length() - 1)
  • 遇到 # 时,将 sb 的内容复制一遍并追加:sb.append(sb)
  • 遇到 % 时,对 sb 进行原地反转:sb.reverse()

遍历完输入字符串后,将 sb.toString() 返回。

class Solution {
    public String processStr(String s) {
        // 使用 StringBuilder 来高效地构建和修改字符串
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isLowerCase(c)) {
                // 如果是小写字母,直接追加到 sb
                sb.append(c);
            } else if (c == '*') {
                // 如果是 '*',删除 sb 的最后一个字符(如果存在)
                if (sb.length() >= 1) sb.deleteCharAt(sb.length() - 1);
            } else if (c == '#') {
                // 如果是 '#',将当前 sb 内容复制并追加到自身后面
                sb.append(sb);
            } else {
                // 如果是 '%',将 sb 内容进行翻转
                sb.reverse();
            }
        }
        // 返回最终结果
        return sb.toString();
    }
}

Q2. 最小化最大组件代价

题目翻译

给定一个无向连通图,包含 n 个节点(编号从 0n-1),以及一个 edges 数组,其中 edges[i] = [u_i, v_i, w_i] 表示节点 u_iv_i 之间存在一条权重为 w_i 的无向边。另外给定一个整数 k

你可以删除任意条边,使得剩余图的连通分量数目不超过 k。每个连通分量的代价定义为该连通分量中边权重的最大值;如果某个连通分量没有边,则其代价为 0

返回在满足至多 k 个连通分量的前提下,所有连通分量的最大代价的最小可能值。

示例:

输入:n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
输出:4

说明:
删除权重为 6 的边(节点 3-4 之间),此时图分为两部分:
- 一个只包含节点 4 的单独连通分量,费用为 0。
- 其余节点的连通分量中最大边权为 4。
因此最大代价为 4。

解题思路

要想让图分成至多 k 个组件,并且最大组件代价最小,就要尽可能保留小权重的边,删除大权重的边。当保留的边数使得连通分量数量降到 k 时,当前考虑的边权就是答案。

具体做法:

  1. 如果 n <= k,说明可以让每个节点单独为一个连通分量,最大代价为 0,直接返回 0
  2. 按照边权从小到大排序 edges
  3. 使用并查集(DSU),一开始有 n 个连通分量。
  4. 从最小权重边开始,依次尝试合并两个端点所在的分量。合并一次(即删除更高权重边以外都保留),分量数 remain1
  5. remain <= k 时,说明当前这条边的权值就是最终答案。
class Solution {
    public int minCost(int n, int[][] edges, int k) {
        // 如果节点数不超过 k,则可以不保留任何边,最大代价为 0
        if (n <= k) {
            return 0;
        }
        // 按权值升序排序
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        // 初始化并查集
        DSU uf = new DSU(n);
        // 遍历每条边
        for (int[] e : edges) {
            uf.union(e[0], e[1]); // 合并两个节点
            // 如果连通分量数量已降至 k 或更少,则当前边权即答案
            if (uf.remain <= k) {
                return e[2];
            }
        }
        // 理论上不会到达这里
        return Integer.MAX_VALUE;
    }
}

// 并查集(DSU)结构
class DSU {
    int[] parent; // parent[i] 表示节点 i 的父节点
    int remain;   // 当前剩余的连通分量数量

    public DSU(int N) {
        parent = new int[N];
        remain = N; // 初始时每个节点都是单独的分量
        for (int i = 0; i < N; ++i) {
            parent[i] = i; // 自己的父节点初始化为自己
        }
    }

    // 查找操作,带路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并两个集合
    public void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            parent[fx] = fy; // 将 fx 的根指向 fy
            --remain;        // 分量数减 1
        }
    }
}

Q3. 特殊操作字符串 II

题目翻译

给定一个字符串 s,由小写英文字母和特殊字符 *#% 组成;以及一个整数 k

同样按从左到右对字符串进行处理,构建一个新的字符串 result,规则与 Q1 完全一致:

  1. 小写字母:追加到 result
  2. *:删除 result 最后的一个字符(如果存在)。
  3. #:复制当前 result 并追加到自身。
  4. %:反转当前 result

返回最终 result 的第 k 个字符(0 下标)。如果 k 超出 result 长度范围,则返回 '.'

示例:

输入:s = "a#b%*", k = 1
输出:"a"

同 Q1 的示例,最终字符串为 "ba",其中下标 1 处的字符是 'a'。

解题思路

由于最终字符串的长度可能非常大(指数级增长),无法直接构建。需要在遍历时维护当前长度 l,并使用倒序扫描来 "回溯" 找到第 k 个字符。

  1. 预处理阶段:先按原顺序扫描 s,用一个栈 stack 记录每次遇到 * 操作前的长度,将长度 len 变化记录下来,最后得到处理完所有字符后的总长度 l
  2. 如果 l <= k,说明 k 越界,直接返回 '.'
  3. s 的末尾开始倒序遍历每个操作,根据以下规则更新 lk
    • 字母:如果 l == k+1,则当前字符就是答案;否则 l--
    • *:从 stack 弹出上一次删除前的长度,赋值给 l
    • #:因为 # 是复制一倍,故当前长度为原长度的两倍,记原长度为 ne = l/2。如果 k >= ne(落在复制部分),则 k -= ne;然后将 l = ne
    • %:反转操作对索引的映射是 k = l-1-k

直到找到目标字符。

class Solution {
    public char processStr(String s, long k) {
        // 用栈记录每次 '*' 删除操作前的长度
        Stack<Long> stack = new Stack<>();
        // 先计算最终字符串的长度
        long l = calculateLength(s, stack);
        // 如果 k 越界,直接返回 '.'
        if (l <= k) {
            return '.';
        }
        // 从后向前回溯操作
        for (int i = s.length() - 1; i >= 0; --i) {
            char c = s.charAt(i);
            if (Character.isLowerCase(c)) {
                // 如果当前位置是字母,且当前 l 正好是 k+1,则找到了答案
                if (l == k + 1) {
                    return c;
                }
                // 否则长度减 1,继续回溯
                --l;
            } else if (c == '*') {
                // '*' 操作:回退到删除前的长度
                l = stack.pop();
            } else if (c == '#') {
                // '#' 操作:复制操作前的长度
                long ne = l / 2;
                // 如果 k 落在复制出来的第二份里,则调整 k
                if (ne <= k) {
                    k -= ne;
                }
                // 回退 l 到复制前
                l = ne;
            } else {
                // '%' 操作:索引映射到反转前的位置
                k = l - 1 - k;
            }
        }
        // 理论上不会到达这里
        return '1';
    }

    // 计算最终字符串长度的辅助函数
    private long calculateLength(String s, Stack<Long> stack) {
        long len = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isLowerCase(c)) {
                // 字母:长度加 1
                ++len;
            } else if (c == '*') {
                // '*':记录当前长度到栈,然后删除最后一个字符(如果有)
                stack.push(len);
                len = Math.max(0, len - 1);
            } else if (c == '#') {
                // '#': 复制,长度翻倍
                len *= 2;
            }
            // '%' 只影响内容顺序,不改变长度
        }
        return len;
    }
}

Q4. 图中的最长回文路径

题目翻译

给定一个整数 n 和一个无向图,图中包含 n 个节点(编号 0n-1),由二维数组 edges 表示无向边,其中 edges[i] = [u_i, v_i] 表示节点 u_iv_i 之间存在一条边。另有一个长度为 n 的字符串 label,其中 label[i] 是节点 i 对应的字符。

你可以从任意节点出发,沿着边移动,每个节点至多访问一次,形成一条简单路径。路径上的节点所对应的字符连接成一个字符串。返回可以形成的回文字符串的最大长度。

示例:

输入:n = 3, edges = [[0,1],[1,2]], label = "aba"
输出:3

解释:
可选路径 0 → 1 → 2,对应字符串 "aba",是最长的回文,长度为 3。

解题思路

由于节点数 n 最多为较小量级(例如 n <= 12),可以用状态压缩和动态规划。

  1. 状态表示:用一个整数 mask 的二进制位来表示当前路径上访问过的节点集合,mask 范围 [1, 2^n)
  2. 预处理所有子集:先按子集大小(节点数)分组,存储到 countMap[c],其中包含所有大小为 c 的子集 mask
  3. 连通性预处理:使用邻接矩阵 isConnected[u][v] 判断两个节点是否有边。
  4. 动态规划三维数组isValid[l][r][mask] 表示在子集 mask 范围内,能够构成一个以 l 为起点、r 为终点的回文路径。

    • 若子集大小 i = 1,单节点总是回文,isValid[l][l][mask] = true
    • i = 2,两节点如果连通且字符相同,则 isValid[l][r][mask] = true
    • i > 2,枚举子集两端 lr,要求字符相同,且在剩余子集 remain = mask ^ (1<<l) ^ (1<<r) 中存在一条从某 t1t2 的回文路径,并且 t1l 相邻,t2r 相邻。
  5. 更新结果:每当某个 isValid[l][r][mask] 变为 true,就可以更新最大回文长度 res = 子集大小

此方法时间复杂度约为 O(n^2 * 2^n * n^2),适用于 n <= 12 的场景。

class Solution {
    public int maxLen(int n, int[][] edges, String label) {
        // 建立邻接矩阵,标记节点间连通关系
        boolean[][] isConnected = new boolean[n][n];
        for (int[] e : edges) {
            isConnected[e[0]][e[1]] = true;
            isConnected[e[1]][e[0]] = true;
        }
        // 按子集大小分组存储所有子集
        List<Integer>[] countMap = new List[n + 1];
        for (int i = 1; i <= n; ++i) {
            countMap[i] = new ArrayList<>();
        }
        int max = 1 << n;
        for (int mask = 1; mask < max; ++mask) {
            int c = Integer.bitCount(mask); // 子集大小
            countMap[c].add(mask);
        }
        // 三维 DP 数组,isValid[l][r][mask] 表示 mask 子集内可从 l 到 r 构成回文路径
        boolean[][][] isValid = new boolean[n][n][max];
        int res = 1; // 最少回文长度为 1

        // 按子集大小从小到大枚举
        for (int size = 1; size <= n; ++size) {
            for (int mask : countMap[size]) {
                // 枚举子集两端节点 l
                outer:
                for (int l = 0; l < n; ++l) {
                    if ((mask & (1 << l)) == 0) continue; // l 不在子集中

                    if (size == 1) {
                        // 单节点子集,总是回文
                        isValid[l][l][mask] = true;
                    } else if (size == 2) {
                        // 两节点子集,如果连通且字符相同,则是回文
                        for (int r = l + 1; r < n; ++r) {
                            if ((mask & (1 << r)) != 0
                                    && label.charAt(l) == label.charAt(r)
                                    && isConnected[l][r]) {
                                isValid[l][r][mask] = true;
                                isValid[r][l][mask] = true;
                                res = 2;
                            }
                        }
                    } else {
                        // 大于两个节点的子集,需要更复杂的转移
                        for (int r = l + 1; r < n; ++r) {
                            if ((mask & (1 << r)) != 0
                                    && label.charAt(l) == label.charAt(r)) {
                                int remain = mask ^ (1 << l) ^ (1 << r);
                                // 在剩余子集中寻找可行路径
                                for (int t1 = 0; t1 < n; ++t1) {
                                    if ((remain & (1 << t1)) == 0 || !isConnected[t1][l]) continue;
                                    for (int t2 = 0; t2 < n; ++t2) {
                                        if ((remain & (1 << t2)) != 0
                                                && isValid[t1][t2][remain]
                                                && isConnected[t2][r]) {
                                            // 找到可行回文,更新状态和结果
                                            isValid[l][r][mask] = true;
                                            isValid[r][l][mask] = true;
                                            res = size;
                                            // 跳出到下一个 l
                                            continue outer;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *