当前位置: 首页 > 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;建立的…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...