当前位置: 首页 > news >正文

LeetCode 2681. Power of Heroes【排序,数学,贡献法】2060

本文属于「征服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^5
  • 1 <= 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 当成最大值:

  1. 如果只选 d d d 单独一个数,那么力量为 d 3 d^3 d3
  2. 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 d2a22
  3. b b b 为最小值,由于中间的 c c c 可选可不选,一共有 2 1 2^1 21 种方案,所以力量总和为 d 2 ⋅ b ⋅ 2 1 d^2\cdot b\cdot 2^1 d2b21
  4. c c c 为最小值,只有 2 0 = 1 2^0=1 20=1 种方案,所以力量总和为 d 2 ⋅ c ⋅ 2 0 d^2\cdot c\cdot 2^0 d2c20

因此,当 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) d3+d2(a22+b21+c20)
s = a ⋅ 2 2 + b ⋅ 2 1 + c ⋅ 2 0 s=a\cdot 2^2 + b\cdot 2^1 + c\cdot 2^0 s=a22+b21+c20 ,上式为
d 3 + d 2 ⋅ s = d 2 ⋅ ( d + s ) d^3 + d^2\cdot s = d^2\cdot(d+s) d3+d2s=d2(d+s)
继续,把 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} == a23+b22+c21+d20 2(a22+b21+c20)+d20 2s+d
这意味着,我们不需要枚举最小值,只需要枚举最大值,就可以把 s s s 递推计算出来。

