2681.英雄的力量

链接：2681.英雄的力量
难度：Hard
标签：数组、数学、动态规划、前缀和、排序
简介：请你返回所有可能的 非空 英雄组的 力量 之和。

题解 1 - cpp

• 编辑时间：2023-08-01
• 执行用时：88ms
• 内存消耗：88.63MB
• 编程语言：cpp
• 解法介绍：排序后遍历统计。

class Solution {
public:
    typedef long long ll;
    int sumOfPower(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // min (...cnt) max， sum统计min为最小值的情况个数，pow(2, cnt)
        ll res = 0, MOD = 1e9 + 7, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            ll num = nums[i], num2 = num * num % MOD;
            // 当子序列内只有num时的情况
            res += num2 * num % MOD;
            // 前面最小值的和 乘以 最大值的平方
            res += sum * num2 % MOD;
            // 重新累加最小值的和
            sum = ((sum * 2 % MOD) + num) % MOD;
        }
        return res % MOD;
    }
};

题解 2 - python

• 编辑时间：2023-08-01
• 执行用时：168ms
• 内存消耗：25.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        nums.sort()
        res = sum = 0
        MOD = 1000000000 + 7
        for i in range(len(nums)):
            num = nums[i]
            num2 = num * num % MOD
            res += num2 * num % MOD + sum * num2 % MOD
            sum = (sum * 2 % MOD + num) % MOD
        return int(res % MOD)

题解 3 - rust

• 编辑时间：2023-08-01
• 执行用时：24ms
• 内存消耗：3.37MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn sum_of_power(nums: Vec<i32>) -> i32 {
        let mut nums: Vec<i64> = nums.into_iter().map(|v| v as i64).collect();
        nums.sort();
        let mut res = 0i64;
        let mut sum = 0i64;
        const MOD: i64 = 1000000000 + 7;
        for i in 0..nums.len() {
            let num = nums[i];
            let num2 = num * num % MOD;
            res += num2 * num % MOD + sum * num2 % MOD;
            sum = (sum * 2 % MOD + num) % MOD
        }
        (res % MOD) as i32
    }
}