音平商城谁做的网站,策划方案模板,网页设计特效网站,建站宝盒购买本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个下标从 0 开始的整数数组 nums 它表示英雄的能力值。如果我们选出一部分英雄这组英雄的 力量 定义为
i0 i1 … ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。
请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大请你将结果对 109 7 取余。
示例 1
输入nums [2,1,4]
输出141
解释
第 1 组[2] 的力量为 22 * 2 8 。
第 2 组[1] 的力量为 12 * 1 1 。
第 3 组[4] 的力量为 42 * 4 64 。
第 4 组[2,1] 的力量为 22 * 1 4 。
第 5 组[2,4] 的力量为 42 * 2 32 。
第 6 组[1,4] 的力量为 42 * 1 16 。
第 7 组[2,1,4] 的力量为 42 * 1 16 。
所有英雄组的力量之和为 8 1 64 4 32 16 16 141 。示例 2
输入nums [1,1,1]
输出7
解释总共有 7 个英雄组每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。提示
1 nums.length 10^51 nums[i] 10^9 贡献法与本题类似的但不同的
907. 子数组的最小值之和1508. 子数组和排序后的区间和1856. 子数组最小乘积的最大值2104. 子数组范围和2281. 巫师的总力量和但比本题难。与 2281 同样使用单调栈获取贡献区间的还有很多题目如2818. 操作使得分最大
解法 贡献法
由于元素的顺序不影响答案先排序。
设有 a , b , c , d , e a,b,c,d,e a,b,c,d,e 五个数顺序从小到大。如果把 d d d 当成最大值
如果只选 d d d 单独一个数那么力量为 d 3 d^3 d3 。选 a a a 为最小值由于中间的 b b b 和 c c c 可选可不选一共有 2 2 2^2 22 种方案所以力量总和为 d 2 ⋅ a ⋅ 2 2 d^2\cdot a\cdot 2^2 d2⋅a⋅22 。选 b b b 为最小值由于中间的 c c c 可选可不选一共有 2 1 2^1 21 种方案所以力量总和为 d 2 ⋅ b ⋅ 2 1 d^2\cdot b\cdot 2^1 d2⋅b⋅21 。选 c c c 为最小值只有 2 0 1 2^01 201 种方案所以力量总和为 d 2 ⋅ c ⋅ 2 0 d^2\cdot c\cdot 2^0 d2⋅c⋅20 。
因此当 d d d 为最大值时 d d d 及其左侧元素对答案的贡献为 d 3 d 2 ⋅ ( a ⋅ 2 2 b ⋅ 2 1 c ⋅ 2 0 ) d^3 d^2\cdot (a\cdot 2^2 b\cdot 2^1 c\cdot 2^0) d3d2⋅(a⋅22b⋅21c⋅20) 令 s a ⋅ 2 2 b ⋅ 2 1 c ⋅ 2 0 sa\cdot 2^2 b\cdot 2^1 c\cdot 2^0 sa⋅22b⋅21c⋅20 上式为 d 3 d 2 ⋅ s d 2 ⋅ ( d s ) d^3 d^2\cdot s d^2\cdot(ds) d3d2⋅sd2⋅(ds) 继续把 e e e 当成最大值观察 s s s 如何变化也就是 a , b , c , d a,b,c,d a,b,c,d 作为最小值的贡献 a ⋅ 2 3 b ⋅ 2 2 c ⋅ 2 1 d ⋅ 2 0 2 ⋅ ( a ⋅ 2 2 b ⋅ 2 1 c ⋅ 2 0 ) d ⋅ 2 0 2 ⋅ s d \begin{aligned} \ a\cdot 2^3 b\cdot 2^2 c\cdot 2^1 d\cdot 2^0\\ \ 2\cdot(a\cdot 2^2 b\cdot 2^1 c\cdot 2^0) d\cdot 2^0\\ \ 2\cdot s d\\ \end{aligned} a⋅23b⋅22c⋅21d⋅20 2⋅(a⋅22b⋅21c⋅20)d⋅20 2⋅sd 这意味着我们不需要枚举最小值只需要枚举最大值就可以把 s s s 递推计算出来。
class Solution {
public:int sumOfPower(vectorint nums) {sort(nums.begin(), nums.end());const int mod 1e9 7;int ans 0, s 0;for (long long x : nums) { // x作为最大值ans (ans x * x % mod * (x s)) % mod; // 中间模1次防止溢出s (s * 2 x) % mod; // 递推计算下个s}return ans;}
};复杂度分析
时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 其中 n n n 为 nums \textit{nums} nums 的长度。瓶颈在排序上。空间复杂度 O ( 1 ) O(1) O(1) 。忽略排序的栈空间仅用到若干额外变量。 思考题把「子序列」改成「子数组」要怎么做
