Weekly Contest 456

欢迎大家加QQ群：623375442。周赛题解都会在周日下午3点左右发布。这周题目不难,TrieTree周

Q1. Partition String

给定一个字符串 s，按照以下步骤将其分割为多个唯一的子串：

• 从索引0开始构建一个子串。
• 继续扩展当前子串，直到当前子串中的字符没有出现过。
• 一旦当前子串是唯一的，将其加入结果列表，并从下一个字符开始构建新的子串。
• 重复上述步骤直到遍历完整个字符串。

返回字符串数组 segments，其中 segments[i] 是第i个子串。

测试样例：

输入：s = "abbccccd"

输出：["a","b","bc","c","cc","d"]

解答：

• 使用字符串构建过程中的每个子串，避免重复。
• 利用Trie树（前缀树）来存储已出现的字符及其组合。

class Solution {
    public List<String> partitionString(String s) {
        List<String> res = new ArrayList<>();
        TrieNode root = new TrieNode(), point = root;
        StringBuilder sb = new StringBuilder();

        // 遍历字符串中的每个字符
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            sb.append(c); // 添加字符到当前子串

            // 如果当前字符没有出现过，则将其加入结果列表
            if (!point.next.containsKey(c)) {
                point.next.put(c, new TrieNode()); // 创建新的节点
                res.add(sb.toString()); // 将当前子串添加到结果
                sb = new StringBuilder(); // 清空当前子串
                point = root; // 重置为根节点，开始新的子串
            } else {
                point = point.next.get(c); // 否则继续扩展当前子串
            }
        }
        return res;
    }
}

class TrieNode {
    HashMap<Character, TrieNode> next;

    public TrieNode() {
        next = new HashMap<>();
    }
}

Q2. Longest Common Prefix Between Adjacent Strings After Removals

给定一个字符串数组 words，对于每个索引 i，执行以下步骤：

• 删除索引为 i 的元素。
• 计算删除该元素后的数组中相邻字符串之间的最长公共前缀的长度。

返回一个数组 answer，其中 answer[i] 是删除索引 i 后相邻字符串之间的最长公共前缀的长度。如果没有相邻的字符串或没有公共前缀，则 answer[i] 应该为0。

测试样例：

输入： words = ["dog","racer","car"]

输出：[0,0,0]

解释：删除任何索引都会导致结果为0。

解答：

• 使用Trie树来存储每个单词的字符，并计算相邻单词的公共前缀。
• 通过遍历并删除每个元素，记录删除后的公共前缀长度。

class Solution {
    public int[] longestCommonPrefix(String[] words) {
        int len = words.length;
        TrieNode root = new TrieNode();
        int[][] overlap = new int[len][2];

        // 遍历每个单词并插入到Trie树中
        for (int i = 0; i < words.length; ++i) {
            TrieNode point = root;
            String word = words[i];
            for (int j = 0; j < word.length(); ++j) {
                char c = word.charAt(j);
                if (!point.next.containsKey(c)) {
                    point.next.put(c, new TrieNode());
                }
                point = point.next.get(c);

                // 计算当前公共前缀的长度
                if (point.last[0] == i - 1 || point.last[1] == i - 1) {
                    overlap[i][0] = j + 1;
                }
                if (point.last[0] == i - 2 || point.last[1] == i - 2) {
                    overlap[i][1] = j + 1;
                }
                point.addPos(i);
            }
        }

        // 使用TreeMap记录最长公共前缀
        TreeMap<Integer, Integer> sortList = new TreeMap<>();
        for (int[] o : overlap) {
            addKey(sortList, o[0]);
        }

        int[] res = new int[len];
        for (int i = 0; i < len; ++i) {
            removeKey(sortList, overlap[i][0]);
            if (i + 1 < len) {
                removeKey(sortList, overlap[i + 1][0]);
                addKey(sortList, overlap[i + 1][1]);
            }
            res[i] = sortList.isEmpty() ? 0 : sortList.lastKey();
            addKey(sortList, overlap[i][0]);
            if (i + 1 < len) {
                addKey(sortList, overlap[i + 1][0]);
                removeKey(sortList, overlap[i + 1][1]);
            }
        }
        return res;
    }

    private void addKey(Map<Integer, Integer> map, int key) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }

    private void removeKey(Map<Integer, Integer> map, int key) {
        int c = map.get(key);
        if (c == 1) {
            map.remove(key);
        } else {
            map.put(key, c - 1);
        }
    }
}

class TrieNode {
    HashMap<Character, TrieNode> next;
    int[] last;

    public TrieNode() {
        next = new HashMap<>();
        last = new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
    }

    public void addPos(int pos) {
        last[1] = last[0];
        last[0] = pos;
    }
}

Q3. Partition Array to Minimize XOR

给定一个整数数组 nums 和一个整数 k，将 nums 分成 k 个非空子数组。对于每个子数组，计算其元素的按位异或（XOR）。

