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

力扣第 104 场双周赛 2681. 英雄的力量

原题链接力扣

 题目大意:我开始看成连续子段了,写了个递归程序....... 

一个数组任选一个子序列,子序列的力量值=最大值平方*最小值。求所有子序列的力量和。

分析过程:如序列长度为n,子序列总数为2的n次幂,显然不可能枚举所有子序列来求解。那么只能锁定子序列最大值和最小值来处理。容易想到先排序,排序后的序列可以取任意ai和aj,那么ai最小值,aj 最大值,i和j之间的元素可以任取,例如i=2,j=6,那么i和j之间有3个其他元素,这3个元素可以任取,因此共有2的3次幂共8种选取方法:(a2,a6) (a2,a3,a6) (a2,a4,a6) (a2,a5,a6)(a2,a3,a4,a6).......。枚举所有i和j,时间复杂度为O(n2)。

这类问题如何继续降低复杂度。一般来说都会存在某种规律,使得下一次的处理能利用上一次的结果,也有写问题存在某种(数学)方法,能直接求得解。本题目通过找规律解决。

假设a1为最小值,那么子序列中必然有a1,此时如果锁定ai为最大值,那么所有满足(a1最小,ai最大)的子序列数量必然ai*ai*a1*pow(2,i-2)。

枚举下最大最小值分别为(i,j)的公式

最大值j\最小值ia1       a2a3......总和
a2a1*a2*a2

(a1)*a2*a2

a32a1*a3*a3a2*a3*a3

(2a1+a2)*a3*a3

a44a1*a4*a42a2*a4*a4(4a1+2a2+a3)*a4*a4
a58a1*a5*a54a2*a5*a52a3*a5*a5......(8a1+4a2+2a3+a4)*a5*a5
a616a1*a6*a68a2*a6*a64a3*a6*a6......

可以发现规律为当ai为最大值时,其组成所有子序列的力量和为Y[i]*a[i]*a[i],而这个Y[i]可以由Y[i-1]*2+a[i-1]求得。

class Solution {
public:int sumOfPower(vector<int>& nums) {int i,j,r=nums.size()-1,mod=1e9+7;;sort(nums.begin(),nums.end());/**< 排序 */long long ans=0,sum=nums[0];for(i=0;i<=r;i++)/**< 就一个元素序列单独处理 */ans=(ans+1LL*nums[i]*nums[i]%mod*nums[i])%mod;for(i=1;i<=r;i++)/**< 最大值为i的力量和 */{long long temp=1LL*nums[i]*nums[i]%mod;ans=(ans+temp*sum%mod)%mod;sum=(sum*2+nums[i])%mod;/**< i+1的系数 */}return (int)ans;}
};

两个循环综合在一起的写法。

class Solution {
public:int sumOfPower(vector<int>& nums) {int i,j,r=nums.size()-1,mod=1e9+7;;sort(nums.begin(),nums.end());/**< 排序 */long long ans=0,sum=0;for(i=0;i<=r;i++)/**< 最大值为i的力量和 */{long long temp=1LL*nums[i]*nums[i]%mod;ans=(ans+temp*(sum+nums[i])%mod)%mod;sum=(sum*2+nums[i])%mod;/**< i+1的系数 */}return (int)ans;}
};

相关文章:

力扣第 104 场双周赛 2681. 英雄的力量

原题链接力扣 题目大意&#xff1a;我开始看成连续子段了&#xff0c;写了个递归程序....... 一个数组任选一个子序列&#xff0c;子序列的力量值最大值平方*最小值。求所有子序列的力量和。 分析过程&#xff1a;如序列长度为n&#xff0c;子序列总数为2的n次幂&#xff0c…...

在linux上创建crypto_LUKS格式的块设备

要在Linux上创建一个块设备并将其格式化为 crypto_LUKS&#xff0c;可以按照以下步骤进行&#xff1a; 创建一个空白文件&#xff0c;作为块设备的基础。可以使用 dd 命令创建指定大小的文件&#xff0c;例如&#xff1a; dd if/dev/zero of/path/to/device bs1M count100这将创…...

76.建立一个主体样式第二部分

上节课的时候我们完成的页面是这个样子&#xff01; ● 之后我们通过绝对定位来解决位置定位的问题 .header-container {width: 1200px;margin: 0 auto;position: absolute;left: 50%;top: 50%; }header {height: 100vh;background-color: orange;position: relative; }● 之…...

SQL删除重复的记录(只保留一条)-窗口函数row_number()

文章目录 一、关于mysql表中数据重复二、聚合函数min(id)not in二、窗口函数row_number()四、补充&#xff1a;常见的窗口函数 一、关于mysql表中数据重复 关于删除mysql表中重复数据问题&#xff0c;本文中给到两种办法&#xff1a;聚合函数、窗口函数row_number()的方法。 (注…...

CF1660D Maximum Product Strikes Back 题解

CF1660D Maximum Product Strikes Back 题解 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路点拨&#xff08;分类题&#xff09;缩小研究对象范围除0的分析加上0的分析 代码实现小方法陈述 题目描述 你有一个长度为 n n n 的数组&#xff0c;每一个元素都在 …...

基于CSSOM的暗链检测技术实现方案

什么是暗链 大部分的开源代码在实现暗链检测的时候都是直接判断页面里面有没有敏感词,如果有,就认为该链接为暗链。这种做法其实是有误的。 违规链接应该分为:外链、内链、死链和暗链。而暗链除了违规,还应该具备“暗”这个看不见的特征。 暗链的特征 其实“暗链”就是看…...

MySQL db、tables_priv、columns_priv和procs_priv权限表

