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

【Leetcode 每日一题】368. 最大整除子集

news 来源：原创 2025/8/23 15:12:07

问题背景

给你一个由 无重复 正整数组成的集合 n u m s nums nums，请你找出并返回其中最大的整除子集 a n s w e r answer answer，子集中每一元素对 ( a n s w e r [ i ] , a n s w e r [ j ] ) (answer[i], answer[j]) (answer[i],answer[j]) 都应当满足：

  • a n s w e r [ i ] % a n s w e r [ j ] = 0 answer[i] \ \% \ answer[j] = 0 answer[i] % answer[j]=0，或
  • a n s w e r [ j ] % a n s w e r [ i ] = 0 answer[j] \ \% \ answer[i] = 0 answer[j] % answer[i]=0
    如果存在多个有效解子集，返回其中任何一个均可。

数据约束

  • 1 ≤ n u m s . l e n g t h ≤ 1000 1 \le nums.length \le 1000 1≤nums.length≤1000
  • 1 ≤ n u m s [ i ] ≤ 2 × 1 0 9 1 \le nums[i] \le 2 \times 10 ^ 9 1≤nums[i]≤2×109
  • n u m s nums nums 中的所有整数 互不相同

解题过程

生成答案的过程，应当是在已经形成的子集中尝试添加新元素，最终结果是从规模更小的解转移而来，用动态规划解决，类似 最长递增子序列。

具体实现

class Solution {public List<Integer> largestDivisibleSubset(int[] nums) {Arrays.sort(nums);int n = nums.length;int[] memo = new int[n];int[] from = new int[n];Arrays.fill(from, -1);int res = 0;int index = 0;for (int i = 0; i < n; i++) {int cur = dfs(i, nums, memo, from);if (cur > res) {res = cur;index = i;}}List<Integer> path = new ArrayList<>(res);for (int i = index; i >= 0; i = from[i]) {path.add(nums[i]);}return path;}private int dfs(int i, int[] nums, int[] memo, int[] from) {if (memo[i] > 0) {return memo[i];}int res = 0;for (int j = 0; j < i; j++) {if (nums[i] % nums[j] != 0) {continue;}int cur = dfs(j, nums, memo, from);if (cur > res) {res = cur;from[i] = j;}}return memo[i] = res + 1;}
}

相关文章：

【Leetcode 每日一题】368. 最大整除子集

问题背景 给你一个由 无重复 正整数组成的集合 n u m s nums nums&#xff0c;请你找出并返回其中最大的整除子集 a n s w e r answer answer&#xff0c;子集中每一元素对 ( a n s w e r [ i ] , a n s w e r [ j ] ) (answer[i], answer[j]) (answer[i],answer[j]) 都应当…...

编程日记 2025/8/23 15:12:07

python三大库之---pandas（二）

python三大库之—pandas&#xff08;二&#xff09; 文章目录 python三大库之---pandas&#xff08;二&#xff09;六&#xff0c;函数6.1、常用的统计学函数6.2重置索引 六&#xff0c;函数 6.1、常用的统计学函数 函数名称描述说明count()统计某个非空值的数量sum()求和mea…...

编程日记 2025/8/23 15:12:06

消防车调度问题：基于Matlab的优化求解

摘要 本文聚焦消防车调度问题&#xff0c;介绍如何将其转化为数学模型并利用Matlab进行求解。通过建立损失矩阵&#xff0c;以总损失最小为目标构建线性规划模型&#xff0c;并针对模型求解结果可能出现的不合理情况&#xff0c;增加消防车到达先后次序约束条件。 关键词&…...

编程日记 2025/8/23 15:12:03

批量将 Markdown 转换为 Word/PDF 等其它格式

在工作当中&#xff0c;我们经常会接触到 Markdown 格式的文档。这是一种非常方便我们做记录&#xff0c;做笔记的一种格式文档。现在很多互联网编辑器都是支持 Markdown 格式的&#xff0c;编辑起文章来更加的方便简介。有时候&#xff0c;我们会碰到需要将 Markdown 格式的文…...

编程日记 2025/8/23 13:09:41

C语言学习笔记-9