返回这 k 个子数组中最大XOR值的最小可能值。

测试样例：

输入：nums = [1,2,3], k = 2

输出：1

解释：最优分割为[1]和[2, 3]。

• 第一个子数组的XOR值是1。
• 第二个子数组的XOR值是2 XOR 3 = 1。
  最终，最大XOR值为1。

解答：通过递归和动态规划计算子数组的XOR值，并分割数组以最小化最大XOR值。

class Solution {
    public int minXor(int[] nums, int k) {
        int len = nums.length;
        int[] max = new int[len], xor = new int[len];
        max[len - 1] = nums[len - 1];
        xor[len - 1] = nums[len - 1];

        // 预处理每个位置的最大值和XOR值
        for (int i = len - 2; i >= 0; --i) {
            max[i] = Math.max(max[i + 1], nums[i]);
            xor[i] = nums[i] ^ xor[i + 1];
        }

        Integer[][] mem = new Integer[nums.length][k + 1];
        return helper(nums, max, xor, 0, k, mem);
    }

    private int helper(int[] nums, int[] max, int[] xor, int pos, int k, Integer[][] mem) {
        if (k == nums.length - pos) {
            return max[pos];
        } else if (k == 1) {
            return xor[pos];
        } else if (mem[pos][k] == null) {
            int cxor = 0;
            mem[pos][k] = Integer.MAX_VALUE;

            // 尝试每种分割方式
            for (int i = pos; i < nums.length && k - 1 <= nums.length - (i + 1); ++i) {
                cxor ^= nums[i];
                mem[pos][k] = Math.min(mem[pos][k], Math.max(cxor, helper(nums, max, xor, i + 1, k - 1, mem)));
            }
        }
        return mem[pos][k];
    }
}

Q4. Maximize Spanning Tree Stability with Upgrades

给定一个整数 n，表示有 n 个节点，编号从0到 n - 1，以及一组边 edges，每条边的格式为 [ui, vi, si, musti]：

• ui 和 vi 表示一条无向边。
• si 是边的强度。
• musti 是一个整数（0或1）。如果 musti == 1，该边必须包含在生成树中，否则可以升级。

你还给定一个整数 k，表示你最多可以执行的升级次数。每次升级将一条边的强度加倍。

返回最大可能的生成树稳定性。如果无法连接所有节点，返回 -1。

测试样例：

输入：n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1

输出：2

解释：

• 边 [0, 1] 的强度 = 2 必须包含在生成树中。
• 边 [1, 2] 可以升级为 6，最大稳定性为2。

解答：

• 通过并查集（Union-Find）解决连接节点的问题。
• 优化生成树的稳定性，通过升级边来尽可能提高稳定性。

class Solution {
    private static final long mul = (long) (1e5 + 1);

    public int maxStability(int n, int[][] edges, int k) {
        DSU uf = new DSU(n);
        int min = Integer.MAX_VALUE;

        // 先处理必须包含的边
        for (int[] e : edges) {
            if (e[3] == 1) {
                min = Math.min(min, e[2]);
                if (uf.find(e[0]) == uf.find(e[1])) {
                    return -1;
                }
                uf.union(e[0], e[1]);
            }
        }

        HashMap<Long, Integer> map = new HashMap<>();

        // 处理可升级的边
        for (int[] e : edges) {
            if (e[3] == 0 && uf.find(e[0]) != uf.find(e[1])) {
                int left = Math.min(uf.find(e[0]), uf.find(e[1]));
                int right = Math.max(uf.find(e[0]), uf.find(e[1]));
                long key = left * mul + right;
                if (!map.containsKey(key)) {
                    map.put(key, e[2]);
                } else {
                    map.put(key, Math.max(map.get(key), e[2]));
                }
            }
        }

        // 优先级队列用于处理可升级的边
        PriorityQueue<Long> queue = new PriorityQueue<>((a, b) -> Integer.compare(map.get(b), map.get(a)));
        List<Integer> buffered = new ArrayList<>();
        for (long key : map.keySet()) {
            queue.add(key);
        }

        // 处理并更新生成树
        while (!queue.isEmpty()) {
            long key = queue.poll();
            int left = (int)(key / mul), right = (int) (key % mul);
            if (uf.find(left) != uf.find(right)) {
                buffered.add(map.get(key));
                uf.union(left, right);
            }
        }

        int first = uf.find(0);
        for (int i = 1; i < n; ++i) {
            if (uf.find(i) != first) {
                return -1;
            }
        }

        Collections.sort(buffered);
        for (int i = 0; i < buffered.size(); ++i) {
            if (i < k) {
                min = Math.min(min, 2 * buffered.get(i));
            } else {
                min = Math.min(min, buffered.get(i));
            }
        }
        return min;
    }
}

class DSU {
    int[] parent;

    public DSU(int N) {
        parent = new int[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) {
        parent[find(x)] = find(y);
    }
}