在 MySQL 数据库中&#xff0c;权限表除了 user 表外&#xff0c;还有 db 表、tables_priv 表、columns_priv 表和 procs_priv 表。在《MySQL user权限表详解》中我们讲解了 MySQL 的 user 表&#xff0c;下面主要介绍其它几种权限表。 db表 db 表比较常用&#xff0c;是 MyS…...

JavaWeb-JSP的学习

JSP 今日目标&#xff1a; 理解 JSP 及 JSP 原理能在 JSP中使用 EL表达式 和 JSTL标签理解 MVC模式 和 三层架构能完成品牌数据的增删改查功能 1、JSP 概述 JSP&#xff08;全称&#xff1a;Java Server Pages&#xff09;&#xff1a;Java 服务端页面。是一种动态的网页技术…...

力扣sql中等篇练习(二十三)

力扣sql中等篇练习(二十三) 1 统计实验的数量 1.1 题目内容 1.1.1 基本题目信息 1.1.2 示例输入输出 1.2 示例sql语句 # 有可能数据本身就不全,就需要自行创建临时表 WITH T as (SELECT Android p1,Reading e1UNIONSELECT Android p1,Sports e1UNIONSELECT Android p1,Prog…...

C语言算法之查找

一.查找相关概念 这一部分解释数据结构里面查找的相关基础概念&#xff1a; 查找&#xff1a;在数据集合中寻找满足某种条件的数据元素的过程。查找表&#xff1a;用于查找的数据集合关键字&#xff1a;数据元素中唯一标识该元素的某个数据项的值静态查找表&#xff1a;静态查…...

肝一肝设计模式【九】-- 享元模式

系列文章目录 肝一肝设计模式【一】-- 单例模式 传送门 肝一肝设计模式【二】-- 工厂模式 传送门 肝一肝设计模式【三】-- 原型模式 传送门 肝一肝设计模式【四】-- 建造者模式 传送门 肝一肝设计模式【五】-- 适配器模式 传送门 肝一肝设计模式【六】-- 装饰器模式 传送门 肝…...

自动化测试的十大雷区【刚入门必看】

虽然从自己的错误中学习也不错&#xff0c;但从别人的错误中学习总是更好的。 作为一个自动化测试人员&#xff0c;分享常见的容易犯的10个错误&#xff0c;可以从中吸取教训&#xff0c;引以为鉴。 一、必要时才自动化 新人小王接到为Web应用程序自动化测试脚本的任务时&…...

【Android源码篇】用grep搜索源码内容关键词

前言 选项&#xff1a; • -w&#xff1a;只匹配整个单词&#xff0c;不会部分匹配 • -r&#xff1a;递归搜索 • -n&#xff1a;显示行号 • -i&#xff1a;忽略字符大小写 • -I&#xff08;大写i&#xff09;&#xff1a;忽略二进制文件 • -I&#xff1a;忽略文件内容&am…...

腾讯云轻量应用服务器卡死怎么连接?

腾讯云轻量云服务器卡死怎么解决&#xff1f;使用腾讯云自带的VNC登录连接轻量服务器&#xff0c;或使用腾讯云OrcaTerm一键免密登录轻量实例。如果是确定数据没问题&#xff0c;也可以使用控制台自带的重启实例。 腾讯云轻量应用服务器参考&#xff1a;https://curl.qcloud.co…...

Charles安装及抓取APP接口

一、Charles使用 Charles是一款代理服务器&#xff0c;通过过将自己设置成系统&#xff08;电脑或者浏览器&#xff09;的网络访问代理服务器&#xff0c;然后截取请求和请求结果达到分析抓包的目的。该软件是用Java写的&#xff0c;能够在Windows&#xff0c;Mac&#xff0c;…...

Linux开发工具:yum和vim的使用

目录 一. Linux下的软件 1.1 软件安装的三种方法 1.2 采用yum安装软件 1.3 yum源的问题 二. vim开发工具的使用 2.1 vim的三种基本模式 2.2 命令模式下vim的常用指令 2.2.1 定位相关指令 2.2.2 光标移动相关指令 2.2.3 插入相关指令 2.2.4 复制粘贴相关指令 2.2.5 替…...

Java基础重温巩固

方法 方法与方法之间是平级关系&#xff0c;不能嵌套return表示结束当前方法 基本数据类型和引用数据类型 基本数据类型&#xff1a;数据存储在自己的空间中 引用数据类型&#xff1a;数据存储在其他空间中&#xff0c;自己空间存储的是地址值 值传递 传递基本数据类型时&…...

Text2SQL 语义解析数据集、解决方案和学术论文资源整合

目录 什么是Text2SQL? Text2SQL语义解析数据集 Text2SQL解决方案 Text2SQL相关学术论文 欢迎大家&#xff0c;我是你们的博主&#xff0c;今天我们来讨论一个非常有趣且有挑战性的话题 —— Text2SQL。这个话题涉及到自然语言处理 (NLP)&#xff0c;数据库查询语言 (SQL)&…...

redis集群+哨兵配置实操宝典

本地安装redis 配置集群和哨兵 1、下载安装redis #wget http://download.redis.io/releases/redis-5.0.12.tar.gz #下载安装包 #yum -y install gcc #安装依赖包 #tar -zxvf redis-5.0.12.tar.gz #cd redis-5.0.12 #make 2、主备配置 我们采用一主两备的结构 主机 192.168.3.…...

nginx的语法

概览 Nginx是一个高效、稳定的开源Web服务器和反向代理服务器&#xff0c;也可以用作邮件代理服务器、负载均衡器和HTTP缓存。以下是Nginx配置文件的一些基本语法和组成部分&#xff1a; 配置块&#xff08;Block Directives&#xff09;&#xff1a;Nginx配置文件由许多嵌套的…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...