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

算法第十二天-最大整除子集

最大整除子集

题目要求

解题思路

来自[宫水三叶]
根据题意:对于符合要求的[整除子集]中的任意两个值,必然满足[较大数]是[较小数]的倍数
数据范围是 1 0 3 10^3 103,我们不可能采取获取所有子集,再检查子集是否合法的暴力搜解法。
通常递归做不了,我们就往[递推]方向取考虑。
由于存在[整除子集]中任意两个值必然存在倍数/约数关系的性质,我们自然会想到对nums进行排序,然后从集合nums中从大到小进行取数每次取数只考虑到当前决策的数是否与[整除子集]中的最后一个数成倍数关系即可。
这时候你可能会想枚举个数作为[整除子集]的起点,然后从前往后遍历一遍,每次都将符合[与当前子集最后一个元素成倍数]关系的数加入答案。
但是这样子的做法只能确保获得[合法解],无法确保得到的是[最长整除子集]
得到这个反例:[9,18,54,90,108,180,360,540,720],如果按照我们上述逻辑,我们得到的是 [9,18,54,108,540] 答案(长度为 5),但事实上存在更长的「整除子集」: [9,18,90,180,360,720](长度为 6)。

其本质是因为同一个数的不同倍数之间不存在必然的[倍数/约数关系],而是存在[具有公约数]的性质,这会导致我们[模拟解法]错过最优解
因此当我们决策到某个数nums[i]时(nums已排好序),我们无法直接将nums[i]直接接在符合[约数关系]的,最靠近位置i的数后面,而是要检查位置i前面的所有符合[约数关系]的位置,找到一个已经形成[整除子集]长度最大的数。换句话说,当我们对nums排好序号并从前往后处理时,已经形成的[整数子集]长度是多少,然后从中选一个最长的[整除子集],将nums[i]接在后面(前提是符合[倍数关系])

动态规划

基于上述分析,我们不难发现这其实是一个序列DP问题:某个状态的转移依赖于与前一个状态的关系。即nums[i]能否接在nums[j]后面,取决于是否满足nums[i] % nums[j] == 0条件
可以看作是[最长上升子序列]问题的变形题。
定义f[i]为考虑前i个数字,且以第i个数为结尾的最长[整数子集]长度
我们不失一般性的考虑任意位置i,存在两种情况:

  • 如果在i之前找不到符合条件nums[i]%nums[j]==0的位置j,那么nums[i]不能接在位置i之前的任何数的后面,只能自己独立作为[整除子集]的第一个数,此时状态转移方程为f[i]=1;
  • 如果在i之前能够找到符合条件的位置j,则取所有符合条件的f[i]的最大值,代表如果希望找到以nums[i]作为结尾的最长[整除子集],需要将nums[i]接到符合条件的最长的nums[j]后面,此时状态转移方程为f[i]=f[j]+1

同时由于我们需要输出具体方案,需要额外使用g[]数组来记录每个状态是由哪个状态转移而来的。
定义g[i]为记录f[i]是由哪个下标的状态转移而来的,如果f[i] = f[j] + 1,则有g[i] = j
对于求方案数的题目,多开一个数组来记录状态从何转移而来是常见的手段。当我们求得所有的状态值止呕,可以对f[]数组进行遍历,取得最长[整除子集]长度和对应下标,然后使用g[]数组进行回溯,取得答案。

代码

class Solution:def largestDivisibleSubset(self, nums: List[int]) -> List[int]:nums.sort()n = len(nums)f,g = [0] *n,[0]*nfor i in range (n):#至少包含自身一个数,因此起始长度为1,由自身转移而来length,prev =1,ifor j in range(i):if nums[i] %nums[j] ==0:# 如果能接在更长的序列后面,则更新[最大长度]&[从何转移而来]if f[j] +1>length:length +=1prev =j# 记录【最终长度】& 【从何转移而来】f[i] =lengthg[i] =prev#遍历所有的f[i],取得[最大长度]和【对应下标】max_len = idx = -1for i in range(n):if f[i] >max_len:idx =imax_len =f[i]#使用g[]数组回溯出具体方案ans=[]while len(ans)<max_len:ans.append(nums[idx])idx = g[idx]ans.reverse()return ans

