Leetcode - 149双周赛
目录
- 一、3438. 找到字符串中合法的相邻数字
- 二、3439. 重新安排会议得到最多空余时间 I
- 三、3440. 重新安排会议得到最多空余时间 II
- 四、3441. 变成好标题的最少代价
一、3438. 找到字符串中合法的相邻数字
题目链接

本题有两个条件:
- 相邻数字互不相同
- 两个数字的的出现次数等于数字本身
先预处理字符串 s s s 中每个字符的出现次数,再从左往右两两枚举,返回第一个满足上述条件的相邻数字,没有返回空字符串。
代码如下:
class Solution {public String findValidPair(String s) {int[] cnt = new int[10];for(char c : s.toCharArray()){cnt[c-'0']++;}for(int i=1; i<s.length(); i++){int x = s.charAt(i) - '0';int y = s.charAt(i-1) - '0';if(x == y) continue;if(cnt[x] == x && cnt[y] == y)return s.substring(i-1, i+1);}return "";}
}
二、3439. 重新安排会议得到最多空余时间 I
题目链接

题目求至多平移 k k k 个会议后,可以获得的最大空余时间,与会议本身的时间无关,可以预处理出会议之间的空余时间(注:不要忘记第一个会议开始前和最后一个会议结束后的空余时间),贪心的想,平移的会议越多,可以获得的空余时间越大,此时题目变成了平移 k k k 个会议后,可以获得的最大空余时间,讨论 k k k 的大小:
- k = 1 k=1 k=1,对于 1 1 1 个会议来说,无论它往前移还是往后移,它会使得连续的 2 2 2 段空余时间合并.
- k = 2 k=2 k=2,对于 2 2 2 个会议来说,无论它们往前移还是往后移,它会使得连续的 3 3 3 段空余时间合并.
- …
- 对于 k k k 个会议来说,无论它们往前移还是往后移,它会使得连续的 k + 1 k+1 k+1 段空余时间合并.
也就是说它其实是一个滑动窗口题,就是维护连续 k + 1 k+1 k+1 段空余时间的最大值。
代码如下:
class Solution {public int maxFreeTime(int event, int k, int[] start, int[] end) {int n = start.length;int[] t = new int[n+1];t[0] = start[0];t[n] = event - end[n-1];for(int i=1; i<n; i++){t[i] = start[i] - end[i-1];}int ans = 0, res = 0;for(int l=0,r=0; r<n+1; r++){res += t[r];if(r-l+1 > k + 1){res -= t[l];l++;}ans = Math.max(ans, res);}return ans;}
}
三、3440. 重新安排会议得到最多空余时间 II
题目链接