class Solution {
public:int sumOfPower(vector<int>& 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) 。忽略排序的栈空间,仅用到若干额外变量。

思考题:把「子序列」改成「子数组」,要怎么做?

相关文章:

LeetCode 2681. Power of Heroes【排序,数学,贡献法】2060

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

AVL树的讲解

算法拾遗三十八AVL树 AVL树AVL树平衡性AVL树加入节点AVL删除节点AVL树代码 AVL树 AVL树具有最严苛的平衡性&#xff0c;&#xff08;增、删、改、查&#xff09;时间复杂度为O&#xff08;logN&#xff09;&#xff0c;AVL树任何一个节点&#xff0c;左树的高度和右树的高度差…...

Unity 之 Input类

文章目录 总述具体介绍 总述 Input 类是 Unity 中用于处理用户输入的重要工具&#xff0c;它允许您获取来自键盘、鼠标、触摸屏和控制器等设备的输入数据。通过 Input 类&#xff0c;您可以轻松地检测按键、鼠标点击、鼠标移动、触摸、控制器按钮等用户输入事件。以下是关于 I…...

亚信科技AntDB数据库连年入选《中国DBMS市场指南》代表厂商

近日&#xff0c;全球权威ICT研究与顾问咨询公司Gartner发布了2023年《Market Guide for DBMS, China》&#xff08;即“中国DBMS市场指南”&#xff09;&#xff0c;该指南从市场份额、技术创新、研发投入等维度对DBMS供应商进行了调研。亚信科技是领先的数智化全栈能力提供商…...

AMBA总线协议(3)——AHB(一)

目录 一、前言 二、什么是AHB总线 1、概述 2、一个典型的基于AHB总线的微处理器架构 3、基本的 AHB 传送特性 三、AMBA AHB总线互联 四、小结 一、前言 在之前的文章中我们初步的了解了一下AMBA总线中AHB,APB,AXI的信号线及其功能&#xff0c;从本文开始我们…...

Git commit与pull的先后顺序

Git commit与pull的先后顺序_git先pull再commit_Mordor Java Girl的博客-CSDN博客 ​ 编辑yucoang2020.04.21 回复 28 先pull再commit的话, 你的commit也就不再纯粹了. 这一个commit不再是"你所编辑的xxx功能, 而是"别人所编辑的你所编辑的xxx". 我认为提交历…...

HarmonyOS/OpenHarmony应用开发-ArkTS语言渲染控制ForEach循环渲染

ForEach基于数组类型数据执行循环渲染。说明&#xff0c;从API version 9开始&#xff0c;该接口支持在ArkTS卡片中使用。 一、接口描述 ForEach(arr: any[], itemGenerator: (item: any, index?: number) > void,keyGenerator?: (item: any, index?: number) > stri…...

Powered by Paraverse | 平行云助力彼真科技打造演出“新物种”

01 怎么看待虚拟演出 彼真科技 我们怎么看待虚拟演出&#xff1f; 虚拟演出给音乐人或者音乐行业带来了哪些新的机会&#xff1f;通过呈现一场高标准的虚拟演出&#xff0c;我们的能力延伸点在哪里&#xff1f; 先说一下我们认知里的虚拟演出的本质&#xff1a; 音乐演出是一…...

企微配置回调服务

1、企微配置可信域名 2、企微获取成员userID 3、企微获取用户敏感数据 4、企微配置回调服务 文章目录 一、简介1、概述2、相关文档地址 二、企微配置消息服务器1、配置消息接收参数2、参数解析3、参数拼接规则 三、代码编写—使用已有库1、代码下载2、代码修改3、服务代码编写 …...

机器人远程控制软件设计

机器人远程控制软件设计 That’s all....

面试题-React(二):React中的虚拟DOM是什么?

一、什么是虚拟DOM&#xff1f; 虚拟DOM是React的核心概念之一&#xff0c;它是一个轻量级的JavaScript对象树&#xff0c;用于表示真实DOM的状态。在React中&#xff0c;当数据发生变化时&#xff0c;首先会在虚拟DOM上执行DOM更新&#xff0c;而不是直接操作真实DOM。然后&a…...

分布式链路追踪——Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

要解决的问题 如何记录请求经过多个分布式服务的信息&#xff0c;以便分析问题所在&#xff1f;如何保证这些信息得到完整的追踪&#xff1f;如何尽可能不影响服务性能&#xff1f; 追踪 当用户请求到达前端A&#xff0c;将会发送rpc请求给中间层B、C&#xff1b;B可以立刻作…...

【IEEE会议】第二届IEEE云计算、大数据应用与软件工程国际学术会议 (CBASE2023)

第二届IEEE云计算、大数据应用与软件工程国际学术会议 (CBASE2023&#xff09; 随着大数据时代的到来&#xff0c;对数据获取的随时性和对计算的需求也在逐渐增长。为推动大数据时代的云计算与软件工程的发展&#xff0c;促进该领域学术交流&#xff0c;在CBASE 2022成功举办的…...

Streamlit项目:基于讯飞星火认知大模型开发Web智能对话应用

文章目录 1 前言2 API获取3 官方文档的调用代码4 Streamlit 网页的搭建4.1 代码及效果展示4.2 Streamlit相关知识点 5 结语 1 前言 科大讯飞公司于2023年8月15日发布了讯飞认知大模型V2.0&#xff0c;这是一款集跨领域知识和语言理解能力于一体的新一代认知智能大模型。前日&a…...

[Vue]解决npm run dev报错node:internal/modules/cjs/loader:1031 throw err;

解决: 有2中方法&#xff0c;建议先尝试第一种&#xff0c;不行再第二种 第一种: 重新安装依赖环境 删除项目的node_modules文件夹&#xff0c;重新执行 # 安装依赖环境 npm install# 运行 npm run dev 我只用了第一种方法就可以了 &#xff0c;第二种方法从别的博主那看到…...

nginx反向代理后实现nginx和apache两种web服务器能够记录客户端的真实IP地址

一.构建环境 二.配置反向代理 1.基于源码安装的nginx环境下修改nginx.conf&#xff08;设备1&#xff09; 2.通过windows powershell进行修改hosts文件并测试 3.设备2和设备3上查看日志&#xff0c;可以看到访问来源都是代理服务器&#xff08;2.190&#xff09;而不是真实…...

【仿写tomcat】四、解析http请求信息,响应给前端,HttpServletRequest、HttpServletResponse的简单实现

思考 在解析请求之前我们要思考一个问题&#xff0c;我们解析的是其中的哪些内容&#xff1f; 对于最基本的实现&#xff0c;当然是请求类型&#xff0c;请求的url以及请求参数&#xff0c;我们可以根据请求的类型作出对应的处理&#xff0c;通过url在我们的mapstore中找到se…...

FL Studio21.1中文完整版Win/Mac

FL Studio All Plugins Edition【中文完整版 Win/Mac】适合音乐制作人/工作室使用&#xff0c;全套插件!&#xff08;20.9新增Vintage Chorus&#xff0c;Pitch Shifter变调插件&#xff09;FL Studio是超多顶级音乐人的启蒙首选&#xff01;包括百大DJ冠军Martin Garrix&…...

基于Mysql+Vue+Django的协同过滤和内容推荐算法的智能音乐推荐系统——深度学习算法应用(含全部工程源码)+数据集

目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境MySQL环境VUE环境 模块实现1. 数据请求和储存2. 数据处理计算歌曲、歌手、用户相似度计算用户推荐集 3. 数据存储与后台4. 数据展示 系统测试工程源代码下载其它资料下载 前言 本项目以丰富的网易云音乐数据为基…...

Python Web开发 Django 简介

今天来为大家介绍 Python 另一个 Web 开发框架 Django&#xff0c;它是一个基于 Python 定制的开源 Web 应用框架&#xff0c;最早源于一个在线新闻 Web 网站&#xff0c;后于2005年开源。Django 的功能大而全&#xff0c;它提供的一站式解决的思路&#xff0c;能让开发者不用在…...

HAproxy搭建web集群

目录 一、HAproxy 概述 二、HAproxy 主要特性 三、HAproxy 负载均衡策略(八种) 四、LVS、Nginx、HAproxy区别 Nginx LVS HAproxy 五、HAproxy部署实战 问题总结&#xff1a; 一、HAproxy 概述 HAProxy是可提供高可用性、负载均衡以及基于TCP和HTTP应用的代理&#xff0…...

临时用工小程序:一款便捷的用工管理软件

随着企业对人力资源需求的不断增长&#xff0c;临时用工需求也日益旺盛。为了满足这一需求&#xff0c;我们研发了一款名为“临时用工小程序”的软件系统&#xff0c;旨在帮助企业实现临时用工的高效管理。 一、技术栈介绍 后端技术栈 本系统采用Java语言作为开发语言&#…...

Android Studio 之 Android 中使用 HanLP 进行句子段落的分词处理(包括词的属性处理)的简单整理

Android Studio 之 Android 中使用 HanLP 进行句子段落的分词处理&#xff08;包括词的属性处理&#xff09;的简单整理 目录 Android Studio 之 Android 中使用 HanLP 进行句子段落的分词处理&#xff08;包括词的属性处理&#xff09;的简单整理 一、简单介绍 二、实现原理…...

CSDN编程题-每日一练(2023-08-20)

CSDN编程题-每日一练(2023-08-19) 一、题目名称:等差数列二、题目名称:喜水青蛙三、题目名称:括号匹配一、题目名称:等差数列 时间限制:1000ms内存限制:256M 题目描述: 给定一已排序的正整数组成的数组,求需要在中间至少插入多少个数才能将其补全成为一等差数列。 “…...

大数据:NumPy进阶应用详解

专栏介绍 结合自身经验和内部资料总结的Python教程&#xff0c;每天3-5章&#xff0c;最短1个月就能全方位的完成Python的学习并进行实战开发&#xff0c;学完了定能成为大佬&#xff01;加油吧&#xff01;卷起来&#xff01; 全部文章请访问专栏&#xff1a;《Python全栈教…...

new String创建几个对象

在java17中 &#xff1a; 问题1&#xff1a;new String("abc")会产生多少个对象&#xff1f; 分两种情况&#xff1a; 情况1&#xff1a; 如果”abc”这个字符串常量不存在&#xff0c;则创建两个对象&#xff0c;分别是“abc”这个字符串常量&#xff0c;以及ne…...

【路由协议】使用按需路由协议和数据包注入的即时网络模拟传递率(PDR)、总消耗能量和节点消耗能量以及延迟研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

c#实现依赖注入

当谈到C#中的依赖注入(Dependency Injection,DI)时,我们可以使用一个简单的示例来说明它是如何工作的。依赖注入是一种设计模式,用于将依赖关系从一个类传递到另一个类,以实现松耦合和可测试性。 假设我们有一个简单的订单处理应用程序,其中包含两个主要类:OrderServi…...

算法通关村十一关 | 位运算实现加法和乘法

1.位实现加法和乘法 在计算机中&#xff0c;位运算的效率要比加减乘除的效率更高&#xff0c;因此在高性能软件中源码中大量使用&#xff0c;计算机里各种运算基本上都是位运算。 学习下面内容之前建议先学习位运算规则&#xff1a;算法通关村十一关 | 位运算的规则_我爱学算…...

C++笔记之条件变量(Condition Variable)与cv.wait 和 cv.wait_for的使用

C笔记之条件变量&#xff08;Condition Variable&#xff09;与cv.wait 和 cv.wait_for的使用 参考博客&#xff1a;C笔记之各种sleep方法总结 code review! 文章目录 C笔记之条件变量&#xff08;Condition Variable&#xff09;与cv.wait 和 cv.wait_for的使用1.条件变量&…...