当前位置: 首页 > 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配置文件由许多嵌套的…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...