当前位置: 首页 > 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侧的连接函数 完整代码…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...