Kimi LeetCode 2836. 在传球游戏中最大化函数值 Java实现

这是 LeetCode 2836 的 Java 实现核心思路是 倍增法Binary Lifting。核心思路1. 问题建模receiver 构成一个出度为 1 的功能图每个节点指向一个节点要求从某个起点出发走 k 步最大化路径上所有节点值之和包含起点。2. 关键约束k 最大可达 10^10无法暴力模拟必须用 倍增法 在 O(log k) 时间内跳跃。3. 倍增预处理- next[i][j]从节点 i 出发走 2^j 步到达的节点- sum[i][j]从节点 i 出发走 2^j 步经过的中间节点值之和不含起点4. 转移方程- next[i][j] next[next[i][j-1]][j-1]- sum[i][j] sum[i][j-1] sum[next[i][j-1]][j-1]5. 答案计算对每个起点将 k 拆分为二进制位逐位跳跃累加。Java 实现javaclass Solution {public long getMaxFunctionValue(ListInteger receiver, long k) {int n receiver.size();// k 的二进制位数即倍增层数int m 64 - Long.numberOfLeadingZeros(k);// next[i][j] 从节点 i 出发走 2^j 步到达的节点int[][] next new int[n][m];// sum[i][j] 从节点 i 出发走 2^j 步路径上所有中间节点值之和不含起点 ilong[][] sum new long[n][m];// 初始化2^0 1 步for (int i 0; i n; i) {next[i][0] receiver.get(i);sum[i][0] receiver.get(i); // 走1步只到达 receiver[i]}// 倍增预处理for (int j 1; j m; j) {for (int i 0; i n; i) {int mid next[i][j - 1];next[i][j] next[mid][j - 1];sum[i][j] sum[i][j - 1] sum[mid][j - 1];}}long ans 0;// 枚举每个起点for (int start 0; start n; start) {int curr start;long total start; // 包含起点自身的值// 将 k 拆分为二进制逐位跳跃for (int j 0; j m; j) {if (((k j) 1) 1) {total sum[curr][j];curr next[curr][j];}}ans Math.max(ans, total);}return ans;}}复杂度分析指标 复杂度时间 O(n × log k)预处理 O(n log k)枚举起点 O(n log k)空间 O(n × log k)两个二维数组示例说明示例 1receiver [2,0,1], k 4- k 4 100₂需要 m 3 层- 从起点 2 出发- 初始 total 2- k 的第 2 位为 1走 2^2 4 步- sum[2][2] 路径 2→1→0→2→1 的中间节点和 1021 4- total 2 4 6最终到达节点 1- 答案 f(2) 6 ✓示例 2receiver [1,1,1,2,3], k 3- k 3 11₂- 从起点 4 出发- 初始 total 4- 第 0 位为 1走 1 步sum[4][0] 3curr 3total 7- 第 1 位为 1走 2 步sum[3][1] 21 3curr 1total 10- 答案 f(4) 10 ✓关键点- sum 的定义sum[i][j] 存储的是走 2^j 步过程中经过的所有节点值之和不含起点这样最终答案就是 起点值 各段 sum 之和。