九、结构体 构造类型&#xff1a; 不是基本类型的数据结构也不是指针类型&#xff0c; 它是若干个相同或不同类型的数据构成的集合 结构体类型&#xff1a; 结构体是一种构造类型的数据结构&#xff0c;是一种或多种基本类型或构造类型的数据的集合。 1.结构体类型定义 定…...

编程日记 2025/8/21 19:08:02

LLM 部署(1)——LLM 部署框架对比

1 Ollama 一个专注于简化大型语言模型&#xff08;LLM&#xff09;在本地部署和运行的开源框架。 简化部署&#xff1a;Ollama使用Docker容器技术来简化LLM的部署过程 捆绑模型组件&#xff1a;Ollama将模型权重、配置和数据捆绑到一个包中&#xff0c;称为Modelfile&#xf…...

编程日记 2025/8/21 18:58:15

Qt坐标体系，控件坐标的设置

Qt窗口坐标体系---平面直角坐标系&#xff08;笛卡尔坐标系&#xff09; 以左上角为0&#xff0c;0坐标原点 给Qt的某个控件&#xff0c;设置位置&#xff0c;就需要指定坐标&#xff0c;对应这个控件来说&#xff0c;坐标系原点就是相对于父控件的 如&#xff1a; QPushButt…...

编程日记 2025/8/18 23:52:38

大数据系列之：Kerberos

大数据系列之&#xff1a;Kerberos 基本概念工作流程安全特性应用场景总结加密原理Kerberos认证流程更改您的密码授予账户访问权限票证管理Kerberos 票据属性使用 kinit 获取票据使用 klist 查看票据使用 kdestroy 销毁票据.k5identity 文件描述 Kerberos 是一种网络认证协议&a…...

编程日记 2025/8/20 9:04:15

【力扣hot100题】（059）单词搜索

这道题给我最大的启示就是不要什么时候都用哈希表&#xff0c;偶尔也要用用数组…… 是这样&#xff0c;一开始还沾沾自喜的以为知道了哈希表的自己一定可以比以前傻傻用数组的我要节省空间&#xff0c;结果发现哈希表不能存储pair用编号存储会时间超限用数组只需要7*7的空间。…...

编程日记 2025/8/20 19:17:37

Java全栈面试宝典：锁机制与Spring生命周期深度解析

目录 一、synchronized锁状态机全解析 &#x1f525; 问题5&#xff1a;synchronized四态转换与性能对比 锁状态转换流程图 锁特性对比表 CAS操作示例 二、ReentrantLock与synchronized深度对比 &#x1f525; 问题6&#xff1a;两大锁机制对比 核心差异矩阵 生产级Re…...

编程日记 2025/8/17 19:45:52

15分钟完成Odoo18.0安装与基本配置

序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo18发行已半年有余&#xff0c;不少企业也已上至生产环境进行使用了。今天我们来看看 Odoo18的安装。 本次安装我们介绍通过阿里云服务器安装Odoo18社区版。 1.服务器准备 1.1操作系统 操作系统使用ubuntu22.04&#xff…...

编程日记 2025/8/17 19:32:14

pom导包成功，但是就是无法使用相关类，同时报错：Library:Maven ‘xxx‘ has broken path

开发环境&#xff1a;Intellij 2023 一、问题记录 在maven工程的pom文件导入如下某一依赖(JGit)。没有显示导包的错误&#xff0c;同时在maven仓库里面找到对应的包是正常下载到相应jar的。 但是就是无法引入相关的类。打开Project Structure&#xff0c;在Dependencies中发现…...

编程日记 2025/8/19 14:38:21

Cocos Creator 进行 Web 发布后，目录结构解析

在使用 Cocos Creator 进行 Web 发布后&#xff0c;生成的目录结构通常包含以下内容&#xff0c;下面为你详细介绍&#xff1a; 1. index.html 这是 Web 项目的入口 HTML 文件&#xff0c;它会加载所需的 JavaScript 文件和资源&#xff0c;从而启动游戏或应用程序。示例代码…...

编程日记 2025/8/21 2:42:34

Linux-磁盘管理

