【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效
文章目录
- Check If Word Is Valid After Substitutions 检查替换后的词是否有效
- 问题描述:
- 分析
- 代码
- Tag
Check If Word Is Valid After Substitutions 检查替换后的词是否有效
问题描述:
给你一个字符串 s ,请你判断它是否 有效 。
字符串 s 有效 需要满足:假设开始有一个空字符串 t = “” ,你可以执行 任意次 下述操作将 t 转换为 s :
将字符串 “abc” 插入到 t 中的任意位置。形式上,t 变为 tleft + “abc” + tright,其中 t == tleft + tright 。注意,tleft 和 tright 可能为 空 。
如果字符串 s 有效,则返回 true;否则,返回 false。
s.length范围[1,20000],仅由abc构成。
分析
使用暴力构造的方法,就是每构造一个有效的s’,然后在s’的每个位置上插入abc,直到达到目标的s长度。但是s’越长,枚举的位置越多,时间复杂度也越大。
同样逆向的做dfs,每次找到一个abc,然后删除,但是这样也会面临相同的问题。
还有一种暴力的思路,就是replace,每一次将所有符合条件的abc,全部用空字符串替换,直到整个s,不存在abc,判断s是否是空字符串。
replace作为封装的string API,确实可以处理这个问题,但是另一方面,这个replace过程中对空间,时间上的消耗,可以思考一下。
这个问题可以抽象成为一个栈,类似于括号匹配。abc可以抽象的作为一个(),遇到字符a,可以直接入栈。遇到字符b,如果要符合条件,那么此时栈顶必须是a,也就是说,如果栈空或者栈顶!=a,说明无法满足题目的条件,返回false。否则可以将栈顶修改为b。遇到字符c,其实和字符b是一样的处理,也是只关心栈顶是否是b。
整个流程遍历一次,最大的空间就是开栈,时间复杂度ON,空间ON。
时间复杂度 O(N)
空间复杂度: O(N)
代码
public boolean isValid(String s) {while(s.indexOf("abc")!=-1){s = s.replace("abc","");}return s.equals("");}
时间复杂度 O(N)
空间复杂度: O(N)
public boolean isValid(String s) {Deque<Integer> st = new ArrayDeque();for(int i=0;i<s.length();i++){int c = s.charAt(i)-'a';if(c==0){st.push(c);continue;}if(st.isEmpty()) return false;int top = st.pop();if(c-top!=1)return false;if(c==1){st.push(c);} } return st.isEmpty(); }
代码还可以再压缩,但是基本流程是这样。
Tag
栈
相关文章:
【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效
文章目录 Check If Word Is Valid After Substitutions 检查替换后的词是否有效问题描述:分析代码 Tag Check If Word Is Valid After Substitutions 检查替换后的词是否有效 问题描述: 给你一个字符串 s ,请你判断它是否 有效 。 字符串 s…...
基于jenkinsfile布置java工程
需求 通过jenkins发布java项目到服务器 预备环境 项目地址: https://gitee.com/asaland/sb-docker-appJenkins 2.387.3 通过Jenkinsfile实现方式 jenkins ui 配置pipeline 什么是pipeline? 直接看注释吧,简单点就是编排可以多个跨时间的构建代理…...
Spring JpaTransactionManager事务管理
首先,在做关于JpaTransactionManager之前,先对Jpa做一个简单的了解,他毕竟不如hibernate那么热门,其实二者很相识,只不过后期hibernate和JDO 版本都已经兼容了其Jpa,目前大家用的少了。 JPA全称Java Persi…...
全国职业院校技能大赛网络建设与运维赛项赛题(七)
全国职业院校技能大赛 网络建设与运维 赛题 (七)...
asp.net+sqlserver企业公司进销存管理系统
基于WEB的进销存管理系统主要企业内部提供服务,系统分为管理员,和员工2部分。 在本基于WEB的进销存管理系统中分为管理员,和普通用户2中模式,其中管理人员主要是对企业内商品类型。商品信息商品的出入库信息,以及员工…...
WxGL应用实例:绘制点云
WxGL附带了几个工具函数,其中read_pcfile用来解析.ply和.pcd格式的点云文件,该函数返回一个PointCloudData类实例,包含以下属性: PointCloudData.ok - 数据是否可用,布尔型PointCloudData.info - 数据可用性说明&…...
一个月内面了30家公司,薪资从18K变成28K,真行啊····
工作3年,换了好几份工作(行业流行性大),每次工作都是裸辞。朋友都觉得不可思议。因为我一直对自己很有信心,而且特别不喜欢请假面试,对自己负责也对公司负责。 但是这次没想到市场环境非常不好,…...
《计算机网络——自顶向下方法》精炼——1.4到1.7
三更灯火五更鸡,努力学习永不止。无惧困难与挑战,砥砺前行向成功。 文章目录 引言正文时延排队时延 吞吐量协议层次,服务模型(重点)封装(重点)网络安全(选看)恶意软件的分…...
消息队列 (Message Queue)
消息队列 What 消息队列 是消息的队列;是消息的临时缓冲;是发布/订阅模式的兄弟;在多个进程/线程间实现异步通讯模式。 Why 消息队列在多个进程/线程中实现了异步通讯模式。 这里我们先介绍下同步消息处理。对于同步消息处理࿰…...
JavaScript原型链污染学习记录
1.JS原型和继承机制 0> 原型及其搜索机制 NodeJS原型机制,比较官方的定义: 我们创建的每个函数都有一个 prototype(原型)属性,这个属性是一个指针,指向一个对象, 而这个对象的用途是包含可…...
顶级白帽黑客必备的十大黑客技术
1.熟悉Linux系统和命令行操作: Linux是黑客的基石,几乎所有黑客工具和技术都是在Linux平台上运行的,熟悉Linux系统和命令行操作是必须的。 2.掌握网络协议和TCP/IP模型: 了解TCP/IP模型、网络协议和通信流程是黑客攻击的基础&a…...
【关于认证鉴权一些概念梳理】
关于认证鉴权一些概念梳理 记录一些灵感瞬间聊聊Session,Cookie和Token三剑客的特性前后端分离登录中的springsecurity与不分离的异同三更up关于springSecurity的讲解B站知乎上关于springSecurity的讲解掘金大佬SpringSecurityJWT认证流程解析一个权限对应一个资源&…...
16.网络爬虫—字体反爬(实战演示)
网络爬虫—字体反爬 一字体反爬原理二字体反爬模块FonttoolsTTF文件 三FontCreator 14.0.0.2790FontCreatorPortable下载与安装 四实战演示五后记 前言: 🏘️🏘️个人简介:以山河作礼。 🎖️🎖️:Python领域…...
BOM概述
目录 什么是BOM 浏览器对象模型(Browser Object Model (BOM)) Window对象 一些常用方法 JavaScript Window Screen Window Screen Window Screen 高度 Window Screen 可用宽度 Window Screen 可用高度 Window Screen 色深 Window Screen 像素深…...
3.Docker实用技术
Docker实用篇 0.学习目标 1.初识Docker 1.1.什么是Docker 微服务虽然具备各种各样的优势,但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中,依赖的组件非常多,不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署…...
群体无人机:协同作战的未来
摘要:本文将探讨群体无人机技术的发展及其在多个领域的应用,特别是在军事作战、救援任务和物流方面的潜力。我们将分析群体无人机在协同作战中的优势,以及如何通过协同控制和通信技术实现更高效的任务完成。 内容: 引言 简要介绍…...
如何在Windows AD域中驻留ACL后门
前言 当拿下域控权限时,为了维持权限,常常需要驻留一些后门,从而达到长期控制的目的。Windows AD域后门五花八门,除了常规的的添加隐藏用户、启动项、计划任务、抓取登录时的密码,还有一些基于ACL的后门。 ACL介绍 …...
LVGL移植——stm32f4
LVGL移植说明 移植LVGL版本:8.3.6 主控:STM32F407ZGT6 github链接:https://github.com/lvgl/lvgl.git 文章目录 LVGL移植说明STM32移植LVGL①需要的依赖文件②移植显示驱动文件③将文件加入工程当中④配置心跳④修改栈堆的空间⑤编译链接 STM…...
ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7
编辑:ll ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7 型号:ADP5054ACPZ-R7 品牌:ADI/亚德诺 封装:LFCSP-48 批号:2023 引脚数量:48 工作温度:-40C~125C 安装类型:表…...
TCP/IP相关面试题
1. 什么是TCP/IP协议?它的作用是什么? TCP/IP(Transmission Control Protocol/Internet Protocol)互联网中最常用的协议,是计算机网络通信的基础。由TCP协议和IP协议两部分组成。IP协议负责数据的传输和路由选择&#…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
