Kimi LeetCode 3547. 图中边值的最大和 Java实现

以下是 LeetCode 3547. 图中边值的最大和 的 Java 实现。解题思路由于每个节点最多与其他两个节点相连整个图由若干链和环组成。核心贪心策略1. 先处理环再处理链——环的每节点度数为 2能贡献更多边权链至少有一个端点度数为 1。2. 链按长度降序处理——长链能贡献更多边优先分配大数。3. 填数策略——将剩余的最大数放在连通分量的中间次大的数交替向两边扩展使得大数尽量相邻类似排序不等式。时间复杂度 O(n \log n)空间复杂度 O(n)。---Java 代码javaimport java.util.*;class Solution {public long maxScore(int n, int[][] edges) {long ans 0;// 建图ListInteger[] graph new List[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] edge : edges) {int u edge[0], v edge[1];graph[u].add(v);graph[v].add(u);}boolean[] seen new boolean[n];ListInteger cycleSizes new ArrayList(); // 所有节点度数为2的连通分量环ListInteger pathSizes new ArrayList(); // 其余连通分量链// 遍历每个连通分量for (int i 0; i n; i) {if (seen[i]) continue;ListInteger component getComponent(graph, i, seen);// 判断是否为环所有节点度数均为2boolean allDegree2 true;for (int u : component) {if (graph[u].size() ! 2) {allDegree2 false;break;}}if (allDegree2) {cycleSizes.add(component.size());} else if (component.size() 1) {pathSizes.add(component.size());}// 孤立点size1不贡献边权无需处理}// 先处理环从剩余的最大数中分配for (int cycleSize : cycleSizes) {ans calculateScore(n - cycleSize 1, n, true);n - cycleSize;}// 链按长度从大到小排序优先处理长链Collections.sort(pathSizes, Collections.reverseOrder());for (int pathSize : pathSizes) {ans calculateScore(n - pathSize 1, n, false);n - pathSize;}return ans;}// BFS/DFS 获取连通分量中的所有节点private ListInteger getComponent(ListInteger[] graph, int start, boolean[] seen) {ListInteger component new ArrayList();QueueInteger queue new LinkedList();queue.offer(start);seen[start] true;component.add(start);while (!queue.isEmpty()) {int u queue.poll();for (int v : graph[u]) {if (!seen[v]) {seen[v] true;queue.offer(v);component.add(v);}}}return component;}/*** 计算将 [left, right] 范围内的数填入一个连通分量的最大边权和** 填数策略用双端队列模拟初始放入两个最大值 right* 从 right-1 递减到 left每次取出队列前端与当前值相乘再将当前值放入队尾* 这样大数会集中在中间次大数交替向两边扩展** param left 可用数的最小值* param right 可用数的最大值* param isCycle 是否为环环需要额外加上首尾相连的一条边* return 该连通分量的最大边权和*/private long calculateScore(int left, int right, boolean isCycle) {DequeLong deque new ArrayDeque();deque.offerLast((long) right);deque.offerLast((long) right);long score 0;for (int value right - 1; value left; value--) {long windowValue deque.pollFirst();score windowValue * value;deque.offerLast((long) value);}// 如果是环首尾两个节点也相邻额外加上它们的乘积if (isCycle) {score deque.peekFirst() * deque.peekLast();}return score;}}---关键说明要点 说明连通分量分类 所有节点度数均为 2 → 环否则为链含孤立点处理顺序 环优先于链因为环的每个节点都有两条边大数在环中能产生更多乘积链按长度降序长链优先拿大数calculateScore 双端队列模拟中间放大数向两边递减的排列。例如 [left..right][7,8,9,10,11]排列为 9-11-10-8-7相邻乘积和最大环额外处理 环首尾相连所以 deque.peekFirst() * deque.peekLast() 是最后一条边的贡献 注意这道题在赛后被社区发现部分测试数据存在争议官方答案可能不是最优但上述贪心策略是标准竞赛解法。