复杂度分析

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)

相关文章:

算法第十二天-最大整除子集

最大整除子集 题目要求 解题思路 来自[宫水三叶] 根据题意&#xff1a;对于符合要求的[整除子集]中的任意两个值&#xff0c;必然满足[较大数]是[较小数]的倍数 数据范围是 1 0 3 10^3 103&#xff0c;我们不可能采取获取所有子集&#xff0c;再检查子集是否合法的暴力搜解法…...

简单易懂的PyTorch 损失函数:优化机器学习模型的关键

目录 torch.nn子模块Loss Functions详解 nn.L1Loss 用途 用法 使用技巧 注意事项 代码示例 nn.MSELoss 用途 用法 使用技巧 注意事项 代码示例 nn.CrossEntropyLoss 用途 用法 使用技巧 注意事项 代码示例 使用类别索引 使用类别概率 nn.CTCLoss 用途 …...

Kubernetes/k8s的存储卷/数据卷

k8s的存储卷/数据卷 容器内的目录和宿主机的目录挂载 容器在系统上的生命周期是短暂的&#xff0c;delete&#xff0c;k8s用控制创建的pod&#xff0c;delete相当于重启&#xff0c;容器的状态也会回复到初始状态 一旦回到初始状态&#xff0c;所有的后天编辑的文件都会消失…...

【漏洞复现】锐捷RG-UAC统一上网行为管理系统信息泄露漏洞

Nx01 产品简介 锐捷网络成立于2000年1月&#xff0c;原名实达网络&#xff0c;2003年更名&#xff0c;自成立以来&#xff0c;一直扎根行业&#xff0c;深入场景进行解决方案设计和创新&#xff0c;并利用云计算、SDN、移动互联、大数据、物联网、AI等新技术为各行业用户提供场…...

Android - 串口通讯(SerialPort)

最早的博客Android 模拟串口通信过程_launch virtual serial port driver pro-CSDN博客里就是用过 Google 提供的 demo&#xff0c;最近想再写个其他的demo发现用起来有点麻烦&#xff0c;还需要导入其他 module&#xff0c;因此在网上找到了Android-SerialPort-API: https://g…...

如何使用設置靜態住宅IP

靜態住宅IP就是一種靜態的、分配給住宅用戶的IP地址。與動態IP地址不同&#xff0c;靜態住宅IP一旦分配給用戶&#xff0c;就會一直保持不變&#xff0c;除非ISP&#xff08;Internet Service Provider&#xff0c;互聯網服務提供商&#xff09;進行手動更改。那麼&#xff0c;…...

在学习爬虫前的准备

1. 写一个爬虫程序需要分几步 获取网页内容。 我们会通过代码给一个网站服务器发送请求&#xff0c;它会返回给我们网页上的内容。 在我们平时使用浏览器访问服务器内容是&#xff0c;本质上也是向服务器发送一个请求&#xff0c;然后服务器返回网页上的内容。只不过浏览器还会…...

windows下安装oracle-win-64-11g超详细图文步骤

官方下载地址&#xff1a;点这里 1.根据自己电脑情况&#xff0c;解压64或者32位客户端&#xff0c;以及database压缩包 2.解压后双击执行database文件夹下的setup.exe 3.详细的安装步骤 &#xff08;1&#xff09;数据库安装 一、配置安全更新 电子邮件可写可不写&#xf…...

Go模板后端渲染时vue单页面冲突处理

go后端模版语法是通过 {{}} &#xff0c;vue也是通过双花括号来渲染的&#xff0c;如果使用go渲染vue的html页面的时候就会报错&#xff0c;因为分别不出来哪个是vue的&#xff0c;哪个是go的&#xff0c;既可以修改go的模板语法 template.New("output").Delims(&qu…...

笔记本摄像头模拟监控推送RTSP流

使用笔记本摄像头模拟监控推送RTSP流 一、基础安装软件准备 本文使用软件下载链接:下载地址 FFmpeg软件: Download ffmpeg 选择Windows builds by BtbN 一个完整的跨平台解决方案&#xff0c;用于录制、转换和流式传输音频和视频。 EasyDarwin软件&#xff1a;Download Easy…...

鸿蒙开发已解决-ArkTS编译时遇到arkts-no-obj-literals-as-types错误

