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坐标系简介 如上图,小车前后对角是有激光雷达的,其坐标系称为激光坐标系,采用极坐标系体现。中间为车体坐标系,激光坐标系相对于车体坐标系关系不变;左下角是地图坐标系,小车扫图后,建立的…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
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* …...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
