Leetcode 3444. Minimum Increments for Target Multiples in an Array
- Leetcode 3444. Minimum Increments for Target Multiples in an Array
- 1. 解题思路
- 2. 代码实现
- 题目链接:3444. Minimum Increments for Target Multiples in an Array
1. 解题思路
这一题我的思路上就是一个深度优先遍历,考察target数组当中的每一个元素的全部倍数被出现的情况下,最少需要多少次操作,以及同时能够满足多少剩余的target数组中的数字,然后持续迭代考察,取其中的最小值。
同时,考虑到时间复杂度的因素,我们将结果用一个全局变量存下来,一旦某一步的结果超过了已知可行的最大操作数,就直接退出递归,从而进行剪枝。
2. 代码实现
给出最终的python代码实现如下:
class Solution:def minimumIncrements(self, nums: List[int], target: List[int]) -> int:nums, target = sorted(nums), sorted(target, reverse=True)n, m = len(nums), len(target)status = [0 for _ in range(m)]ans = math.infdef dfs(idx, nums, status):nonlocal ansif idx >= m:return 0elif status[idx] == 1:return dfs(idx+1, nums, status)need = math.inftgt = 0while tgt < nums[-1]:tgt += target[idx]old_status = deepcopy(status)for i, x in enumerate(target):if status[i] == 1 or tgt % x == 0:status[i] = 1i = bisect.bisect_right(nums, tgt)if i > 0:num = nums.pop(i-1)if abs(num-tgt) < ans:need = min(need, abs(num-tgt) + dfs(idx+1, nums, status))nums.insert(i-1, num)status = old_statusif need >= ans:return math.infif idx == 0:ans = needreturn needdfs(0, nums, status)return ans
提交代码评测得到:耗时12ms,占用内存21.3MB。
相关文章:
Leetcode 3444. Minimum Increments for Target Multiples in an Array
Leetcode 3444. Minimum Increments for Target Multiples in an Array 1. 解题思路2. 代码实现 题目链接:3444. Minimum Increments for Target Multiples in an Array 1. 解题思路 这一题我的思路上就是一个深度优先遍历,考察target数组当中的每一个…...
分享半导体Fab 缺陷查看系统,平替klarity defect系统
分享半导体Fab 缺陷查看系统,平替klarity defect系统;开发了半年有余。 查看Defect Map,Defect image,分析Defect size,defect count trend. 不用再采用klarity defect系统(license 太贵) 也可以…...
Java基础——分层解耦——IOC和DI入门
目录 三层架构 Controller Service Dao 编辑 调用过程 面向接口编程 分层解耦 耦合 内聚 软件设计原则 控制反转 依赖注入 Bean对象 如何将类产生的对象交给IOC容器管理? 容器怎样才能提供依赖的bean对象呢? 三层架构 Controller 控制…...
DeepSeek-R1 本地部署教程(超简版)
文章目录 一、DeepSeek相关网站二、DeepSeek-R1硬件要求三、本地部署DeepSeek-R11. 安装Ollama1.1 Windows1.2 Linux1.3 macOS 2. 下载和运行DeepSeek模型3. 列出本地已下载的模型 四、Ollama命令大全五、常见问题解决附:DeepSeek模型资源 一、DeepSeek相关网站 官…...
Vue3学习笔记-模板语法和属性绑定-2
一、文本插值 使用{ {val}}放入变量,在JS代码中可以设置变量的值 <template><p>{{msg}}</p> </template> <script> export default {data(){return {msg: 文本插值}} } </script> 文本值可以是字符串,可以是布尔…...
csapp笔记3.6节——控制(1)
本节解决了x86-64如何实现条件语句、循环语句和分支语句的问题 条件码 除了整数寄存器外,cpu还维护着一组单个位的条件码寄存器,用来描述最近的算数和逻辑运算的某些属性。可检测这些寄存器来执行条件分支指令。 CF(Carry Flag)…...
PYH与MAC的桥梁MII/MIIM
在学习车载互联网时,看到了一句话,Processor通过DMA直接存储访问与MAC之间进行数据的交互,MAC通过MII介质无关接口与PHY之间进行数据的交互。常见的以太网硬件结构是,将MAC集成进Processor芯片,将PHY留在Processor片外…...
国内flutter环境部署(记录篇)
设置系统环境变量 export PUB_HOSTED_URLhttps://pub.flutter-io.cn export FLUTTER_STORAGE_BASE_URLhttps://storage.flutter-io.cn使用以下命令下载flutter镜像 git clone -b stable https://mirror.ghproxy.com/https://github.com/<github仓库地址>#例如flutter仓…...
选择排序_75. 颜色分类
75. 颜色分类 - 力扣(LeetCode) 题目不追求稳定 可以选择选择排序 这是我没看教程代码之前写的 有点复杂了 我还把元素后移了 class Solution { public:void sortColors(vector<int>& nums) {int min_num_index -1;int min_num 3;for(int i…...
C++ Primer 标准库vector
欢迎阅读我的 【CPrimer】专栏 专栏简介:本专栏主要面向C初学者,解释C的一些基本概念和基础语言特性,涉及C标准库的用法,面向对象特性,泛型特性高级用法。通过使用标准库中定义的抽象设施,使你更加适应高级…...
C# 数组和列表的基本知识及 LINQ 查询
数组和列表的基本知识及 LINQ 查询 一、基本知识二、引用命名空间声明三、数组3.1、一维数组3.2、二维数组3.3、不规则数组 Jagged Array 四、列表 List4.1、一维列表4.2、二维列表 五、数组和列表使用 LINQ的操作和运算5.1、一维 LIST 删除所有含 double.NaN 的行5.2、一维 LI…...
大厂面试题备份20250201
20250201 面试策略 如果三面往后遇到传说中让人忍受不了的业余面试官,就舔着苟过去,入职大概率见不着他,但一二面遇到,反问环节就主动说不够match,让释放流程。 机器/深度学习 百面机器学习 5.4 通用CS 计算机网…...
w191教师工作量管理系统的设计与实现
🙊作者简介:多年一线开发工作经验,原创团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹赠送计算机毕业设计600个选题excel文…...
Git 版本控制:基础介绍与常用操作
目录 Git 的基本概念 Git 安装与配置 Git 常用命令与操作 1. 初始化本地仓库 2. 版本控制工作流程 3. 分支管理 4. 解决冲突 5. 回退和撤销 6. 查看提交日志 前言 在软件开发过程中,开发者常常需要在现有程序的基础上进行修改和扩展。但如果不加以管理&am…...
讲清逻辑回归算法,剖析其作为广义线性模型的原因
1、逻辑回归算法介绍 逻辑回归(Logistic Regression)是一种广义线性回归分析模型。虽然名字里带有“回归”两字,但其实是分类模型,常用于二分类。既然逻辑回归模型是分类模型,为什么名字里会含有“回归”二字呢?这是因为其算法原…...
数据结构(1)——算法时间复杂度与空间复杂度
目录 前言 一、算法 1.1算法是什么? 1.2算法的特性 1.有穷性 2.确定性 3.可行性 4.输入 5.输出 二、算法效率 2.1衡量算法效率 1、事后统计方法 2、事前分析估计方法 2.2算法的复杂度 2.3时间复杂度 2.3.1定义 2.3.2大O渐进表示法 2.3.3常见时间复…...
K8s运维管理平台 - xkube体验:功能较多
目录 简介Lic安装1、需要手动安装MySQL,**建库**2、启动命令3、[ERROR] GetNodeMetric Fail:the server is currently unable to handle the request (get nodes.metrics.k8s.io qfusion-1) 使用总结优点优化 补充1:layui、layuimini和beego的详细介绍1.…...
spring源码阅读系列文章目录
对于spring认识首先要了解 spring相关概念术语,然后是如下的几句话牢记并反射出来: Bean怎么来的,通过BeanDefinitionBeanDefinition有Spring框架内置的,有手动定义或者自动配置扫描出来的(写个Demo工程)B…...
快速提升网站收录:利用网站新闻发布功能
本文转自:百万收录网 原文链接:https://www.baiwanshoulu.com/63.html 利用网站新闻发布功能快速提升网站收录是一个有效的策略。以下是一些具体的建议,帮助你更好地利用这一功能: 一、保持新闻更新频率 搜索引擎尤其重视网站的…...
【14】WLC3504 HA配置实例
1.概述 本文档使用 Cisco WLC 3504 实现无线控制器的高可用性。这里所指的HA是指WLC设备box-to-box的冗余。换句话说,即1:1的设备冗余,其中一个 WLC 将处于Active活动状态,而第二个 WLC 将处于Standby-hot热待机状态,通过RP冗余端口持续监控活动 WLC 的运行状况。两个 WLC…...
再也不怕消息被撤回!Windows防撤回工具完全使用指南
再也不怕消息被撤回!Windows防撤回工具完全使用指南 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁(我已经看到了,撤回也没用了) 项目地址: https://gitcode.com/…...
UE后期处理材质实战:从黑白蒙版到卡通渲染的进阶应用
1. 黑白蒙版遮罩的底层原理与应用 在UE4后期处理材质中,黑白蒙版遮罩是最基础也最实用的功能之一。我第一次接触这个功能时,被它强大的选择性处理能力惊艳到了——它能像手术刀一样精准地分离出场景中的特定物体。 核心原理其实很简单:通过Sc…...
技术揭秘:SillyTavern角色卡片系统的架构设计与实战应用
技术揭秘:SillyTavern角色卡片系统的架构设计与实战应用 【免费下载链接】SillyTavern LLM Frontend for Power Users. 项目地址: https://gitcode.com/GitHub_Trending/si/SillyTavern 在AI角色扮演领域,如何将复杂的角色数据与视觉形象完美融合…...
深入Fast DDS传输层:从UDP、TCP到共享内存,如何为你的ROS2应用选择最佳通信方式?
Fast DDS传输层深度解析:UDP、TCP与共享内存的工程实践指南 在分布式系统架构中,通信中间件的性能直接影响整个系统的响应速度和可靠性。作为ROS 2的默认通信中间件,Fast DDS提供了多种传输协议选择,但如何根据实际场景做出最优决…...
Wan2.2-I2V-A14B在微信小程序开发中的应用:实时图片转视频功能实现
Wan2.2-I2V-A14B在微信小程序开发中的应用:实时图片转视频功能实现 1. 引言 "一张照片能变成视频吗?"这是很多社交类小程序用户常有的疑问。想象一下,用户在电商小程序上传商品图片后,系统自动生成一段展示视频&#…...
location-to-phone-number:如何将电话号码转化为商业智能的地理信息平台
location-to-phone-number:如何将电话号码转化为商业智能的地理信息平台 【免费下载链接】location-to-phone-number This a project to search a location of a specified phone number, and locate the map to the phone number location. 项目地址: https://gi…...
163MusicLyrics:双平台歌词提取的终极解决方案
163MusicLyrics:双平台歌词提取的终极解决方案 【免费下载链接】163MusicLyrics Windows 云音乐歌词获取【网易云、QQ音乐】 项目地址: https://gitcode.com/GitHub_Trending/16/163MusicLyrics 你是否曾为寻找一首心爱歌曲的完整歌词而辗转多个平台…...
别再纠结硬件滚动了!用Arduino+SSD1306库实现超长文本的软件滚动显示(附完整代码)
ArduinoSSD1306实现超长文本流畅滚动的终极方案 当你在创客项目中需要显示超出屏幕宽度的日志数据或长消息时,硬件滚动的局限性就会暴露无遗。我曾在一个环境监测项目中遇到这个问题——传感器数据经常超过OLED屏幕的16字符显示限制,硬件滚动方案直接截断…...
FPGA设计中的组合逻辑环:为什么你的Verilog代码会引发警告?
FPGA设计中的组合逻辑环:为什么你的Verilog代码会引发警告? 在数字电路设计的浩瀚海洋中,组合逻辑环(Combinational Loop)就像是一个潜伏的暗礁,看似无害却可能让你的整个设计"触礁沉没"。作为一…...
【Django 实验三】个人主页开发实战
【Django 实验三】个人主页开发实战 作者:刘静怡 | 学号:F23016208 | 完成日期:2026年3月29日 目录 环境准备项目创建数据模型设计视图函数编写模板系统Admin 后台配置页面美化功能完善总结 一、环境准备 1.1 环境要求 Python: 3.10Django…...
