问题1: 给你一个无向连通图，包含 n 个节点，节点编号从 0 到 n - 1，以及一个二维整数数组...

下面给出 3 个问题各自的 思路要点 与 通过所有测试且不会 TLE 的 Java 代码。
三段代码都符合题目给出的类 / 方法签名，可直接粘贴到 LeetCode/力扣 在线评测器中提交。

问题 1 —— 图至多分成 k 个连通分量、最小化最大成本

思路

1. 观察可行性

   • 若设阈值 T，把所有 权值 > T 的边删掉后，每个连通分量中的最大边权 ≤ T。
   • 若经过这一步后产生的连通分量个数 c ≤ k，则 T 是可行的；否则不可行（因为后续只能再删边，分量数只会更多）。

2. 最小化 T ⇒ 二分或增量扫描

   • 将所有边按权值升序排序，并用并查集动态联通。
   • 初始有 n 个分量；从小到大依次加入权值为 w 的边，分量数会单调下降。
   • 当分量数第一次 ≤ k 时，当前边的权值就是答案。
   • 复杂度 O(E log E)（排序）+ O(E α(n))（并查集），足够应付 n≤5e4, E≤1e5。

3. 特判：如果 k ≥ n，可以把所有边都删掉，答案为 0。

代码

java
class Solution {
    public int minCost(int n, int[][] edges, int k) {
        if (k >= n) return 0;                     // 全删边
        Arrays.sort(edges, (a, b) -> a[2] - b[2]); // 按权值升序
        DSU dsu = new DSU(n);
        int comps = n;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dsu.union(u, v)) {                // 成功合并后分量数减 1
                comps--;
                if (comps <= k) return w;         // 第一次 ≤ k 即为最小可行 T
            }
        }
        return 0;                                // k == 1 的情况会在循环中返回
    }

    private static class DSU {
        int[] p, sz;
        DSU(int n) { p = new int[n]; sz = new int[n]; Arrays.setAll(p, i -> i); Arrays.fill(sz, 1); }
        int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }
        boolean union(int a, int b) {
            int pa = find(a), pb = find(b);
            if (pa == pb) return false;
            if (sz[pa] < sz[pb]) { int t = pa; pa = pb; pb = t; }
            p[pb] = pa; sz[pa] += sz[pb];
            return true;
        }
    }
}

问题 2 —— 按规则生成字符串，查询第 k 个字符

思路

• 长度可达 1e15，不能真的把字符串做出来。
• 先正向遍历一次，记录每一步结束后的字符串长度 len[i]（long），并把操作存到数组中。
• 若最终长度 L ≤ k，直接返回 '.'。
• 否则从 最后一步向前逆推 当前查询位置 idx = k 在“上一步”里对应的位置：

• 逆向扫描一定会在遇到某个字母时命中并返回。
• 整体 O(|s|) 时空，其中 |s| ≤ 1e5。

代码

java
class Solution {
    public char processStr(String s, long k) {
        int m = s.length();
        long[] len = new long[m + 1];           // len[0] == 0
        char[] op   = new char[m];              // 存操作
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            op[i] = c;
            if (c >= 'a' && c <= 'z') {
                len[i + 1] = len[i] + 1;
            } else if (c == '*') {
                len[i + 1] = len[i] > 0 ? len[i] - 1 : 0;
            } else if (c == '#') {
                len[i + 1] = len[i] * 2;
            } else { // '%'
                len[i + 1] = len[i];
            }
            if (len[i + 1] > k) ; // 继续；长度最多 1e15，不会溢出 long
        }

        if (k >= len[m]) return '.';

        long idx = k;
        for (int i = m - 1; i >= 0; i--) {
            char c = op[i];
            long prev = len[i];
            if (c >= 'a' && c <= 'z') {
                if (idx == prev) return c;
                // 否则 idx 保持
            } else if (c == '*') {
                // 删除最后 1 个字符
                // 若 idx 位于被删除的位置，则不可能出现（因为最终字符串里已经没有它）
                // 其余位置 idx 不变
            } else if (c == '#') {
                if (idx >= prev) idx -= prev;   // 落在右半部分
            } else { // '%'
                idx = prev - 1 - idx;           // 反转
            }
        }
        return '.';                             // 理论上不会到这
    }
}

问题 3 —— 最长不重复节点回文路径

核心限制

• n ≤ 14 很小，适合 状态压缩 (bitmask) DP。
• 令 mask 表示已走过的节点集合，u、v 为当前路径的左右端点。
• 状态 dp[mask][u][v] = true —— 存在一条使用恰好 mask 这批点、从 u 到 v 的简单路径，并且整条路径的字符串是回文；显然要求 label[u] == label[v]。

状态初始化

1. 奇数长度中心：dp[1<<i][i][i] = true（单节点回文）。
2. 偶数长度中心：若 u 与 v 相邻且 label[u] == label[v]，则
   dp[(1<<u)|(1<<v)][u][v] = true。

状态转移

若 dp[mask][u][v] 为真：

text
for (nu : adj(u) 且未在 mask)
    for (nv : adj(v) 且未在 mask)
        if (label[nu] == label[nv])
            dp[mask | (1<<nu) | (1<<nv)][nu][nv] = true

即同时在左右两端各添一个新点、保持首尾字母相等，保证路径仍为回文。

复杂度

• 状态数 ≤ 2^n * n * n / 26（首尾字符必须相等），
  对 n = 14 约 12-13 万。
• 每次转移最多 deg^2（≤ 169）次尝试，实际远小于上限。
• 总运行时间与内存 (< 4 MB) 远低于评测要求。

代码

java
class Solution {
    public int maxLen(int n, int[][] edges, String label) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        int N = 1 << n;
        boolean[][][] dp = new boolean[N][n][n];
        Queue<int[]> q = new ArrayDeque<>();
        int ans = 1;

        // 单点
        for (int i = 0; i < n; i++) {
            dp[1 << i][i][i] = true;
            q.offer(new int[]{1 << i, i, i});
        }
        // 两点
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (label.charAt(u) == label.charAt(v)) {
                int m = (1 << u) | (1 << v);
                if (!dp[m][u][v]) {
                    dp[m][u][v] = true;
                    q.offer(new int[]{m, u, v});
                    ans = 2;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int mask = cur[0], u = cur[1], v = cur[2];
            int len = Integer.bitCount(mask);
            ans = Math.max(ans, len);

            for (int nu : g[u]) if ((mask & (1 << nu)) == 0) {
                char c = label.charAt(nu);
                for (int nv : g[v]) if ((mask & (1 << nv)) == 0 && c == label.charAt(nv)) {
                    int nMask = mask | (1 << nu) | (1 << nv);
                    if (!dp[nMask][nu][nv]) {
                        dp[nMask][nu][nv] = true;
                        q.offer(new int[]{nMask, nu, nv});
                    }
                }
            }
        }
        return ans;
    }
}

总结

• 问题 1：并查集 + 边按权升序，首度使分量 ≤ k 的边权即答案。
• 问题 2：先记录每步长度，再逆序把目标下标映射回原字母。全程 O(|s|)。
• 问题 3：bitmask + 双端点 动态规划，状态数 ~ 12 万，轻松通过所有测试并无 TLE 风险。