文章目录 1、查看磁盘和文件&#xff08;夹&#xff09;使用情况2、磁盘分区1&#xff09;查看分区情况2&#xff09;MBR分区3&#xff09;GPT分区 3、磁盘分区格式化4、磁盘挂载1&#xff09;挂载2&#xff09;卸载挂载点3&#xff09;永久挂载 1、查看磁盘和文件&#xff08;…...

编程日记 2025/8/21 6:00:17

P1149 [NOIP 2008 提高组] 火柴棒等式（DFS）

题目描述 给你 n 根火柴棍&#xff0c;你可以拼出多少个形如 ABC 的等式&#xff1f;等式中的 A、B、C 是用火柴棍拼出的整数&#xff08;若该数非零&#xff0c;则最高位不能是 0&#xff09;。用火柴棍拼数字 0∼9 的拼法如图所示&#xff1a; 注意&#xff1a; 加号与等号…...

编程日记 2025/8/22 8:02:47

机器学习新范式：Kubernetes + Kubeflow，解锁模型训练与部署的高效密码

一、Kubernetes在机器学习模型训练与部署中的作用 Kubernetes作为一个强大的容器编排平台&#xff0c;为机器学习模型的训练与部署提供了以下核心支持&#xff1a; 分布式训练支持&#xff1a;Kubernetes能够自动化部署和管理PyTorch等机器学习框架的分布式训练任务。通过利用…...

编程日记 2025/8/20 10:11:53

testflight上架ipa包-只有ipa包的情况下如何修改签名信息为苹果开发者账户对应的信息-ipa苹果包如何手动改签或者第三方工具改签-优雅草卓伊凡

testflight上架ipa包-只有ipa包的情况下如何修改签名信息为苹果开发者账户对应的信息-ipa苹果包如何手动改签或者第三方工具改签-优雅草卓伊凡 直接修改苹果IPA包的签名和打包信息并不是一个推荐的常规做法&#xff0c;因为这可能违反苹果的开发者条款&#xff0c;并且可能导致…...

编程日记 2025/8/21 19:23:12

SpringSecurity框架入门

简介 官网 Spring Security是一个Java框架&#xff0c;用于保护应用程序的安全性。它提供了一套全面的安全解决方案&#xff0c;包括身份验证、授权、防止攻击等功能。Spring Security基于过滤器链的概念&#xff0c;可以轻松地集成到任何基于Spring的应用程序中。它支持多种…...

编程日记 2025/8/18 1:20:03

AIDD-人工智能药物设计-双扩散模型结合多目标优化策略助力3D小分子药物设计

Adv. Sci. | 双扩散模型结合多目标优化策略助力3D小分子药物设计 药物发现中，如何精准且高效地设计具有理想物理化学性质的潜在药物分子，对当前的研究水平来说仍然是一项重大挑战。近年来，基于深度学习的全新分子生成（de novo molecular generation）方法取得了显著进展，…...

编程日记 2025/8/19 22:45:12

Python面向对象编程 - 接口隔离原则(ISP)

1. 原则定义 接口隔离原则(Interface Segregation Principle, ISP) 是SOLID原则中的"I"&#xff0c;核心思想是&#xff1a; 客户端不应该被迫依赖它们不使用的接口 即&#xff1a;多个特定功能的接口比一个通用接口更好 2. 核心思想 将臃肿的接口拆分为更小、更具…...

编程日记 2025/8/21 15:45:28

mac安装浏览器闪退处理

安装 Chrome或edge后打开浏览器出现闪退&#xff0c;是因为权限不够。 以下是针对edge的处理方法。 sudo chown -R $(whoami) ~/Library/Application\ Support/Microsoft\ Edge sudo chmod -R 755 ~/Library/Application\ Support/Microsoft\ Edge 原因分析&#xff1a; 在…...

编程日记 2025/8/21 1:38:00

408 计算机网络 知识点记忆（5）

前言 本文基于王道考研课程与湖科大计算机网络课程教学内容&#xff0c;系统梳理核心知识记忆点和框架&#xff0c;既为个人复习沉淀思考&#xff0c;亦希望能与同行者互助共进。&#xff08;PS&#xff1a;后续将持续迭代优化细节&#xff09; 往期内容 408 计算机网络 知识…...

编程日记 2025/8/22 1:14:37

