leetcode
leetcode 2301 ~ 2350
英雄的力量

英雄的力量

难度:

标签:

题目描述

You are given a 0-indexed integer array nums representing the strength of some heroes. The power of a group of heroes is defined as follows:

  • Let i0, i1, ... ,ik be the indices of the heroes in a group. Then, the power of this group is max(nums[i0], nums[i1], ... ,nums[ik])2 * min(nums[i0], nums[i1], ... ,nums[ik]).

Return the sum of the power of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [2,1,4]
Output: 141
Explanation: 
1st group: [2] has power = 22 * 2 = 8.
2nd group: [1] has power = 12 * 1 = 1. 
3rd group: [4] has power = 42 * 4 = 64. 
4th group: [2,1] has power = 22 * 1 = 4. 
5th group: [2,4] has power = 42 * 2 = 32. 
6th group: [1,4] has power = 42 * 1 = 16. 
​​​​​​​7th group: [2,1,4] has power = 42​​​​​​​ * 1 = 16. 
The sum of powers of all groups is 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141.

Example 2:

Input: nums = [1,1,1]
Output: 7
Explanation: A total of 7 groups are possible, and the power of each group will be 1. Therefore, the sum of the powers of all groups is 7.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

代码结果

运行时间: 100 ms, 内存: 26.2 MB

/*
 * 题目思路：
 * 1. 使用Java Stream流来处理数组。
 * 2. 对每个子集计算最大最小值，然后计算英雄组的力量。
 * 3. 将所有的力量相加并取模10^9 + 7。
 */

import java.util.*;
import java.util.stream.*;

public class HeroPowerStream {
    private static final int MOD = 1000000007;

    public int sumOfPowers(int[] nums) {
        int n = nums.length;
        return IntStream.range(1, 1 << n)
                .map(i -> {
                    int max = IntStream.range(0, n)
                            .filter(j -> (i & (1 << j)) != 0)
                            .map(j -> nums[j])
                            .max()
                            .orElse(Integer.MIN_VALUE);
                    int min = IntStream.range(0, n)
                            .filter(j -> (i & (1 << j)) != 0)
                            .map(j -> nums[j])
                            .min()
                            .orElse(Integer.MAX_VALUE);
                    return (int) (((long) max * max % MOD) * min % MOD);
                })
                .reduce(0, (a, b) -> (a + b) % MOD);
    }

    public static void main(String[] args) {
        HeroPowerStream hp = new HeroPowerStream();
        int[] nums = {2, 1, 4};
        System.out.println(hp.sumOfPowers(nums)); // 输出141
    }
}

解释

方法:

本题解首先对数组进行排序，确保数组元素按升序排列。排序之后，数组中的每个元素x在某个位置i时，它在前i个元素中是最大的。因此，对于数组中的每个元素x，我们可以计算以x作为最大值的所有子集的力量和，因为x左侧的所有元素都不超过x。使用变量s来累加之前所有元素的和（考虑了每个元素出现的次数），这样可以快速计算出包含x的所有子集的最小值之和。对于每个元素x，其贡献的力量可以表示为x^2 * (x + s)，其中s是x左侧所有元素的和，每次迭代时更新s为s*2 + x。这种方法避免了直接枚举所有子集，通过数学推导简化了计算过程。

时间复杂度:

O(n log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中，为什么要对原数组进行排序？这样做有什么特别的好处？
▷
排序的主要目的是为了确保当遍历到数组中的某个元素x时，它是当前遍历过的所有元素中的最大值。这样，可以保证在计算子集的最小值之和时，如果子集包含x，那么x就是该子集的最小值。这种方法避免了复杂的比较操作，并使得计算每个元素x作为子集最小值的情况变得直接且清晰。
🦆
该算法中的变量`s`代表什么意义？如何理解`s*2 + x`这一更新过程？
▷
在该算法中，变量`s`表示在当前元素x之前的所有元素的和。随着数组的遍历，每一个新元素都会存在于新的子集中，而之前的每个元素会在新的子集中出现两倍（即原有的子集加上新元素形成的新子集）。因此，更新过程`s*2 + x`意味着将之前所有元素的总和翻倍（考虑到新的子集的形成），然后加上当前元素x本身，以此来更新s的值，反映出所有包含当前元素x及其之前元素的子集的元素总和。
🦆
在计算`ans = (ans + x*x*(x+s)) % MOD`时，`x*x*(x+s)`表达式具体是如何推导出来的，能否详细解释一下其背后的数学原理？
▷
表达式`x*x*(x+s)`是基于以下数学原理推导出来的：对于数组中的某个元素x，在x之前的任何元素都不会超过x，因此如果包含x的子集选择x作为最小值，那么这个子集的力量就是x乘以该子集的元素总和。这里，x+s表示包含x的所有可能子集的元素总和（s是之前元素的总和，x是当前元素）。因此，x乘以(x+s)就得到了包含x的所有子集的力量总和。再乘以x是因为每个子集的力量是它的最小元素乘以子集的总和。
🦆
如何保证在遍历排序后的数组时，每个元素`x`作为最大值的所有子集的最小值之和能够被正确计算？
▷
通过排序，我们确保了每次处理元素x时，它是到目前为止遇到的最大元素。由于排序保证了x之前的任何元素都不大于x，因此在考虑包含x的所有可能子集时，x将是这些子集中的最小值。这样，我们就可以简单地通过累积之前元素的总和并用这些总和来计算包含当前元素的所有子集的力量值，从而确保计算的准确性和高效性。

相关问题

使二叉树所有路径值相等的最小代价半有序排列