本题与 T2 的区别在于只能移动 1 个会议,且会议之间的顺序可以发生改变,这将会导致一个新的情况,如果会议 i i i 可以移动到会议 i − 1 i-1 i−1 前面的空余时间或者会议 i + 1 i+1 i+1 后面的空余时间中(即会议 i i i 的大小 <= 空余时间),那么当前的空余时间 = 会议 i i i 与 会议 i − 1 i-1 i−1 的空余时间 + 会议 i i i 与 会议 i + 1 i+1 i+1 的空余时间 + 会议 i i i 本身的时间。否则与 T2 情况相同,当前的空余时间 = 会议 i i i 与 会议 i − 1 i-1 i−1 的空余时间 + 会议 i i i 与 会议 i + 1 i+1 i+1 的空余时间
接下来就是如何判断会议 i i i 可以移动到后面或前面,这里可以使用前后缀分解的做法来预处理 [ 0 , i − 1 ] [0,i-1] [0,i−1] 的最大空余时间,和 [ i + 1 , n − 1 ] [i+1,n-1] [i+1,n−1] 的最大空余时间。
代码如下:
class Solution {public int maxFreeTime(int event, int[] start, int[] end) {int n = start.length;int[] t = new int[n+1];t[0] = start[0];t[n] = event - end[n-1];int ans = Math.max(t[0], t[n]);int[] pre = new int[n+1];//前缀最大值pre[0] = t[0];for(int i=1; i<n; i++){t[i] = start[i] - end[i-1];pre[i] = Math.max(pre[i-1], t[i]);}int[] suf = new int[n+1];//后缀最大值suf[n] = t[n];for(int i=n-1; i>=0; i--){suf[i] = Math.max(suf[i+1], t[i]);}int res = 0;for(int l=0,r=1; r<n+1; l++,r++){int len = end[l] - start[l];//判断当前 会议l 能否移动到前面/后面if(l>0 && pre[l-1] >= len || l+2<n+1 && suf[l+2] >= len)ans = Math.max(ans, t[r] + t[l] + len);else ans = Math.max(ans, t[l] + t[r]);}return ans;}
}
四、3441. 变成好标题的最少代价
题目链接

对于本题来说,它返回的好标题需要满足两个条件,操作次数最少且字典序最小,可以先使用 d f s dfs dfs 计算出得到好标题的最小操作次数,定义 d f s ( i , j ) : dfs(i,j): dfs(i,j): 第 i i i 个位置变成 j j j 时, [ i + 1 , n − 1 ] [i+1,n-1] [i+1,n−1] 变成好标题的最小操作次数,然后转成 d p dp dp,此时可以使用数组记录每个状态的转移来源,最后逆推得到操作次数最小的最小的字典序。
代码如下:
class Solution {public String minCostGoodCaption(String caption) {int n = caption.length();if(n < 3) return "";int res = Integer.MAX_VALUE;char[] s = caption.toCharArray();int[][] f = new int[n+1][26];int[][] nxt = new int[n+1][26];int[] minJ = new int[n+1];for(int i=n-1; i>=0; i--){int mn = Integer.MAX_VALUE;for(int j=0; j<26; j++){int res1 = f[i+1][j] + Math.abs(s[i] - 'a' - j);int res2 = i <= n - 6 ? f[i+3][minJ[i+3]] + Math.abs(s[i] - 'a' - j) + Math.abs(s[i+1] - 'a' - j) + Math.abs(s[i+2] - 'a' - j) : Integer.MAX_VALUE;if(res1 > res2 || res1 == res2 && minJ[i+3] < j){res1 = res2;nxt[i][j] = minJ[i+3];}else{nxt[i][j] = j;}f[i][j] = res1;if(res1 < mn){mn = res1;minJ[i] = j;}}}char[] ans = new char[n];int i = 0, j = minJ[0];while(i < n){ans[i] = (char)(j + 'a');int k = nxt[i][j];if(k == j){i++;}else{ans[i+2] = ans[i+1] = ans[i];i += 3;j = k;}}return new String(ans);}
}
相关文章:
Leetcode - 149双周赛
目录 一、3438. 找到字符串中合法的相邻数字二、3439. 重新安排会议得到最多空余时间 I三、3440. 重新安排会议得到最多空余时间 II四、3441. 变成好标题的最少代价 一、3438. 找到字符串中合法的相邻数字 题目链接 本题有两个条件: 相邻数字互不相同两个数字的的…...
解决 ComfyUI-Impact-Pack 中缺少 UltralyticsDetectorProvider 节点的问题
解决 ComfyUI-Impact-Pack 中缺少 UltralyticsDetectorProvider 节点的问题 1. 安装ComfyUI-Impact-Pack 首先确保ComfyUI-Impact-Pack 已经下载 地址: https://github.com/ltdrdata/ComfyUI-Impact-Pack 2. 安装ComfyUI-Impact-Subpack 由于新版本的Impact Pack 不再提供这…...
使用Kickstart配置文件封装操作系统实现Linux的自动化安装
使用Kickstart配置文件封装操作系统实现Linux的自动化安装 创建ks.cfg配置文件 可以使用已经安装完成的Linux操作系统中的/root目录下的anaconda.cfg配置文件 注意,配置文件会因为kickstart的版本兼容性的问题导致无法安装报错需要在实际使用过程中删除某些参数 …...
Android笔记【snippet】
一、 6、Card及ConstraintLayout线性布局 //定义单独的机器人单独一行的卡片 Composable fun RobotCard(robot: Robot,navController:NavController){Card(modifier Modifier.fillMaxWidth().wrapContentHeight().padding(5.dp),colors CardDefaults.elevatedCardColors(co…...
zsh: command not found: conda
场景描述 在 Linux 服务器上使用 zsh 时,如果出现 zsh: command not found: conda 错误,说明你的系统未正确配置 conda 命令,或者你尚未安装 Anaconda/Miniconda。 解决方案 确保已安装 Anaconda 或 Miniconda conda 是 Anaconda 或 Minico…...
【知识科普】CPU,GPN,NPU知识普及
CPU,GPU,NPU CPU、GPU、NPU 详解1. CPU(中央处理器)2. GPU(图形处理器)3. NPU(神经网络处理器) **三者的核心区别****协同工作示例****总结** CPU、GPU、NPU 详解 1. CPU(中央处理器࿰…...
【C++八股】struct和Class的区别
1. 默认访问控制 struct:结构体中的成员默认是 public,即外部代码可以直接访问结构体的成员。class:类中的成员默认是 private,即外部代码不能直接访问类的成员,必须通过公有接口(通常是成员函数ÿ…...
鹧鸪云光伏仓储、物料管理软件详细功能
采购中心 :作为核心枢纽,能集中管理多品牌设备,企业可灵活按需采购。采购与退货流程高效便捷,审核通过后物资快速补充、问题货物及时退回,保障资金与物资顺畅周转,避免积压浪费。付款与退款环节 ࿱…...
bazel 小白理解
Bazel命令是用于构建和测试软件项目的一个强大工具,尤其适用于大规模和多语言的软件项目。对于小白来说,可以这样理解Bazel及其命令: Bazel的基本概念 构建系统:Bazel是一个构建系统,它的主要任务是自动化地编译和链…...
MVC(Model-View-Controller)framework using Python ,Tkinter and SQLite
1.项目结构 sql: CREATE TABLE IF NOT EXISTS School (SchoolId TEXT not null, SchoolName TEXT NOT NULL,SchoolTelNo TEXT NOT NULL) 整体思路 Model:负责与 SQLite 数据库进行交互,包括创建表、插入、删除、更新和查询数据等操作。View࿱…...
WPF 设置宽度为 父容器 宽度的一半
方法1:使用 绑定和转换器 实现 创建类文件 HalfWidthConverter public class HalfWidthConverter : IValueConverter{public object Convert(object value, Type targetType, object parameter, CultureInfo culture){if (value is double width){return width / 4…...
java项目之在线心理评测与咨询管理系统(源码+文档)
项目简介 在线心理评测与咨询管理系统实现了以下功能: 在线心理评测与咨询管理系统的主要使用者分为: (1)在个人中心,管理员可以修改自己的用户名和登录密码。 (2)在系统前台可以查看首页&…...
【STM32系列】利用MATLAB配合ARM-DSP库设计FIR数字滤波器(保姆级教程)
ps.源码放在最后面 设计IIR数字滤波器可以看这里:利用MATLAB配合ARM-DSP库设计IIR数字滤波器(保姆级教程) 前言 本篇文章将介绍如何利用MATLAB与STM32的ARM-DSP库相结合,简明易懂地实现FIR低通滤波器的设计与应用。文章重点不在…...
Springboot框架扩展功能的使用
Spring Boot 提供了许多扩展点,允许开发者在应用程序的生命周期中插入自定义逻辑。这些扩展点可以帮助你更好地控制应用程序的行为,例如在启动时初始化数据、在关闭时释放资源、或者自定义配置加载逻辑。以下是 Spring Boot 中常见的扩展点: …...
yum报错 Could not resolve host: mirrorlist.centos.org
检查dns 使用ping www.baidu.com ,如果ping不通,检查/etc/resolv.conf文件中是否有: nameserver 8.8.8.8 nameserver 8.8.4.4 替换yum源 1.备份原始的 YUM 源配置文件: sudo cp /etc/yum.repos.d/CentOS-Base.repo /etc/yum.r…...
docker使用dockerfile打包镜像(docker如何打包)
文章目录 1. 编写 Dockerfile2. 构建 Docker 镜像3. 运行 Docker 容器4. 导出与导入镜像(可选) 1. 编写 Dockerfile Dockerfile 是一个文本文件,其中包含了一系列指令,这些指令定义了如何构建你的 Docker 镜像。下面以一个简单的…...
去中心化AGI网络架构:下一代人工智能的范式革命
文章目录 引言:当AGI遇到去中心化一、中心化AI架构的四大困境1.1 算力垄断与资源错配1.2 数据孤岛与隐私悖论1.3 模型暴政与单点故障1.4 创新抑制与价值捕获二、去中心化AGI网络的架构设计2.1 分层架构总览2.2 网络层:混合拓扑结构2.3 计算层:动态算力编排2.4 数据层:零知识…...
gitlab无法登录问题
在我第一次安装gitlab的时候发现登录页面是 正常的页面应该是 这种情况的主要原因是不是第一次登录,所以我们要找到原先的密码 解决方式: [rootgitlab ~]# vim /etc/gitlab/initial_root_password# WARNING: This value is valid only in the followin…...
单向链表在实际项目中的应用
前言 在实际项目中,单向链表经常被用来解决排队问题,因为链表允许动态地添加和移除元素,非常适合模拟队列(FIFO,先进先出)的行为。 这里的链表包含头节点,头结点的数据用来记录链表长度&#x…...
【系统架构设计师】操作系统 ③ ( 存储管理 | 页式存储弊端 - 段式存储引入 | 段式存储 | 段表 | 段表结构 | 逻辑地址 的 合法段地址判断 )
文章目录 一、页式存储弊端 - 段式存储引入1、页式存储弊端 - 内存碎片2、页式存储弊端 - 逻辑结构不匹配3、段式存储引入 二、段式存储 简介1、段式存储2、段表3、段表 结构4、段内地址 / 段内偏移5、段式存储 优缺点6、段式存储 与 页式存储 对比 三、逻辑地址 的 合法段地址…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