文章目录 项目场景:问题描述原因分析:解决方案:解决方案1解决方案2此Bug解决方案总结项目场景: 在开发鸿蒙项目过程中,遇到了arkts-no-obj-literals-as-types,总结了自己和网上人的解决方案,故写下这篇文章。 遇到问题: rkTS编译时遇到arkts-no-obj-literals-as-type…...

实现目标检测中的数据格式自由(labelme json、voc、coco、yolo格式的相互转换)

在进行目标检测任务中&#xff0c;存在labelme json、voc、coco、yolo等格式。labelme json是由anylabeling、labelme等软件生成的标注格式、voc是通用目标检测框&#xff08;mmdetection、paddledetection&#xff09;所支持的格式&#xff0c;coco是通用目标检测框&#xff0…...

一文读懂JVS逻辑引擎如何调用规则引擎:含详细步骤与场景示例

在当今的数字化时代&#xff0c;业务逻辑和规则的复杂性不断增加&#xff0c;这使得逻辑引擎和规则引擎在处理业务需求时显得尤为重要。逻辑引擎和规则引擎通过定义、解析和管理业务逻辑和规则&#xff0c;能够帮助企业提高工作效率、降低运营成本&#xff0c;并增强决策的科学…...

苹果应用上架是否需要软件著作权?

苹果应用上架是否需要软件著作权&#xff1f; 摘要 随着移动互联网的发展&#xff0c;苹果应用在市场上占据了很大份额。但是&#xff0c;很多开发者在上传苹果应用到App Store时&#xff0c;都会遇到一个问题&#xff0c;即是否需要进行软著申请&#xff1f;本文将深入探讨这…...

LDD学习笔记 -- Linux字符设备驱动

LDD学习笔记 -- Linux字符设备驱动 虚拟文件系统 VFS设备号相关Kernel APIs动态申请设备号动态创建设备文件内核空间和用户空间的数据交换系统调用方法readwritelseek 写一个伪字符设备驱动在主机上测试pcd(HOST)在目标板上测试pcd(TARGET) 字符驱动程序用于与Linux内核中的设备…...

杰理AC63串口收发实例

在event.h文件中预定义串口消息 #define DEVICE_EVENT_FROM_MY_UART ((M << 24) | (Y << 16) | (U << 8) | \0)在app_spp_and_le.c文件里对SYS_DEVICE_EVENT做处理&#xff0c;添加收到DEVICE_EVENT_FROM_MY_UART消息时的处理函数my_rx_handler(); cas…...

麦芯(MachCore)开发教程1 --- 设备软件中间件

黄国强 2024/1/10 acloud163.com 对任何公司来说&#xff0c;在短时间内开发一款高质量设备专用软件&#xff0c;是一件不太容易做到的事情。麦芯是笔者发明的一款设备软件中间件产品。麦芯致力于给设备厂商提供一个开发工具和平台&#xff0c;让客户快速高效的开发自己的设备专…...

reset命令

作用&#xff1a;将当前 HEAD 重置为指定状态 Git 的四个区域 Workspace&#xff1a;工作区&#xff0c;就是你平时存放项目代码的地方;Index / Stage&#xff1a;暂存区&#xff0c;用于临时存放你的改动&#xff0c;事实上它只是一个文件&#xff0c;保存即将提交到文件列表…...

Linux内核--进程管理(十二)LinuxIO基础知识与概念

目录 一、引言 二、IO基本概念 ------>2.1、内存空间划分 ------>2.2、读写操作 ------>2.3、用户态切换到内核态的3种方式 三、PIO&DMA ------>3.1、PIO 工作原理 ------>3.2、DMA 工作原理 四、缓冲IO和直接IO ------>4.1、缓冲 IO ------&…...

gem5学习(11):将缓存添加到配置脚本中——Adding cache to the configuration script

目录 一、Creating cache objects 1、Classic caches and Ruby 二、Cache 1、导入SimObject(s) 2、创建L1Cache 3、创建L1Cache子类 4、创建L2Cache 5、L1Cache添加连接函数 6、为L1ICache和L1DCache添加连接函数 7、为L2Cache添加内存侧和CPU侧的连接函数 完整代码…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...