Java面试黄金宝典38

1. TIME_WAIT 和 CLOSE_WAIT 的区别 定义 TIME_WAIT：是主动发起关闭连接操作的一方，在发送最后一个 ACK 确认包之后进入的状态。此状态存在的意义在于确保对端能收到最后一个 ACK 包，同时让网络中可能残留的旧数据包自然消逝，防止其干扰后续相同四元组（源 IP、源端口、目…...

编程日记 2025/8/20 15:40:56

【算法】筛质数

目录 埃氏筛法算法原理代码 欧拉筛法算法原理代码 埃氏筛法 算法原理 算法思想就像"筛子"一样&#xff0c;把合数筛掉&#xff0c;剩下的就是质数&#xff1a; 从2开始&#xff0c;依次检查每个数如果当前数未被标记为合数&#xff0c;它就是质数然后把这个质数的…...

编程日记 2025/8/22 18:25:21

【IDEA】✈️自定义模板，自动生成类和方法注释

&#x1f4a5;&#x1f4a5;✈️✈️欢迎阅读本文章❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;本篇文章阅读大约耗时三分钟。 ⛳️motto&#xff1a;不积跬步、无以千里 &#x1f4cb;&#x1f4cb;&#x1f4cb;本文目录如下&#xff1a;&#x1f381;&#x1f381;&a…...

编程日记 2025/8/21 7:54:24

笔试专题（六）

文章目录 最长无重复子数组&#xff08;滑动窗口&#xff09;题解代码 重排字符串&#xff08;贪心 构造&#xff09;题解代码 牛牛冲钻五&#xff08;模拟&#xff09;题解代码 最长无重复子数组&#xff08;滑动窗口&#xff09; 题目链接 题解 1. 滑动窗口 2. 什么时候…...

编程日记 2025/8/20 19:08:29

【算法实践】跳跃游戏——计算到达终点的最小跳数

问题描述 给定一个非负数数组 arr[]&#xff0c;每个元素表示从该位置最多可向前跳跃的步数。 示例&#xff1a; 若 arr[i] 3&#xff0c;则可以从位置 i 跳跃到 i1、i2 或 i3。若 arr[i] 0&#xff0c;则无法从该位置向前跳跃。 任务&#xff1a;找到从数组第一个位置移动…...

编程日记 2025/8/22 2:28:09

sklearn的Pipeline

Pipeline类 介绍：Pipeline 可以将多个数据处理步骤和机器学习模型组合成一个序列，其中每个步骤都是一个变换器（Transformer）或者估计器（Estimator），并且Pipeline中的最后一个必须为估计器，其它的必须为变换器，如果Pipeline中的估计器为为分类器则整个Pipeline就作为分…...

编程日记 2025/8/19 7:34:10

Unity3D仿星露谷物语开发34之单击Drop项目

1、目标 当在道具栏中选中一个Item时&#xff0c;点击地面就可以实现Item的drop操作&#xff0c;每点击一次就drop一次&#xff0c;直到道具栏中Item数量不够。 这样的好处&#xff1a;避免每次Drop都从道具栏中拖拉Item&#xff0c;通过点击这种操作可以更加高效。 方法&am…...

编程日记 2025/8/17 9:38:42

每日一题（小白）回溯篇4

深度优先搜索题&#xff1a;找到最长的路径&#xff0c;计算这样的路径有多少条&#xff08;使用回溯&#xff09; 分析题意可以得知&#xff0c;每次向前后左右走一步&#xff0c;直至走完16步就算一条走通路径。要求条件是不能超出4*4的范围&#xff0c;不能重复之前的路径。…...

编程日记 2025/8/18 0:08:09

Day16——路由2

路由独有的两个生命周期钩子 作用&#xff1a;用于捕获路由组件的激活状态 具体名字&#xff1a; activated 路由组件被激活时触发 deactivated 路由组件失活时触发 现在在缓存路由组件的基础上,想要使h2中的文字透明度不断变化&#xff0c;在切换到别的组件时销毁控制文字不…...

编程日记 2025/8/20 9:00:10

iproute2 工具集使用详解

