LeetCode 题解工作台
节点序列的最大得分
给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。 给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [a i , b i ] ，表示节点 a i 和 b i 之…
4
题型
2
代码语言
3
相关题
当前训练重点
困难 · 图
答案摘要
枚举中间边 $(a, b)$，假设与 相邻的点为 ，与 相邻的点为 。对于相邻点，取分数最大的三个点进行枚举。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
给你一个 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- 不会有重边。
解题思路
方法一：枚举中间边
枚举中间边 ，假设与 相邻的点为 ，与 相邻的点为 。对于相邻点，取分数最大的三个点进行枚举。
class Solution:
def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
for k in g.keys():
g[k] = nlargest(3, g[k], key=lambda x: scores[x])
ans = -1
for a, b in edges:
for c in g[a]:
for d in g[b]:
if b != c != d != a:
t = scores[a] + scores[b] + scores[c] + scores[d]
ans = max(ans, t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate identify and efficiently explore valid edge triplets?
- question_mark
Does the candidate consider the edge constraints and node connectivity in each sequence?
- question_mark
How well does the candidate optimize the solution for large inputs, considering the constraints?
常见陷阱
外企场景- error
Failing to properly account for edge connections when checking for valid node sequences.
- error
Not optimizing the search space for large graphs, leading to excessive computational complexity.
- error
Misunderstanding the requirement of a sequence length of exactly 4 nodes, leading to incorrect solutions.
进阶变体
外企场景- arrow_right_alt
Consider variations where the sequence length is changed to 3 or 5 nodes.
- arrow_right_alt
Extend the problem to include weighted edges and explore how this changes the sequence scoring.
- arrow_right_alt
Implement a solution for sequences with dynamic edge connectivity instead of static edges.