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

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. 代码实现 题目链接&#xff1a;3444. Minimum Increments for Target Multiples in an Array 1. 解题思路 这一题我的思路上就是一个深度优先遍历&#xff0c;考察target数组当中的每一个…...

分享半导体Fab 缺陷查看系统,平替klarity defect系统

分享半导体Fab 缺陷查看系统&#xff0c;平替klarity defect系统&#xff1b;开发了半年有余。 查看Defect Map&#xff0c;Defect image&#xff0c;分析Defect size&#xff0c;defect count trend. 不用再采用klarity defect系统&#xff08;license 太贵&#xff09; 也可以…...

Java基础——分层解耦——IOC和DI入门

目录 三层架构 Controller Service Dao ​编辑 调用过程 面向接口编程 分层解耦 耦合 内聚 软件设计原则 控制反转 依赖注入 Bean对象 如何将类产生的对象交给IOC容器管理&#xff1f; 容器怎样才能提供依赖的bean对象呢&#xff1f; 三层架构 Controller 控制…...

DeepSeek-R1 本地部署教程(超简版)

文章目录 一、DeepSeek相关网站二、DeepSeek-R1硬件要求三、本地部署DeepSeek-R11. 安装Ollama1.1 Windows1.2 Linux1.3 macOS 2. 下载和运行DeepSeek模型3. 列出本地已下载的模型 四、Ollama命令大全五、常见问题解决附&#xff1a;DeepSeek模型资源 一、DeepSeek相关网站 官…...

Vue3学习笔记-模板语法和属性绑定-2

一、文本插值 使用{ {val}}放入变量&#xff0c;在JS代码中可以设置变量的值 <template><p>{{msg}}</p> </template> <script> export default {data(){return {msg: 文本插值}} } </script> 文本值可以是字符串&#xff0c;可以是布尔…...

csapp笔记3.6节——控制(1)

本节解决了x86-64如何实现条件语句、循环语句和分支语句的问题 条件码 除了整数寄存器外&#xff0c;cpu还维护着一组单个位的条件码寄存器&#xff0c;用来描述最近的算数和逻辑运算的某些属性。可检测这些寄存器来执行条件分支指令。 CF&#xff08;Carry Flag&#xff09…...

PYH与MAC的桥梁MII/MIIM

在学习车载互联网时&#xff0c;看到了一句话&#xff0c;Processor通过DMA直接存储访问与MAC之间进行数据的交互&#xff0c;MAC通过MII介质无关接口与PHY之间进行数据的交互。常见的以太网硬件结构是&#xff0c;将MAC集成进Processor芯片&#xff0c;将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. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; 题目不追求稳定 可以选择选择排序 这是我没看教程代码之前写的 有点复杂了 我还把元素后移了 class Solution { public:void sortColors(vector<int>& nums) {int min_num_index -1;int min_num 3;for(int i…...

C++ Primer 标准库vector

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

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 面试策略 如果三面往后遇到传说中让人忍受不了的业余面试官&#xff0c;就舔着苟过去&#xff0c;入职大概率见不着他&#xff0c;但一二面遇到&#xff0c;反问环节就主动说不够match&#xff0c;让释放流程。 机器/深度学习 百面机器学习 5.4 通用CS 计算机网…...

w191教师工作量管理系统的设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…...

Git 版本控制:基础介绍与常用操作

目录 Git 的基本概念 Git 安装与配置 Git 常用命令与操作 1. 初始化本地仓库 2. 版本控制工作流程 3. 分支管理 4. 解决冲突 5. 回退和撤销 6. 查看提交日志 前言 在软件开发过程中&#xff0c;开发者常常需要在现有程序的基础上进行修改和扩展。但如果不加以管理&am…...

讲清逻辑回归算法,剖析其作为广义线性模型的原因

1、逻辑回归算法介绍 逻辑回归(Logistic Regression)是一种广义线性回归分析模型。虽然名字里带有“回归”两字&#xff0c;但其实是分类模型&#xff0c;常用于二分类。既然逻辑回归模型是分类模型&#xff0c;为什么名字里会含有“回归”二字呢&#xff1f;这是因为其算法原…...

数据结构(1)——算法时间复杂度与空间复杂度

目录 前言 一、算法 1.1算法是什么&#xff1f; 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&#xff0c;**建库**2、启动命令3、[ERROR] GetNodeMetric Fail:the server is currently unable to handle the request (get nodes.metrics.k8s.io qfusion-1) 使用总结优点优化 补充1&#xff1a;layui、layuimini和beego的详细介绍1.…...

spring源码阅读系列文章目录

对于spring认识首先要了解 spring相关概念术语&#xff0c;然后是如下的几句话牢记并反射出来&#xff1a; Bean怎么来的&#xff0c;通过BeanDefinitionBeanDefinition有Spring框架内置的&#xff0c;有手动定义或者自动配置扫描出来的&#xff08;写个Demo工程&#xff09;B…...

快速提升网站收录:利用网站新闻发布功能

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/63.html 利用网站新闻发布功能快速提升网站收录是一个有效的策略。以下是一些具体的建议&#xff0c;帮助你更好地利用这一功能&#xff1a; 一、保持新闻更新频率 搜索引擎尤其重视网站的…...

【14】WLC3504 HA配置实例

1.概述 本文档使用 Cisco WLC 3504 实现无线控制器的高可用性。这里所指的HA是指WLC设备box-to-box的冗余。换句话说,即1:1的设备冗余,其中一个 WLC 将处于Active活动状态,而第二个 WLC 将处于Standby-hot热待机状态,通过RP冗余端口持续监控活动 WLC 的运行状况。两个 WLC…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

爬虫基础学习day2

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

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...