目录 一、iproute2 核心命令&#xff1a;ip二、常用功能详解1. 管理网络接口&#xff08;link 对象&#xff09;2. 管理 IP 地址&#xff08;address 对象&#xff09;3. 管理路由表&#xff08;route 对象&#xff09;4. 管理 ARP 和邻居缓存&#xff08;neigh 对象&#xff0…...

编程日记 2025/8/19 20:04:22

C++学习之套接字并发服务器

目录 1.昨天套接字服务器的弊端 2.如何通过多进程方式实现服务器并发 3.多进程服务器-1 4.多进程服务器-2 5.多进程版程序-回收子进程被信号中断的处理 6.多线程版TCP服务处理思路 7.多线程并发服务器编写 8.为什么不能把文件描述符地址传到子线程中 9.多线程程序测试 …...

编程日记 2025/8/19 2:55:06

MCP项目开发-一个简单的RAG示例

MCP项目开发-一个简单的RAG示例 前言 前言 客户端是基于官网的例子改的&#xff0c;模型改成了openai库连接仅仅使用基础的RAG流程作为一个演示&#xff0c;包含了以下步骤 query改写搜索&#xff1a;使用google serper重排序&#xff1a;使用硅基流动的api 大模型api也使用…...

编程日记 2025/8/22 11:43:19

Windows安装ssh服务

使用管理员权限打开Windows PowerShell Add-WindowsCapability -Online -Name OpenSSH.Server~~~~0.0.1.0启动服务 Start-Service sshd 设置开机自启 Set-Service sshd -StartupType Automatic允许22端口 New-NetFirewallRule -Name “SSH” -DisplayName “SSH” -Enabled Tr…...

编程日记 2025/8/21 8:35:24

从零实现本地大模型RAG部署

1. RAG概念 RAG&#xff08;Retrieval-Augmented Generation&#xff09;即检索增强生成&#xff0c;是一种结合信息检索与大型语言模型&#xff08;大模型&#xff09;的技术。从外部知识库&#xff08;如文档、数据库或网页&#xff09;中实时检索相关信息&#xff0c;并将其…...

编程日记 2025/8/17 23:57:51

什么是ThreadLocal

ThreadLocal 是 Java 提供的一个工具类&#xff0c;它为每一个使用该变量的线程都提供了一个独立的变量副本。换句话说&#xff1a;每个线程都有自己的本地变量副本、互不干扰。它不是用来共享数据的&#xff0c;而是用来隔离数据的。 一、为什么需要 ThreadLocal&#xff1f;…...

编程日记 2025/8/19 2:27:33

MySQL-SQL-DQL语句、DQL基本查询、DQL条件查询、DQL分组查询、聚合函数、DQL排序查询、DQL分页查询

一. DQL DQL&#xff1a;Data Query Language(数据查询语言)&#xff0c;用来查询数据库表中的记录。 关键字&#xff1a;SELETE -- DQL 完整语法select字段列表 from表名列表 where条件列表 group by分组字段列表 having分组后条件列表 order by排序字段列表 limit分页参数 …...

编程日记 2025/8/20 22:10:44

vue2 vue3 响应式差异

vue2 响应式原理看这 链接: link 总结&#xff1a; object.defineproperty()是对属性的劫持&#xff0c;对属性劫持有两大缺陷 1. 需要遍历对象的所有属性&#xff0c;深层属性需递归&#xff0c;存在效率问题 2. 后添加的属性&#xff0c;无法获得响应式&#xff0c;因为劫持…...

编程日记 2025/8/18 0:27:17

常见NLP模型发展脉络：从传统方法到大语言模型

自然语言处理作为人工智能领域的重要分支&#xff0c;经历了从传统统计方法到深度学习的巨大飞跃。本文将带你梳理NLP模型的发展脉络&#xff0c;回顾那些推动技术进步的重要里程碑。 一、统计学习阶段&#xff08;1990s-2010s初&#xff09; 早期的NLP模型主要基于统计方法&…...

编程日记 2025/8/18 0:28:32

Bert论文解析

文章目录 BERT&#xff1a;用于语言理解的深度双向转换器的预训练一、摘要三、BERT介绍BERT及其详细实现答疑&#xff1a;为什么没有标注的数据可以用来预训练模型&#xff1f;1. 掩码语言模型&#xff08;Masked Language Model, MLM&#xff09;2. 下一句预测&#xff08;Nex…...

