DeepSeek LeetCode LCP 16. 游乐园的游览计划 Java实现

这道题的核心是在无向图中找到两个共享顶点A的三角形A-B-C-A 和 A-B-C-A使得它们覆盖的不同顶点权值之和最大。由于数据规模较大顶点和边最多10000暴力枚举所有三角形会超时通常采用根号分治来优化。Java实现代码javaimport java.util.*;class Solution {public int maxWeight(int[][] edges, int[] value) {int n value.length;// 1. 建图邻接表用于遍历 邻接矩阵用于快速判断边是否存在ListInteger[] graph new List[n];boolean[][] hasEdge new boolean[n][n];for (int i 0; i n; i) graph[i] new ArrayList();for (int[] e : edges) {int u e[0], v e[1];graph[u].add(v);graph[v].add(u);hasEdge[u][v] hasEdge[v][u] true;}// 2. 根号分治度数 limit 的为“大点”否则为“小点”int limit (int) Math.sqrt(n);boolean[] isBig new boolean[n];for (int i 0; i n; i) {if (graph[i].size() limit) isBig[i] true;}// 存储每个顶点参与的三角形只存顶点三元组和权值和Listint[][] triByVertex new List[n];for (int i 0; i n; i) triByVertex[i] new ArrayList();// 3. 枚举所有三角形// 3.1 枚举小点 v枚举其两个邻居 a, b检查 a,b 是否相连for (int v 0; v n; v) {if (isBig[v]) continue;ListInteger adj graph[v];for (int i 0; i adj.size(); i) {for (int j i 1; j adj.size(); j) {int a adj.get(i), b adj.get(j);if (hasEdge[a][b]) {int sum value[v] value[a] value[b];triByVertex[v].add(new int[]{v, a, b, sum});triByVertex[a].add(new int[]{v, a, b, sum});triByVertex[b].add(new int[]{v, a, b, sum});}}}}// 3.2 枚举大点枚举任意三个大点检查是否两两相连ListInteger bigNodes new ArrayList();for (int i 0; i n; i) if (isBig[i]) bigNodes.add(i);for (int i 0; i bigNodes.size(); i) {for (int j i 1; j bigNodes.size(); j) {for (int k j 1; k bigNodes.size(); k) {int a bigNodes.get(i), b bigNodes.get(j), c bigNodes.get(k);if (hasEdge[a][b] hasEdge[a][c] hasEdge[b][c]) {int sum value[a] value[b] value[c];triByVertex[a].add(new int[]{a, b, c, sum});triByVertex[b].add(new int[]{a, b, c, sum});triByVertex[c].add(new int[]{a, b, c, sum});}}}}// 4. 计算答案枚举公共顶点 A找两个最优三角形组合int ans 0;for (int a 0; a n; a) {Listint[] tris triByVertex[a];if (tris.size() 2) {// 只有一个三角形时只能游玩一个答案就是该三角形的权值和if (tris.size() 1) ans Math.max(ans, tris.get(0)[3]);continue;}// 按权值和降序排序只需考虑前几个tris.sort((x, y) - y[3] - x[3]);// 尝试前 min(5, size) 个组合通常足够for (int i 0; i Math.min(5, tris.size()); i) {for (int j i 1; j Math.min(5, tris.size()); j) {int[] t1 tris.get(i), t2 tris.get(j);SetInteger set new HashSet();set.add(t1[0]); set.add(t1[1]); set.add(t1[2]);set.add(t2[0]); set.add(t2[1]); set.add(t2[2]);int sum 0;for (int node : set) sum value[node];ans Math.max(ans, sum);}}}return ans;}}复杂度分析· 时间复杂度O(N√N)在 N10000 的规模下可接受。· 空间复杂度O(N M)用于存储图、邻接矩阵及三角形信息。核心思路1. 问题转化将游玩路径抽象为两个共享顶点 A 的三角形。2. 高效找三角形利用“根号分治”平衡大小顶点的枚举开销避免 O(N^3) 的暴力。3. 枚举组合对每个顶点 A枚举其参与的所有三角形取两个去重后权值和最大的组合。4. 剪枝优化只需考虑每个顶点下权值和最大的前几个三角形进行组合无需全量枚举。