LeetCode-day23-3098. 求出所有子序列的能量和
LeetCode-day23-3098. 求出所有子序列的能量和
- 题目描述
- 示例
- 示例1:
- 示例2:
- 示例3:
- 思路
- 代码
题目描述
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个 子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。
请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
由于答案可能会很大,将答案对 109 + 7 取余 后返回。
示例
示例1:
输入:nums = [1,2,3,4], k = 3
输出:4
解释:
nums 中总共有 4 个长度为 3 的子序列:[1,2,3] ,[1,3,4] ,[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。
示例2:
输入:nums = [2,2], k = 2
输出:0
解释:
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。
示例3:
输入:nums = [4,3,-1], k = 2
输出:10
解释:
nums 总共有 3 个长度为 2 的子序列:[4,3] ,[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。
思路
子序列问题的拆解 + 前缀和优化
代码
MOD = 10**9+7class Solution:def sumOfPowers(self, a: List[int], k: int) -> int:n = len(a)a.sort()def calc(dist_from_center: List[int], limit_lo: int) -> int:m = len(dist_from_center) # 从中心点算起的距离f = [[0] * k for _ in range(m)] # f[i][j]: 取到第i个元素时,拿j个物品的方法数f[0][1] = 1 # 背包问题方案数f_acc = [[0] * k for _ in range(m + 1)] # f_acc[i][j]: 物品[0, i-1], 拿j物品的方法数f_acc[1][1] = 1pt = 0for i in range(1, m):while pt < i and dist_from_center[i] - dist_from_center[pt] >= limit_lo:pt += 1for v in range(k - 1):f[i][v + 1] = (f[i][v + 1] + f_acc[pt][v]) % MODfor v in range(k):f_acc[i + 1][v] = (f_acc[i][v] + f[i][v]) % MODreturn f_acc[-1] # 物品[0, m]之方法数ans = 0for i in range(n):for j in range(i):min_diff = a[i] - a[j] # 最小差值dist_left = [a[j] - a[k] for k in range(j, -1, -1)] # 注意取距离中心点的距离,要包含自己!f_left = calc(dist_left, min_diff + 1) # 左右随便找一个不包含,都不会重复dist_right = [a[k] - a[i] for k in range(i, n)]f_right = calc(dist_right, min_diff)for x in range(1, k): # 枚举左右取多少,左右至少取一个ans = (ans + min_diff * f_left[x] * f_right[k - x]) % MODreturn ans
相关文章:
LeetCode-day23-3098. 求出所有子序列的能量和
LeetCode-day23-3098. 求出所有子序列的能量和 题目描述示例示例1:示例2:示例3: 思路代码 题目描述 给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个 子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。 请…...
CSS3雷达扫描效果
CSS3雷达扫描效果https://www.bootstrapmb.com/item/14840 要创建一个CSS3的雷达扫描效果,我们可以使用CSS的动画(keyframes)和transform属性。以下是一个简单的示例,展示了如何创建一个类似雷达扫描的动画效果: HTM…...
单例模式懒汉模式和饿汉模式
线程安全 单例模式在单线程中,当然是安全的。但是如果在多线程中,由于并行判断,可能会导致创建多个实例。那么如何保证在多线程中单例还是只有一个实例呢? 常见的三种方式: 局部静态变量 原理和饿汉模式相似,利用static只会初始…...
python __repr__和__str__区别
1. __repr__ __repr__ 方法由 repr() 内置函数调用,用于计算对象的“正式”字符串表示形式。理想情况下,这个字符串应该看起来像一个有效的 Python 表达式,可以在适当的环境下用来重新创建具有相同值的对象。如果这不可能实现,那…...
huawei USG6001v1学习----NAT和智能选路
目录 1.NAT的分类 2.智能选路 1.就近选路 2.策略路由 3.智能选路 NAT:(Network Address Translation,网络地址转换) 指网络地址转换,1994年提出的。NAT是用于在本地网络中使用私有地址,在连接互联网时转而使用全局…...
FPGA JTAG最小系统 EP2C5T144C8N
FPGA的文档没有相应的基础还真不容易看懂,下面是B站上对FPGA文档的解读(本文非对文档解读,只是为个人记录第三期:CycloneIV E最小系统板设计(一)从Datasheet上获取FPGA的基本参数_哔哩哔哩_bilibili 电源部份 核心电…...
Android 15 之如何快速适配 16K Page Size
在此之前,我们通过 《Android 15 上 16K Page Size 为什么是最坑》 介绍了: 什么是16K Page Size为什么它对于 Android 很坑如何测试 如果你还没了解,建议先去了解下前文,然后本篇主要是提供适配的思路,因为这类适配…...
学习unity官方的网络插件Netcode【一】
对bool值的个人理解: using Unity.Netcode; using UnityEngine; //个人理解:通过Rpc完成了一次客户端给服务端发消息,服务端再向所有客户端广播消息 public class RpcTest : NetworkBehaviour {public override void OnNetworkSpawn(){if (!…...
QT写一个mainWindow
切换风格的写法: 先看看样式效果: mian_window.h文件 #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow>class MainWindow : public QMainWindow {Q_OBJECTpublic:MainWindow(QWidget *parent nullptr);~MainWindow();void Ini…...
Java查找算法练习(2024.7.23)
顺序查找 package SearchExercise20240723; import java.util.Scanner; public class SearchExercise {public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println("需要多大的数组?");int size sc.nextInt();int[] array …...
洗地机哪个牌子好?四款口碑最好的洗地机排名推荐
随着“懒人经济”的出现,越来越多的人开始使用洗地机。洗地机哪个牌子好?为了帮助大家在这个琳琅满目的市场中做出明智决策,本文特别整理了四款口碑最好的洗地机排名推荐,它们凭借出色的清洁效果、智能化的操作体验以及用户的高度…...
如何提升短视频的曝光量和获客效能?云微客来解决
在流量至上的当下,短视频凭借其优势,迅速成为了众多企业获客引流的核心营销手段。进入短视频赛道后,如何提升短视频的曝光量和获客效能,就成为了众多企业亟待解决的焦点。 如果你不想投入大量的广告预算,还想在短视频平…...
SpringBoot开发中如何缓存数据, 减少数据库的访问频率?
一:自定义是否开启缓存 方法一: 在不同环境的配置文件中如application-dev.yml、application-test.yml、application-prod.yml,修改 spring.cache.type none; spring:cache:type: none 方法二: 自定义配置 application.yml&…...
PostgreSQL如何在windows/linux开启归档
linux开启归档: archive_mode onarchive_command test ! -f /mnt/pg12/archivedir/%f && cp %p /mnt/pg12/archivedir/%fwindows开启归档: archive_mode onarchive_command copy "%p" "C:\\server\\pg12\\archivedir\\%f&q…...
【启明智显分享】基于国产Model3芯片的7寸触摸屏助力智慧医疗,电子床头屏提升护理交互
未来医院必然是以信息化为基础,以物联网为特征,以医疗为核心的服务型医院。病房作为医院的重要服务场所,成为智慧医院建设的重要一环。 为提高医护人员与患者的互动交流,给医疗注入智慧元素,让患者享受智能服务&#…...
从理论到实践:如何用 TDengine 打造完美数据模型
在用 TDengine 进行数据建模之前,我们需要回答两个关键问题:建模的目标用户是谁?他们的具体需求是什么?在一个典型的时序数据管理方案中,数据采集和数据应用是两个主要环节。如下图所示: 对于数据采集工程师…...
可以免费合并pdf的软件 合并pdf文件的软件免费 合并pdf的软件免费
在数字化办公的今天,pdf格式因其稳定性和跨平台兼容性被广泛使用。然而,当我们需要将多个 pdf 文件合并为一个时,却往往感到力不从心。本文将为你介绍几款强大的pdf文件合并软件,让你轻松管理文档。 方法一、使用pdf转换器 步骤1…...
【排序 滑动窗口 】1498. 满足条件的子序列数目
本文涉及至知识点 排序 C算法:滑动窗口总结 LeetCode1498. 满足条件的子序列数目 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大,…...
RabbitMQ普通集群搭建指南
RabbitMQ普通集群搭建指南 本文已经完全迁移至,www.geekery.cn 后续不在此更新 目标架构 本次搭建的目标是构建一个由三个节点组成的RabbitMQ集群,节点信息如下: rabbit02: IP地址 192.168.10.132rabbit03: IP地址 192.168.10.133rabbit04:…...
AGV平面坐标系变换公式及实例
1、AGV坐标系简介 如上图,小车前后对角是有激光雷达的,其坐标系称为激光坐标系,采用极坐标系体现。中间为车体坐标系,激光坐标系相对于车体坐标系关系不变;左下角是地图坐标系,小车扫图后,建立的…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
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 如果用户登录尝试失败次…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