编程日记 2025/8/17 22:27:39

【数学】勒让德定理（legendres-formula）详解

勒让德定理&#xff08;Legendre’s Formula&#xff09;详解 这段代码使用的数学原理是勒让德定理&#xff0c;它是计算质数p在n!的质因数分解中指数的核心方法。 一、定理内容 对于任意质数p和正整数n&#xff0c;p在n!的质因数分解中的指数&#xff08;即n!能被p整除的最…...

编程日记 2025/8/22 5:12:23

时空联合规划算法

本文主要讲解时空时空联合规划算法。 文章目录 前言一、时空联合规划基本概念1.1 EM Planner算法求解过程1.2 时空联合规划算法求解过程二、基于搜索的规划方法2.1 构建三维时空联合规划地图2.2 基于Hybrid A*的时空联合规划二、基于迭代搜索的规划方法2.1 这段时间更新中2.2 这…...

编程日记 2025/8/19 15:50:37

如何在idea中新建一个项目

Java通常展现的方式就是项目&#xff0c;但是在不熟悉idea的情况下&#xff0c;我们应该如何创建一个项目呢&#xff1f; 第一步&#xff1a;点击File-->New-->Project 第二步&#xff1a;选择 Empty Project 第三步&#xff1a;点击File-->找到Project Structure--&…...

编程日记 2025/8/19 21:27:07

设计模式简述（十三）适配器模式

适配器模式 描述基本使用使用关于适配器关联不兼容类的方式如果原有抽象层是抽象类若原有抽象是接口使用 描述 适配器模式常用于系统已经上限稳定运行&#xff0c;但现有需求需要将两个不匹配的类放到一起工作时使用。 也就是说这是一个迭代阶段使用的模式。 这种模式&#x…...

编程日记 2025/8/19 7:49:05

功耗日志抓取需求

最近罗列了一些功耗分析需要的常见日志&#xff1a; 测试功耗前&#xff1a; adb shell dumpsys batterystats --reset adb shell dumpsys batterystats --enable full-wake-history 测试功耗后&#xff0c;使用脚本导出如下功耗日志&#xff1a; 脚本 chmod x collect_logs.s…...

编程日记 2025/8/21 23:32:51

设计模式简述（十一）装饰器模式

装饰器模式 描述基本使用使用 描述 装饰器模式是一种功能型模式 用于动态增强对象的功能 这么一说感觉上和代理模式有些类似 抽象装饰器 要实现原有业务接口&#xff0c;并注入原有业务对象 至于对原有业务对象的调用&#xff0c;可以采用private业务对象 实现业务接口方法的…...

编程日记 2025/8/20 19:03:54

MongoDB基础知识

MongoDB基础知识 目录 基础篇 一、MongoDB入门指南&#xff08;零基础必读&#xff09;二、MongoDB简介三、MongoDB安装与配置四、MongoDB基本操作五、MongoDB查询操作 进阶篇 六、MongoDB索引七、MongoDB聚合操作八、MongoDB数据模型九、MongoDB安全十、MongoDB备份恢复十一…...

编程日记 2025/8/22 12:56:29

Kubernetes详细教程（一）：入门、架构及基本概念

Kubernetes&#xff08;常简称为K8s&#xff09;是一个开源的平台&#xff0c;用于自动化部署、扩展和管理容器化应用程序。 官方文档&#xff1a;https://kubernetes.io/zh-cn/docs/concepts/overview/components/ 一、入门 &#xff08;一&#xff09;Kubernetes是什么&am…...

编程日记 2025/8/21 17:59:08

架构思维：限流技术深度解析

文章目录 Pre业务场景熔断 VS 限流4大限流算法固定时间窗口计数滑动时间窗口计数漏桶令牌桶 方案实现使用令牌桶还是漏桶模式&#xff1f;在 Nginx 中实现限流还是在网关层中实现限流&#xff1f;使用分布式限流还是单机限流&#xff1f;使用哪个开源技术&#xff1f; 限流方案…...

编程日记 2025/8/23 11:22:11