每日算法-250430
每日算法 - 2025年4月30日
记录下今天解决的两道题目。
870. 优势洗牌 (Advantage Shuffle)
题目描述
解题思路与方法
核心思想:贪心策略 (田忌赛马)
这道题的目标是对于 nums1
中的每个元素,找到 nums2
中一个比它小的元素进行配对(如果可能),使得优势配对的数量最大化。如果 nums1
中的某个元素找不到 nums2
中可以战胜的对手,那么就用它去对付 nums2
中最强的对手,以保存 nums1
中更强的元素去对付 nums2
中可以战胜的对手。这类似于经典的“田忌赛马”策略。
具体步骤:
- 排序
nums1
:将nums1
升序排序,这样我们可以从小到大处理nums1
中的元素。 - 排序
nums2
的索引:我们不能直接排序nums2
,因为需要保留其原始元素的下标信息以构建最终结果ret
。因此,我们创建一个索引数组indexs
,存储0
到n-1
。然后根据nums2
中对应索引位置的元素值对indexs
进行升序排序。排序后,indexs[0]
指向nums2
中最小元素的原始索引,indexs[n-1]
指向nums2
中最大元素的原始索引。 - 双指针分配:
- 使用两个指针
left
和right
分别指向indexs
数组的开始(对应nums2
最小值)和结束(对应nums2
最大值)。 - 使用一个指针
i
遍历排序后的nums1
(从i=0
开始)。 - 比较
nums1[i]
(当前nums1
中最小的可用元素) 和nums2[indexs[left]]
(当前nums2
中最小的未匹配元素)。 - 如果
nums1[i] > nums2[indexs[left]]
:说明nums1[i]
可以战胜nums2
中当前最小的对手。这是一个优势匹配。我们将nums1[i]
分配给nums2
中这个最小对手的原始位置,即ret[indexs[left]] = nums1[i]
。然后移动left
指针 (left++
),考虑nums2
中下一个最小的对手。 - 如果
nums1[i] <= nums2[indexs[left]]
:说明nums1[i]
连nums2
中当前最小的对手都无法战胜。根据贪心策略,这个nums1[i]
应该去对付nums2
中最强的对手(反正也打不过,不如消耗掉对方最强的),以保留nums1
中更强的元素。我们将nums1[i]
分配给nums2
中当前最大对手的原始位置,即ret[indexs[right]] = nums1[i]
。然后移动right
指针 (right--
),考虑nums2
中下一个最大的对手。 - 无论哪种情况,
nums1[i]
都已经被使用,所以移动i
指针 (i++
) 处理nums1
中的下一个元素。
- 使用两个指针
- 循环继续:重复步骤 3,直到
left > right
,此时所有nums1
中的元素都已分配完毕。 - 返回结果数组
ret
。
复杂度分析
- 时间复杂度: O ( N log N ) O(N \log N) O(NlogN)。主要是排序
nums1
和indexs
数组所需的时间。双指针遍历过程是 O ( N ) O(N) O(N) 的。 - 空间复杂度: O ( N ) O(N) O(N)。需要额外的空间存储
indexs
数组和结果数组ret
。
Code
class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums2.length;Integer[] indexs = new Integer[n];for (int i = 0; i < n; i++) {indexs[i] = i;}Arrays.sort(nums1);Arrays.sort(indexs, (a, b) -> (nums2[a] - nums2[b]));int left = 0, right = n - 1;int i = 0;int[] ret = new int[n];while (left <= right) {int index = 0;if (nums1[i] <= nums2[indexs[left]]) {index = indexs[right];right--;} else {index = indexs[left];left++;}ret[index] = nums1[i];i++;}return ret;}
}
3402. 使每一列严格递增的最少操作次数 (Minimum Operations to Make Columns Strictly Increasing)
题目描述
解题思路与方法
核心思想:贪心策略
题目要求我们用最少的操作次数使得网格 grid
的每一列都严格递增。对于每一列,我们需要确保 grid[j][i] > grid[j-1][i]
对所有 j > 0
成立。
为了使操作次数最少,当发现 grid[j][i] <= grid[j-1][i]
时,我们应该将 grid[j][i]
增加到刚好满足严格递增条件的最小值,即 grid[j-1][i] + 1
。
具体步骤:
- 初始化总操作次数
ret = 0
。 - 遍历每一列:外层循环遍历列索引
i
从0
到grid[0].length - 1
。 - 遍历每一行的元素(从第二行开始):内层循环遍历行索引
j
从1
到grid.length - 1
。 - 检查条件:在每一列内部,比较当前元素
grid[j][i]
和它正上方的元素grid[j-1][i]
。 - 执行操作:
- 如果
grid[j][i] <= grid[j-1][i]
,说明不满足严格递增条件。 - 计算需要增加的值:
increase = (grid[j-1][i] + 1) - grid[j][i]
。 - 将这个增加的值累加到总操作次数
ret
中。 - 关键:更新
grid[j][i]
的值 为grid[j-1][i] + 1
。这一步非常重要,因为下一行的元素grid[j+1][i]
需要和 更新后 的grid[j][i]
进行比较。
- 如果
- 遍历完所有列和行后,
ret
就是所需的最小总操作次数。 - 返回
ret
。
复杂度分析
- 时间复杂度: O ( R × C ) O(R \times C) O(R×C),其中 R 是网格的行数,C 是网格的列数。我们需要遍历网格中的每个元素一次(除了第一行)。
- 空间复杂度: O ( 1 ) O(1) O(1)。我们是在原地修改
grid
(虽然题目可能没要求必须原地修改,但这样做不影响结果且节省空间),只需要常数级别的额外空间存储变量ret
、i
、j
等。
Code
class Solution {public int minimumOperations(int[][] grid) {int ret = 0;for (int i = 0; i < grid[0].length; i++) {for (int j = 1; j < grid.length; j++) {if (grid[j][i] <= grid[j - 1][i]) {ret += (grid[j - 1][i] + 1 - grid[j][i]);grid[j][i] = grid[j - 1][i] + 1;}}}return ret;}
}
相关文章:
每日算法-250430
每日算法 - 2025年4月30日 记录下今天解决的两道题目。 870. 优势洗牌 (Advantage Shuffle) 题目描述 解题思路与方法 核心思想:贪心策略 (田忌赛马) 这道题的目标是对于 nums1 中的每个元素,找到 nums2 中一个比它小的元素进行配对(如果…...
MacOS 安装 cocoapods
MacOS 安装 cocoapods 下面使用 HomeBrew 安装 cocoapods 一、检测 HomeBrew 是否安装 打开终端执行命令 brew -v #如果安装,输出如 Homebrew 4.5.0如果未安装 Mac HomeBrew安装 二、检测 ruby 是否安装 系统一般自带了 ruby 但是这个升级有些麻烦,我…...
MATLAB绘制饼图(二维/三维)
在数据分析与展示领域,饼图是一种直观且高效的可视化工具,能够在瞬间传递各部分与整体的比例关系。今天,我将分享一段 MATLAB 绘制二维及三维饼图的代码,助你轻松将数据以饼图形式呈现于众人眼前。 无论是二维饼图的简洁明了&…...
python将字符串转成二进制数组
python将字符串转成二进制数组 功能概述: save_binary_to_json() 函数:将字符串转换为二进制数据(字节的整数表示),并保存到JSON文件中。 load_binary_from_json() 函数:从JSON文件中读取二进制数据并还原…...
防止HTTPS页面通过<iframe>标签嵌入HTTP内容
防止HTTPS页面通过<iframe>标签嵌入HTTP内容 出于安全考虑,现代浏览器实施了严格的规则来防止HTTPS页面通过<iframe>标签嵌入HTTP内容。这种行为主要是为了防止所谓的“混合内容”问题,即在一个安全(加密)的页面中…...
windows 使用websocket++ (C++环境)
一、简介 websocket官方网址:http://websocket.org/ websocketpp官方网址:https://www.zaphoyd.com/websocketpp websocketpp使用手册:https://www.zaphoyd.com/websocketpp/manual/ websocketpp 是 C 的 WebSocket 客户端/服务器库. 它是…...
无水印短视频素材下载网站有哪些?十个高清无水印视频素材网站分享
你知道怎么下载无水印视频素材吗?今天小编就给大家推荐十个高清无水印视频素材下载的网站,如果你也是苦于下载高清无水印的短视频素材,赶紧来看看吧~ 1. 稻虎网 首推的是稻虎网。这个网站简直就是短视频创作者的宝库。无论你需要…...
【dify—5】Dify关联Ollama
目录 一、修改.env文件 二、启动dify 三、访问dify 四、设置关联 五、添加模型插件 5.1 添加模型 5.2 配置信息编辑 第一部分 安装difydocker教程:【difydocker安装教程】-CSDN博客 第二部分 dock重装教程: 【dify—2】docker重装-CSDN博客 第三…...
PostgreSQL可串行化快照隔离和冻结处理
1.可串行化快照隔离 可串行化快照隔离SSI已经嵌入到快照隔离SI中,以实现真正的可串行化隔离等级。 SSI实现基本策略 使用SIREDA锁记录事务访问的所有对象(元组,页面,关系)。 当写入任何堆元组/索引元组时ÿ…...
Java 多线程进阶:什么是线程安全?
在多线程编程中,“线程安全”是一个非常重要但又常被误解的概念。尤其对于刚接触多线程的人来说,不理解线程安全的本质,容易写出“偶尔出错”的代码——这类 bug 往往隐蔽且难以复现。 本文将用尽可能通俗的语言,从三个角度解释线…...
Java导出带图片的Excel
使用easypoi导出带图片的Excel, 引入依赖 依赖中着重要剔除可能会造成冲突的依赖,不剔除的话可能会报错 Exception in thread “main” java.lang.NoSuchFieldError: Class org.openxmlformats.schemas.spreadsheetml.x2006.main.CTWorkbook does not …...
Keysight万用表使用指南及基于Python采集数据生成Excel文件
文章目录 说明使用的库openpyxlpyvisa 代码说明效果展示参考代码 说明 本文介绍了 Keysight 34465A 的基本使用和 SCPI 指令设置,演示了使用 Python 的 PyVISA 库控制两台 34465A 同时采集数据的完整流程,包括设置采样参数、触发测量、读取数据、使用 O…...
HarmonyOS Next-DevEco Studio(5.0.2)无网络环境配置(详细教程)
开发者如果电脑处于完全无网环境,可以参考下面文档进行相关配置 DevEco Studio(5.0.2)开发环境一览: 工具版本DevEco Studio5.0.2openHarmonySDK14ohpm5.0.11node.js18.20.1hypium1.0.21 一、下载DevEco Studio(5.0.2 Release)…...
数字中国的建设之路:超聚变以“智算数能”四大密钥,共建智能体时代
文 | 智能相对论 作者 | 陈泊丞 即便是数字中国建设这样的宏大叙事,在长期的行业实践与业务聚焦之下,未来的发展路径也将会越来越清晰。日前,第八届数字中国建设峰会在福建拉开序幕,各大论坛、企业、机构、组织等纷纷围绕数字中…...
PageOffice在线打开word文件,并实现切换文件
本示例关键代码的编写位置,请参考“PageOffice 开发者中心-快速起步–开始 - 快速上手”里您所使用的开发语言框架的最简集成代码 注意 本文中展示的代码均为关键代码,复制粘贴到您的项目中,按照实际的情况,例如文档路径ÿ…...
Ubuntu 24.04 终端美化
参考文章:Ubuntu终端美化(tabbyoh-my-zsh)-Ubuntu系列03 有些步骤和 Ubuntu 24.04 不太适配,而且逻辑不太适合小白,故写此文。 1. 安装 Tabby 参考文章的 tabby 版本过老,如果在 Ubuntu 24.04 装会报一些依…...
python合并word中的run
在处理Word文档时,使用python-docx库可以读取文档中的段落,并将每个段落中的多个run合并为一个run。run对象用于表示段落中具有相同格式的文本部分。将多个run合并为一个run可以帮助简化文档结构,尤其是在格式一致的情况下。 以下是一个示例…...
微前端框架选型指南
微前端框架选型指南 一、写在前面 微前端架构为大型前端系统提供了分而治之的能力,不同团队可以独立开发、部署和维护各自的模块。然而,当前市面上存在多种微前端框架(如 Qiankun、Wujie、micro-app、Hel、Emp 等),选…...
Tailwind CSS实战技巧:从核心类到高效开发
使用 Kooboo平台 训练实战技巧,无需配置安装,直接引入CDN就可以在线练习了!具体操作流程:进入Kooboo后,选择创建空白站点 -> 站点开发 -> 控制面板 -> 页面 ->新建普通页面 -> 编写代码 一、核心布局类…...
C# 事件与委托
一、委托基础 1. 委托定义 委托是一种类型安全的函数指针,它允许将方法作为参数传递给其他方法。 // 声明一个委托类型 public delegate void MyDelegate(string message);// 使用委托 public class Program {public static void Main(){// 创建委托实例并指向方…...
django_rq
使用 Loguru 记录 Django-RQ 任务日志 要在 Django-RQ 处理的任务中使用 Loguru 记录日志,你需要做的就是按照标准的 Loguru 使用方法配置和使用日志记录器。下面是一个简单的示例,展示如何在 Django-RQ 的任务中集成 Loguru: 安装必要的包…...
Java List分页工具
PageUtil.java import com.google.common.collect.Lists; import com.jd.platform.hotkey.dashboard.common.domain.Page; import org.springframework.util.CollectionUtils;import java.util.ArrayList; import java.util.List;public class PageUtil {/*** 通用分页工具类*…...
【UE5】“对不起,您的客户端未能传递登录所需的参数”解决办法
想要进入Epic账户,正常登录后就会弹出这个: 官方提供了一个解决办法: 如果以上办法行不通,关闭单点登录: 成功解决...
Web开发-JavaEE应用SpringBoot栈模版注入ThymeleafFreemarkerVelocity
知识点: 1、安全开发-JavaEE-开发框架-SpringBoot&路由&传参 2、安全开发-JavaEE-模版引擎-Thymeleaf&Freemarker&Velocity 一、演示案例-WEB开发-JavaEE-开发框架-SpringBoot&路由&传参 类似于php语言中的thinkphp,不过要更加…...
出现Invalid bound statement (not found)问题的原因可能有哪些
1.全局配置文件没配好? 检查全局配置文件application.properties或application.yml是否配置扫描mapper包的文件路径 #mybatis配置mapper文件路径 #mybatis.mapper-locationsclasspath:/mapper/*.xml #mybatis-plus配置mapper文件路径 mybatis-plus.mapper-locatio…...
多类型文件集中查看系统
软件介绍 Universal Viewer 是一款具备多格式兼容能力的文件查看工具,旨在为用户提供统一化的文档处理方案。 核心功能优势 该工具采用全格式兼容架构,支持包括图片、音视频及办公文档在内的多种通用文件类型,实现单一软件完成多格式处…...
WebSocket与Socket、TCP、HTTP的关系及区别
1.什么是WebSocket及原理 WebSocket是HTML5中新协议、新API。 WebSocket从满足基于Web的日益增长的实时通信需求应运而生,解决了客户端发起多个Http请求到服务器资源浏览器必须要在经过长时间的轮询问题,实现里多路复用,是全双工、双向、单套…...
【25软考网工】第四章(4)无线局域网WLAN安全技术、无线个人网WPAN
目录 一、无线局域网安全技术 1. WLAN安全机制 编辑 1)SSID访问控制 2)物理地址过滤 3)WEP认证和加密 4)WPA(认证、加密、数据完整性) 5)WPA2 6)无线认证技术 2. WEP和W…...
Vue:el-table-tree懒加载数据
目录 一、出现场景二、具体使用三、修改时重新加载树节点四、新增、删除重新加载树节点 一、出现场景 在项目的开发过程中,我们经常会使用到表格树的格式,但是犹豫数据较多,使用分页又不符合项目需求时,就需要对树进行懒加载的操…...
JCRQ1河马算法+消融实验!HO-CNN-LSTM-Attention系列四模型多变量时序预测,作者:机器学习之心
JCRQ1河马算法消融实验!HO-CNN-LSTM-Attention系列四模型多变量时序预测 目录 JCRQ1河马算法消融实验!HO-CNN-LSTM-Attention系列四模型多变量时序预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 基于HO-CNN-LSTM-Attention、CNN-LSTM-Attent…...
vue elementui 去掉默认填充 密码input导致的默认填充
<el-form-item prop"code"><div style"display: flex; width: 100%; align-items: flex-end"><el-inputv-model"loginForm.code"size"small"auto-complete"off"placeholder"请输入验证码"keyup.en…...
Android学习总结之设计场景题
设计图片请求框架的缓存模块 核心目标是通过分层缓存策略(内存缓存 磁盘缓存)提升图片加载效率,同时兼顾内存占用和存储性能。以下是针对 Android 面试官的回答思路,结合代码注释说明关键设计点: 一、缓存架构设计&…...
【数学建模国奖速成系列】优秀论文绘图复现代码(四)
文章目录 引言三维图双轴图三维散点图完整复现代码 引言 数模比赛的绘图是非常重要得,这篇文章给大家分享我自己复现国奖优秀论文的代码,基于Matalab来实现,可以直接运行出图。之前的文章也有分享【折线图、柱状图、箱线图、热图】的绘制&am…...
哪些因素会影响远程视频监控的质量?浅述EasyCVR视频智能诊断技术
在安防领域,无线监控系统凭借其灵活部署、便捷扩展的特性得到广泛应用。然而,实时监控图像清晰度不足、回放调查受限等问题,严重制约了其应用效果。经分析,摄像机性能、线缆质量、无线网桥性能、交换机配置及供电电压等是影响图像…...
Android学习总结之算法篇六(数组和栈)
括号匹配 public static boolean isValid(String s) {// 创建一个栈用于存储左括号Stack<Character> stack new Stack<>();// 遍历字符串中的每个字符for (char c : s.toCharArray()) {if (c ( || c [ || c {) {// 如果是左括号,将其压入栈中stack…...
一套SaaS ERP管理系统源码,支持项目二开商用,SpringBoot+Vue+ElementUI+UniAPP
ERP管理系统源码,一款适用于小微企业的SaaS ERP管理系统源码, 采用最新的技术栈开发(SpringBootVueElementUIUniAPP),让企业简单上云。 专注于小微企业的应用需求,如企业基本的进销存、询价,报价, 采购、销售、MRP生产制造、品质…...
【Agent】MCP协议 | 用高德MCP Server制作旅游攻略
note MCP (Model Context Protocol) 代表了 AI 与外部工具和数据交互的标准建立。MCP 的本质:它是一个统一的协议标准,使 AI 模型能够以一致的方式连接各种数据源和工具,类似于 AI 世界的"USB-C"接口。 它能够在 LLM/AI Agent 与外…...
ISO 26262认证步骤
一、企业需要做? 从 ISO 26262 标准导入到认证大概需要经历7 个主要的阶段, 分别是策划阶段、 流程建立阶段、 流程试运行阶段、 流程认证阶段、 流程推广阶段、 产品认证阶段和持续运行阶段。 策划阶段:精准布局差距分析:对照 I…...
php+mysql活动报名学生选课产品预定旅游报名系统网站源码
本系统是一个基于PHPMySQL的活动报名管理系统,支持多个活动的发布、报名、审核等功能。系统分为用户端和管理端两个部分,实现了活动报名的完整流程管理。 环境要求 ------- - PHP 7.1 - MySQL 5.6 - 支持mysqli扩展 - 支持session - 支持文件上传 默认账…...
Qt QWebEngine应用和网页的交互
一、QWebEngine简介 1、Qt WebEngine模块提供了一个Web浏览器引擎,可以轻松地将万维网上的内容嵌入到没有本机Web引擎的平台上的Qt应用程序中。 2、Qt WebEngine提供了用于渲染HTML,XHTML和SVG文档的C 类和QML类型,它们使用级联样式表&#…...
【爬虫】deepseek谈爬虫工具
2025 年,随着 Web 技术的演进和反爬机制的升级,工具生态也会进一步优化。以下是 2025 年爬虫 & 自动化测试的前沿工具预测,结合行业趋势和现有技术发展方向: 🚀 2025 年推荐组合(预测版) 1…...
大数据治理自动化与智能化实践指南:架构、工具与实战方案(含代码)
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言:从人治到机治,数据治理正在进化 随着数据体量持续膨胀、数据场景复杂化,传统依赖人工规则的大数据治理方式已难以为继。企业在治理过程中面临: 数据质量问题激增,人工检测成本高 元数…...
基于BM1684X+RK3588的智能工业视觉边缘计算盒子解决方案
智能工业视觉边缘计算终端技术方案书 1. 产品概述 1.1 产品定位 面向工业自动化场景的高性能AI视觉处理设备集成BM1684X(8TOPS INT8)AI加速芯片 RK3588(6TOPS NPU)异构计算支持工业级多相机接入、实时缺陷检测、高精度定…...
dubbo泛化调用时transient字段失效问题
工作中发现dubbo泛化调用时结果类中的某个字段即使已经用transient修饰了,但是前端还是会有该字段展示,探究了原因如下: 如果是走的泛化调用,会通过genericFilter和genericImplFilter两个类来处理序列化和反序列化,会…...
【C++】数据结构 九种排序算法的实现
本篇博客给大家带来的是直接插入、希尔、直接选择、堆、冒泡、快速、归并、计数、排序算法的实现! 🐟🐟文章专栏:数据结构 🚀🚀若有问题评论区下讨论,我会及时回答 ❤❤欢迎大家点赞、收藏、分享…...
【数据结构与算法】跳表实现详解
文章目录 Ⅰ. 前言Ⅱ. 跳表(skiplist)一、什么是跳表二、跳表的发明历程三、跳表的搜索方式Ⅲ. skiplist的算法性能分析一、理论准备二、性能分析(了解即可,主要记结论)Ⅳ. skiplist与平衡树、哈希表的比较Ⅴ. skiplist的实现[ 设计跳表](https://leetcode.cn/problems/de…...
2025年“深圳杯”数学建模挑战赛B题-LED显示屏颜色转换设计与校正
LED显示屏颜色转换设计与校正 小驴数模 问题的背景 走在晚风都市,或春日田野,我们都会看到一个色彩斑斓的世界。色彩是我们对世界一种重要感知。什么是色彩,或颜色?颜色是光作用于人眼引起的视觉感知现象,它与物体的…...
毕业论文 | 基于C#开发的NMEA 0183协议上位机
以下是基于C#开发的NMEA 0183协议上位机完整实现方案,包含串口通信、数据解析与可视化功能: 基于C#开发的NMEA 0183协议上位机 一、项目结构二、核心代码实现1. 数据模型定义2. 串口通信管理3. NMEA协议解析核心4. 主界面实现(Windows Forms)三、界面设计关键元素(需在窗体…...
【Scrapy】简单项目实战--爬取dangdang图书信息
目录 一、基本步骤 1、新建项目 :新建一个新的爬虫项目 2、明确目标 (items.py):明确你想要抓取的目标 3、制作爬虫 (spiders/xxspider.py):制作爬虫开始爬取网页 4、存储内容 (p…...
Linux架构篇、第1章_01架构的介绍HTTP HTTPS 协议全面解析
题目:HTTP/HTTPS 协议全面解析:原理、区别与状态码详解 版本号: 1.0,0 作者: 老王要学习 日期: 2025.04.30 适用环境: 服务器 文档说明 本文围绕 HTTP/HTTPS 协议展开,详细介绍了协议的基本概念、工作原理、两者之间的区别以及常见的状态码…...