节点序列的最大得分
难度:
标签:
题目描述
给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。
给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。
一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：
- 序列中每 相邻 节点之间有边相连。
- 序列中没有节点出现超过一次。
节点序列的分数定义为序列中节点分数之 和 。
请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。
示例 1：
输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：24 解释：上图为输入的图，节点序列为 [0,1,2,3] 。 节点序列的分数为 5 + 2 + 9 + 8 = 24 。 观察可知，没有其他节点序列得分和超过 24 。 注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。 序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。
示例 2：
输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]] 输出：-1 解释：上图为输入的图。 没有长度为 4 的合法序列，所以我们返回 -1 。
提示：
n == scores.length4 <= n <= 5 * 1041 <= scores[i] <= 1080 <= edges.length <= 5 * 104edges[i].length == 20 <= ai, bi <= n - 1ai != bi- 不会有重边。
代码结果
运行时间: 283 ms, 内存: 34.8 MB
/*
* 思路：
* 1. 同样使用邻接表表示图。
* 2. 使用Java Stream API进行遍历并计算分数。
* 3. 用Collectors和Optional处理最大值的获取。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int maximumScore(int[] scores, int[][] edges) {
int n = scores.length;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
return graph.stream().flatMapToInt(u -> graph.get(u).stream().flatMapToInt(v -> graph.get(v).stream()
.flatMapToInt(x -> graph.get(x).stream().filter(y -> y != v && y != u)
.map(y -> scores[u] + scores[v] + scores[x] + scores[y])))).max().orElse(-1);
}
}
解释
方法:
该题解的思路如下：
1. 为每个节点维护一个长度为3的数组，存储与该节点相连的分数最高的3个节点。
2. 遍历所有边，更新每个节点的相连节点数组。
3. 再次遍历所有边，对于每条边(a,b)，尝试以a和b为中心节点构造长度为4的节点序列，选取a和b各自相连的最高分节点作为端点，计算序列得分。
4. 在所有可能的节点序列中，选取得分最高的作为最终答案。
时间复杂度:
O(m)
空间复杂度:
O(n)
代码细节讲解
🦆
在构建长度为3的数组来存储每个节点相连的分数最高的三个节点时，如果一个节点的连接节点少于三个，该如何处理？
▷🦆
在题解中提到，遍历所有边来更新相连节点数组时，仅考虑了分数较高的节点。请问如果存在多个节点具有相同的分数，该如何决定其在数组中的位置？
▷🦆
题解中提到使用贪心策略选择每个节点相连的最高分节点作为端点，这种策略是否一定能保证找到最大得分的四节点序列？
▷🦆
在计算得分时，如果节点a和节点b的最高分节点相同，题解中的方法会如何避免重复使用同一个节点？
▷