leetcode：891. 子序列宽度之和【排序 + 贡献法】

题目截图

题目分析

• 最大值和最小值求法一样
• 有2^n个子序列选法
• ai有多少次能作为最大出现在子序列中
• 排序后，为b1,b2…bn
• b1作为max出现的非空子序列有1次
• b2作为max出现的非空子序列有2次
• b3作为max出现的非空子序列有4次
• 最小值同理
• 相减即可

python

class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        # 排序 + 贡献
        MOD = 10 ** 9 + 7
        n = len(nums)
        # max_sum
        max_sum = 0
        nums.sort()
        for i, v in enumerate(nums):
            max_sum += v * pow(2, i, MOD)
            max_sum %= MOD
        # min_sum
        min_sum = 0
        for i, v in enumerate(nums[::-1]):
            min_sum += v * pow(2, i, MOD)
            min_sum %= MOD
        # ans
        # print(max_sum, min_sum)
        return (max_sum - min_sum) % MOD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

java

class Solution {
    private static int MOD = (int) 1e9 + 7;

    public int sumSubseqWidths(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        // 预处理幂
        int[] pow = new int[n];
        pow[0] = 1;
        for (int i = 1; i < n; i++) {
            pow[i] = pow[i - 1] * 2 % MOD;
        }
        // max_sum
        long max_sum = 0L;
        for (int i = 0; i < n; i++) {
            max_sum += (long)nums[i] * pow[i] % MOD;
        }
        // min_sum
        long min_sum = 0L;
        for (int i = 0; i< n; i++) {
            min_sum += (long)nums[n - 1 - i] * pow[i] % MOD;
        }
        // ans
        return (int)((max_sum - min_sum) % MOD + MOD) % MOD;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结

• java注意int和long的转换即可
• java需要进行幂的预处理