当前位置: 首页 > 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、段式存储 与 页式存储 对比 三、逻辑地址 的 合法段地址…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

Selenium 查找页面元素的方式

Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素&#xff0c;以下是主要的定位方式&#xff1a; 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...

LTR-381RGB-01RGB+环境光检测应用场景及客户类型主要有哪些?

RGB环境光检测 功能&#xff0c;在应用场景及客户类型&#xff1a; 1. 可应用的儿童玩具类型 (1) 智能互动玩具 功能&#xff1a;通过检测环境光或物体颜色触发互动&#xff08;如颜色识别积木、光感音乐盒&#xff09;。 客户参考&#xff1a; LEGO&#xff08;乐高&#x…...