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

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 i1 前面的空余时间或者会议 i + 1 i+1 i+1 后面的空余时间中(即会议 i i i 的大小 <= 空余时间),那么当前的空余时间 = 会议 i i i 与 会议 i − 1 i-1 i1 的空余时间 + 会议 i i i 与 会议 i + 1 i+1 i+1 的空余时间 + 会议 i i i 本身的时间。否则与 T2 情况相同,当前的空余时间 = 会议 i i i 与 会议 i − 1 i-1 i1 的空余时间 + 会议 i i i 与 会议 i + 1 i+1 i+1 的空余时间

接下来就是如何判断会议 i i i 可以移动到后面或前面,这里可以使用前后缀分解的做法来预处理 [ 0 , i − 1 ] [0,i-1] [0,i1] 的最大空余时间,和 [ i + 1 , n − 1 ] [i+1,n-1] [i+1n1] 的最大空余时间。

代码如下:

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,n1] 变成好标题的最小操作次数,然后转成 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. 找到字符串中合法的相邻数字 题目链接 本题有两个条件&#xff1a; 相邻数字互不相同两个数字的的…...

解决 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配置文件 注意&#xff0c;配置文件会因为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 时&#xff0c;如果出现 zsh: command not found: conda 错误&#xff0c;说明你的系统未正确配置 conda 命令&#xff0c;或者你尚未安装 Anaconda/Miniconda。 解决方案 确保已安装 Anaconda 或 Miniconda conda 是 Anaconda 或 Minico…...

【知识科普】CPU,GPN,NPU知识普及

CPU,GPU,NPU CPU、GPU、NPU 详解1. CPU&#xff08;中央处理器&#xff09;2. GPU&#xff08;图形处理器&#xff09;3. NPU&#xff08;神经网络处理器&#xff09; **三者的核心区别****协同工作示例****总结** CPU、GPU、NPU 详解 1. CPU&#xff08;中央处理器&#xff0…...

【C++八股】struct和Class的区别

1. 默认访问控制 struct&#xff1a;结构体中的成员默认是 public&#xff0c;即外部代码可以直接访问结构体的成员。class&#xff1a;类中的成员默认是 private&#xff0c;即外部代码不能直接访问类的成员&#xff0c;必须通过公有接口&#xff08;通常是成员函数&#xff…...

鹧鸪云光伏仓储、物料管理软件详细功能

采购中心 &#xff1a;作为核心枢纽&#xff0c;能集中管理多品牌设备&#xff0c;企业可灵活按需采购。采购与退货流程高效便捷&#xff0c;审核通过后物资快速补充、问题货物及时退回&#xff0c;保障资金与物资顺畅周转&#xff0c;避免积压浪费。付款与退款环节 &#xff1…...

bazel 小白理解

Bazel命令是用于构建和测试软件项目的一个强大工具&#xff0c;尤其适用于大规模和多语言的软件项目。对于小白来说&#xff0c;可以这样理解Bazel及其命令&#xff1a; Bazel的基本概念 构建系统&#xff1a;Bazel是一个构建系统&#xff0c;它的主要任务是自动化地编译和链…...

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&#xff1a;负责与 SQLite 数据库进行交互&#xff0c;包括创建表、插入、删除、更新和查询数据等操作。View&#xff1…...

WPF 设置宽度为 父容器 宽度的一半

方法1&#xff1a;使用 绑定和转换器 实现 创建类文件 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项目之在线心理评测与咨询管理系统(源码+文档)

项目简介 在线心理评测与咨询管理系统实现了以下功能&#xff1a; 在线心理评测与咨询管理系统的主要使用者分为&#xff1a; &#xff08;1&#xff09;在个人中心&#xff0c;管理员可以修改自己的用户名和登录密码。 &#xff08;2&#xff09;在系统前台可以查看首页&…...

【STM32系列】利用MATLAB配合ARM-DSP库设计FIR数字滤波器(保姆级教程)

ps.源码放在最后面 设计IIR数字滤波器可以看这里&#xff1a;利用MATLAB配合ARM-DSP库设计IIR数字滤波器&#xff08;保姆级教程&#xff09; 前言 本篇文章将介绍如何利用MATLAB与STM32的ARM-DSP库相结合&#xff0c;简明易懂地实现FIR低通滤波器的设计与应用。文章重点不在…...

Springboot框架扩展功能的使用

Spring Boot 提供了许多扩展点&#xff0c;允许开发者在应用程序的生命周期中插入自定义逻辑。这些扩展点可以帮助你更好地控制应用程序的行为&#xff0c;例如在启动时初始化数据、在关闭时释放资源、或者自定义配置加载逻辑。以下是 Spring Boot 中常见的扩展点&#xff1a; …...

yum报错 Could not resolve host: mirrorlist.centos.org

检查dns 使用ping www.baidu.com &#xff0c;如果ping不通&#xff0c;检查/etc/resolv.conf文件中是否有&#xff1a; nameserver 8.8.8.8 nameserver 8.8.4.4 替换yum源 1.备份原始的 YUM 源配置文件&#xff1a; sudo cp /etc/yum.repos.d/CentOS-Base.repo /etc/yum.r…...

docker使用dockerfile打包镜像(docker如何打包)

文章目录 1. 编写 Dockerfile2. 构建 Docker 镜像3. 运行 Docker 容器4. 导出与导入镜像&#xff08;可选&#xff09; 1. 编写 Dockerfile Dockerfile 是一个文本文件&#xff0c;其中包含了一系列指令&#xff0c;这些指令定义了如何构建你的 Docker 镜像。下面以一个简单的…...

去中心化AGI网络架构:下一代人工智能的范式革命

文章目录 引言:当AGI遇到去中心化一、中心化AI架构的四大困境1.1 算力垄断与资源错配1.2 数据孤岛与隐私悖论1.3 模型暴政与单点故障1.4 创新抑制与价值捕获二、去中心化AGI网络的架构设计2.1 分层架构总览2.2 网络层:混合拓扑结构2.3 计算层:动态算力编排2.4 数据层:零知识…...

gitlab无法登录问题

在我第一次安装gitlab的时候发现登录页面是 正常的页面应该是 这种情况的主要原因是不是第一次登录&#xff0c;所以我们要找到原先的密码 解决方式&#xff1a; [rootgitlab ~]# vim /etc/gitlab/initial_root_password# WARNING: This value is valid only in the followin…...

单向链表在实际项目中的应用

前言 在实际项目中&#xff0c;单向链表经常被用来解决排队问题&#xff0c;因为链表允许动态地添加和移除元素&#xff0c;非常适合模拟队列&#xff08;FIFO&#xff0c;先进先出&#xff09;的行为。 这里的链表包含头节点&#xff0c;头结点的数据用来记录链表长度&#x…...

【系统架构设计师】操作系统 ③ ( 存储管理 | 页式存储弊端 - 段式存储引入 | 段式存储 | 段表 | 段表结构 | 逻辑地址 的 合法段地址判断 )

文章目录 一、页式存储弊端 - 段式存储引入1、页式存储弊端 - 内存碎片2、页式存储弊端 - 逻辑结构不匹配3、段式存储引入 二、段式存储 简介1、段式存储2、段表3、段表 结构4、段内地址 / 段内偏移5、段式存储 优缺点6、段式存储 与 页式存储 对比 三、逻辑地址 的 合法段地址…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...