DeepSeek LeetCode 2681.英雄的力量 JavaScript实现

以下是 LeetCode 2681“英雄的力量”的 JavaScript 实现。解题思路与 Java 版本一致1. 排序将数组升序排序便于确定最小值和最大值2. 数学优化对于每个元素作为最大值时计算它对答案的贡献3. 前缀和维护所有可能的最小值之和避免重复计算JavaScript 代码javascriptvar sumOfPower function(nums) {const MOD 1000000007;nums.sort((a, b) a - b);let ans 0;let prefixSum 0; // 维护 Σ nums[j] * 2^jfor (let i 0; i nums.length; i) {const val nums[i];// 当前元素作为最大值的贡献val² * (所有可能的最小值之和)const contribution (val * val) % MOD;const sum (prefixSum val) % MOD;ans (ans contribution * sum) % MOD;// 更新前缀和当前元素会成为后续元素的最小值候选prefixSum (prefixSum * 2 val) % MOD;}return ans;};详细版本便于理解javascriptvar sumOfPower function(nums) {const MOD BigInt(1000000007);nums.sort((a, b) a - b);let ans 0n;let prefixSum 0n; // Σ nums[j] * 2^jfor (let i 0; i nums.length; i) {const val BigInt(nums[i]);// 当前元素作为最大值的贡献const maxPower (val * val) % MOD;const minSum (prefixSum val) % MOD;ans (ans maxPower * minSum) % MOD;// 更新前缀和用于下一轮prefixSum (prefixSum * 2n val) % MOD;}return Number(ans);};暴力验证版本仅用于理解javascript// 暴力解法O(2^n)仅用于验证小数据var sumOfPowerBrutal function(nums) {const n nums.length;let ans 0;// 枚举所有非空子集for (let mask 1; mask (1 n); mask) {let minVal Infinity;let maxVal -Infinity;for (let i 0; i n; i) {if (mask (1 i)) {minVal Math.min(minVal, nums[i]);maxVal Math.max(maxVal, nums[i]);}}ans (ans minVal * maxVal * maxVal) % 1000000007;}return ans;};算法演示javascript// 示例nums [2, 1, 4]// 排序后[1, 2, 4]// 手动计算过程// 排序数组: [1, 2, 4]//// i0, val1:// prefixSum 0// minSum 0 1 1// contribution 1² * 1 1// ans 1// prefixSum 0*2 1 1//// i1, val2:// minSum 1 2 3// contribution 2² * 3 4 * 3 12// ans 1 12 13// prefixSum 1*2 2 4//// i2, val4:// minSum 4 4 8// contribution 4² * 8 16 * 8 128// ans 13 128 141console.log(sumOfPower([2, 1, 4])); // 141使用 BigInt 避免溢出的版本推荐javascriptvar sumOfPower function(nums) {const MOD 1000000007n;nums.sort((a, b) a - b);let ans 0n;let prefixSum 0n;for (let i 0; i nums.length; i) {const val BigInt(nums[i]);// 当前元素作为最大值的贡献const maxPower (val * val) % MOD;const minSum (prefixSum val) % MOD;ans (ans maxPower * minSum) % MOD;// 更新前缀和每个之前的最小值都有选或不选两种可能prefixSum (prefixSum * 2n val) % MOD;}return Number(ans);};数学原理解释对于排序后的数组 a[0] ≤ a[1] ≤ ... ≤ a[n-1]1. 固定最大值 a[i]· 所有以 a[i] 为最大值的子集最小值可以是 a[0], a[1], ..., a[i]· 对于最小值 a[j] (0 ≤ j ≤ i)中间元素 (j1 到 i-1) 可以任意选或不选· 子集个数 2^(i-j-1)当 ji 时个数为 12. 贡献公式贡献 Σ_{j0}^{i} a[j] * a[i]² * 2^(i-j-1) a[i]² * Σ_{j0}^{i} a[j] * 2^(i-j-1)3. 前缀和优化令 S[i] Σ_{j0}^{i} a[j] * 2^(i-j)则 S[i] 2 * S[i-1] a[i]其中 S[-1] 04. 贡献简化贡献 a[i]² * (S[i-1] a[i])复杂度分析· 时间复杂度O(n log n)主要来自排序· 空间复杂度O(1)只使用了常数个变量运行示例javascript// 测试用例console.log(sumOfPower([2, 1, 4])); // 141console.log(sumOfPower([1, 1, 1])); // 6console.log(sumOfPower([3])); // 27console.log(sumOfPower([1, 2, 3, 4])); // 需要验证这个解法利用了数学推导和前缀和技巧将指数级复杂度优化为线性加上排序的 O(n log n)。