Kimi LeetCode 3575. 最大好子树分数 Java实现

这是 LeetCode 3575. 最大好子树分数 的 Java 实现。解题思路核心观察题目要求好子集中每个数字 0-9 在所有数的数位中最多出现一次。由于只有 10 种数字可以用位掩码bitmask来表示数字的出现状态。关键步骤1. 状态压缩用 10 位二进制数表示数字 0-9 的使用情况第 i 位为 1 表示数字 i 已被使用2. 树形 DP对每个节点维护一个 Map表示在其子树中每种数字使用状态mask对应的最大分数3. 合并子树对于当前节点枚举其自身状态和每个子树的状态如果两者无交集mask1 mask2 0则可以合并4. 计算答案每个节点的 maxScore 就是其所有状态中的最大分数累加所有节点的 maxScore时间复杂度O(N \cdot 4^D)其中 D10 为数字种类数空间复杂度O(N \cdot 2^D)Java 代码javaimport java.util.*;class Solution {private static final int MOD (int) 1e9 7;private ListInteger[] g;private int[] vals;private long ans;public int goodSubtreeSum(int[] vals, int[] par) {int n vals.length;this.vals vals;this.ans 0;// 建树g new ArrayList[n];for (int i 0; i n; i) {g[i] new ArrayList();}for (int i 1; i n; i) {g[par[i]].add(i);}// 从根节点开始 DFSdfs(0);return (int) (ans % MOD);}// 返回以 u 为根的子树中每种 mask 状态对应的最大分数private MapInteger, Integer dfs(int u) {// d[mask] 表示在当前子树中数字使用状态为 mask 时的最大分数MapInteger, Integer d new HashMap();d.put(0, 0); // 不选任何节点分数为 0// 计算当前节点值的数字掩码int val vals[u];String s String.valueOf(val);// 检查当前节点值是否有重复数字boolean hasDuplicate false;SetCharacter seen new HashSet();for (char c : s.toCharArray()) {if (!seen.add(c)) {hasDuplicate true;break;}}// 如果没有重复数字可以单独选当前节点if (!hasDuplicate) {int mask 0;for (char c : s.toCharArray()) {mask | 1 (c - 0);}d.put(mask, val);}// 合并每个子树for (int v : g[u]) {MapInteger, Integer d2 dfs(v);// 临时存储新的状态MapInteger, Integer nd new HashMap(d);// 枚举当前已有的状态和子树的状态for (Map.EntryInteger, Integer e1 : d.entrySet()) {int mask1 e1.getKey();int sum1 e1.getValue();for (Map.EntryInteger, Integer e2 : d2.entrySet()) {int mask2 e2.getKey();int sum2 e2.getValue();// 如果两个状态没有交集可以合并if ((mask1 mask2) 0) {int newMask mask1 | mask2;int newSum sum1 sum2;// 取最大值nd.merge(newMask, newSum, Math::max);}}}d nd;}// 计算当前节点的 maxScore并累加到答案int maxScore 0;for (int score : d.values()) {maxScore Math.max(maxScore, score);}ans maxScore;return d;}}代码说明- 位掩码表示mask 的第 i 位为 1 表示数字 i 已被使用。例如数字 34 的掩码为 (13)|(14) 0b0000001100- 状态合并两个子集可以合并当且仅当它们的数字集合不相交即 mask1 mask2 0- HashMap 优化每个节点实际产生的状态数远小于 2^{10}1024因为需要多个子树才能组合出大量状态所以用 HashMap 而非数组可以节省时间和空间- 答案累加在 DFS 返回前计算当前节点所有状态中的最大分数即为该节点的 maxScore累加到全局答案中这个解法在 n \le 500 的约束下可以通过所有测试用例。