目錄
2681. 英雄的力量
題目描述：
實(shí)現(xiàn)代碼與解析：
數(shù)學(xué)規(guī)律
原理思路：
2681. 英雄的力量
題目描述：
????????給你一個(gè)下標(biāo)從?0?開始的整數(shù)數(shù)組?nums?，它表示英雄的能力值。如果我們選出一部分英雄，這組英雄的?力量?定義為：
-
i0?，i1?，...?ik?表示這組英雄在數(shù)組中的下標(biāo)。那么這組英雄的力量為?max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik])?。
請(qǐng)你返回所有可能的?非空?英雄組的?力量?之和。由于答案可能非常大，請(qǐng)你將結(jié)果對(duì)?109 + 7?取余。?
示例 1：
輸入：nums = [2,1,4]
輸出：141
解釋：
第 1?組：[2] 的力量為 2^2?* 2 = 8 。
第 2?組：[1] 的力量為 1^2 * 1 = 1 。
第 3?組：[4] 的力量為 4^2 * 4 = 64 。
第 4?組：[2,1] 的力量為 2^2 * 1 = 4 。
第 5 組：[2,4] 的力量為 4^2 * 2 = 32 。
第 6?組：[1,4] 的力量為 4^2 * 1 = 16 。
第? ??????7?組：[2,1,4] 的力量為 4^2 * 1 = 16 。
所有英雄組的力量之和為 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。
示例 ：
輸入：nums = [1,1,1]
輸出：7
解釋：總共有 7 個(gè)英雄組，每一組的力量都是 1 。所以所有英雄組的力量之和為 7 。
實(shí)現(xiàn)代碼與解析：
數(shù)學(xué)規(guī)律
class Solution {
public:
int mod = 1e9 + 7;
int sumOfPower(vector<int>& nums) {
sort(nums.begin(), nums.end());
long long res = 0, sum = 0;
for (int i = 0; i < nums.size(); i++)
{
res = (res + (long long)nums[i] * (long long)nums[i] % mod * (nums[i] + sum)) % mod;
sum = (sum * 2 + nums[i]) % mod;
}
return res;
}
};原理思路：
? ? ? ? 分析題目，可以發(fā)現(xiàn)，其實(shí)英雄能力值之和每個(gè)子集的最大值和最小值有關(guān)，所有我們先sort排序，然后遍歷，讓其作為最大值，這是固定的，所以只要找出以 nums[ i ] 為最大值結(jié)尾的子集的最小值的和與最大值的平方相乘就得出了此種情況的英雄力量的和，最后全加起來，就得到了答案。
? ? ? ? 所以關(guān)鍵的核心就時(shí)如何求出以 nums[ i ] 為最大值結(jié)尾的子集的最小值的和。
比如排序后{1， 2， 3，?4}， 當(dāng)遍歷到4時(shí)，以其為最大值的子集有多少種？
? ? ? ? 當(dāng)選擇1為最小值時(shí)，2可選可不選，3可選可不選，這樣就是2 * 2 = 4 個(gè)，4 * （4 * 4）* 1就為一組力量值?？梢园l(fā)現(xiàn)一組力量值是和元素的個(gè)數(shù)和最小值有關(guān)的。
? ? ? ? 那么我們可以總結(jié)出遞推式，之間算出一個(gè)最大值平方需要乘的總和為：sum(nums[i]?* 2 ^ 最小值與最大值中間的數(shù)字個(gè)數(shù))，i 從 0 到最大值下標(biāo)。
????????這樣就可以發(fā)現(xiàn)子集最小值總和明顯是可以根據(jù)前一個(gè)的子集最小值總和算出來的。規(guī)律如下：文章來源：http://www.zghlxwxcb.cn/news/detail-639572.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-639572.html
到了這里，關(guān)于Leetcode每日一題：2681. 英雄的力量（2023.8.1 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
