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

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&#xff1a;示例2&#xff1a;示例3&#xff1a; 思路代码 题目描述 给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个 子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。 请…...

CSS3雷达扫描效果

CSS3雷达扫描效果https://www.bootstrapmb.com/item/14840 要创建一个CSS3的雷达扫描效果&#xff0c;我们可以使用CSS的动画&#xff08;keyframes&#xff09;和transform属性。以下是一个简单的示例&#xff0c;展示了如何创建一个类似雷达扫描的动画效果&#xff1a; HTM…...

单例模式懒汉模式和饿汉模式

线程安全 单例模式在单线程中&#xff0c;当然是安全的。但是如果在多线程中&#xff0c;由于并行判断&#xff0c;可能会导致创建多个实例。那么如何保证在多线程中单例还是只有一个实例呢? 常见的三种方式: 局部静态变量 原理和饿汉模式相似&#xff0c;利用static只会初始…...

python __repr__和__str__区别

1. __repr__ __repr__ 方法由 repr() 内置函数调用&#xff0c;用于计算对象的“正式”字符串表示形式。理想情况下&#xff0c;这个字符串应该看起来像一个有效的 Python 表达式&#xff0c;可以在适当的环境下用来重新创建具有相同值的对象。如果这不可能实现&#xff0c;那…...

huawei USG6001v1学习----NAT和智能选路

目录 1.NAT的分类 2.智能选路 1.就近选路 2.策略路由 3.智能选路 NAT:&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09; 指网络地址转换&#xff0c;1994年提出的。NAT是用于在本地网络中使用私有地址&#xff0c;在连接互联网时转而使用全局…...

FPGA JTAG最小系统 EP2C5T144C8N

FPGA的文档没有相应的基础还真不容易看懂&#xff0c;下面是B站上对FPGA文档的解读(本文非对文档解读&#xff0c;只是为个人记录第三期&#xff1a;CycloneIV E最小系统板设计&#xff08;一&#xff09;从Datasheet上获取FPGA的基本参数_哔哩哔哩_bilibili 电源部份 核心电…...

Android 15 之如何快速适配 16K Page Size

在此之前&#xff0c;我们通过 《Android 15 上 16K Page Size 为什么是最坑》 介绍了&#xff1a; 什么是16K Page Size为什么它对于 Android 很坑如何测试 如果你还没了解&#xff0c;建议先去了解下前文&#xff0c;然后本篇主要是提供适配的思路&#xff0c;因为这类适配…...

学习unity官方的网络插件Netcode【一】

对bool值的个人理解&#xff1a; using Unity.Netcode; using UnityEngine; //个人理解&#xff1a;通过Rpc完成了一次客户端给服务端发消息&#xff0c;服务端再向所有客户端广播消息 public class RpcTest : NetworkBehaviour {public override void OnNetworkSpawn(){if (!…...

QT写一个mainWindow

切换风格的写法&#xff1a; 先看看样式效果&#xff1a; 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 …...

洗地机哪个牌子好?四款口碑最好的洗地机排名推荐

随着“懒人经济”的出现&#xff0c;越来越多的人开始使用洗地机。洗地机哪个牌子好&#xff1f;为了帮助大家在这个琳琅满目的市场中做出明智决策&#xff0c;本文特别整理了四款口碑最好的洗地机排名推荐&#xff0c;它们凭借出色的清洁效果、智能化的操作体验以及用户的高度…...

如何提升短视频的曝光量和获客效能?云微客来解决

在流量至上的当下&#xff0c;短视频凭借其优势&#xff0c;迅速成为了众多企业获客引流的核心营销手段。进入短视频赛道后&#xff0c;如何提升短视频的曝光量和获客效能&#xff0c;就成为了众多企业亟待解决的焦点。 如果你不想投入大量的广告预算&#xff0c;还想在短视频平…...

SpringBoot开发中如何缓存数据, 减少数据库的访问频率?

一&#xff1a;自定义是否开启缓存 方法一&#xff1a; 在不同环境的配置文件中如application-dev.yml、application-test.yml、application-prod.yml&#xff0c;修改 spring.cache.type none; spring:cache:type: none 方法二&#xff1a; 自定义配置 application.yml&…...

PostgreSQL如何在windows/linux开启归档

linux开启归档&#xff1a; archive_mode onarchive_command test ! -f /mnt/pg12/archivedir/%f && cp %p /mnt/pg12/archivedir/%fwindows开启归档&#xff1a; archive_mode onarchive_command copy "%p" "C:\\server\\pg12\\archivedir\\%f&q…...

【启明智显分享】基于国产Model3芯片的7寸触摸屏助力智慧医疗,电子床头屏提升护理交互

未来医院必然是以信息化为基础&#xff0c;以物联网为特征&#xff0c;以医疗为核心的服务型医院。病房作为医院的重要服务场所&#xff0c;成为智慧医院建设的重要一环。 为提高医护人员与患者的互动交流&#xff0c;给医疗注入智慧元素&#xff0c;让患者享受智能服务&#…...

从理论到实践:如何用 TDengine 打造完美数据模型​

在用 TDengine 进行数据建模之前&#xff0c;我们需要回答两个关键问题&#xff1a;建模的目标用户是谁&#xff1f;他们的具体需求是什么&#xff1f;在一个典型的时序数据管理方案中&#xff0c;数据采集和数据应用是两个主要环节。如下图所示&#xff1a; 对于数据采集工程师…...

可以免费合并pdf的软件 合并pdf文件的软件免费 合并pdf的软件免费

在数字化办公的今天&#xff0c;pdf格式因其稳定性和跨平台兼容性被广泛使用。然而&#xff0c;当我们需要将多个 pdf 文件合并为一个时&#xff0c;却往往感到力不从心。本文将为你介绍几款强大的pdf文件合并软件&#xff0c;让你轻松管理文档。 方法一、使用pdf转换器 步骤1…...

【排序 滑动窗口 】1498. 满足条件的子序列数目

本文涉及至知识点 排序 C算法&#xff1a;滑动窗口总结 LeetCode1498. 满足条件的子序列数目 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大&#xff0c;…...

RabbitMQ普通集群搭建指南

RabbitMQ普通集群搭建指南 本文已经完全迁移至&#xff0c;www.geekery.cn 后续不在此更新 目标架构 本次搭建的目标是构建一个由三个节点组成的RabbitMQ集群&#xff0c;节点信息如下&#xff1a; rabbit02: IP地址 192.168.10.132rabbit03: IP地址 192.168.10.133rabbit04:…...

AGV平面坐标系变换公式及实例

1、AGV坐标系简介 如上图&#xff0c;小车前后对角是有激光雷达的&#xff0c;其坐标系称为激光坐标系&#xff0c;采用极坐标系体现。中间为车体坐标系&#xff0c;激光坐标系相对于车体坐标系关系不变&#xff1b;左下角是地图坐标系&#xff0c;小车扫图后&#xff0c;建立的…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...