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

Leetcode.2337 移动片段得到字符串

题目链接

Leetcode.2337 移动片段得到字符串 rating : 1693

题目描述

给你两个字符串 starttarget ,长度均为 n n n 。每个字符串 仅 由字符 'L''R''_' 组成,其中:

  • 字符 'L''R' 表示片段,其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 移动,而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 移动。
  • 字符 '_' 表示可以被 任意 'L''R' 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ,返回 true ;否则,返回 false

示例 1:

输入:start = “L__R__R”, target = “L______RR”
输出:true
解释:可以从字符串 start 获得 target ,需要进行下面的移动:

  • 将第一个片段向左移动一步,字符串现在变为 “L___R__R_” 。
  • 将最后一个片段向右移动一步,字符串现在变为 “L___R___R” 。
  • 将第二个片段向右移动三步,字符串现在变为 “L______RR” 。 可以从字符串 start 得到 target ,所以返回 true 。

示例 2:

输入:start = “R_L_”, target = “__LR”
输出:false
解释:字符串 start 中的 ‘R’ 片段可以向右移动一步得到 “RL” 。
但是,在这一步之后,不存在可以移动的片段,所以无法从字符串 start 得到 target 。

示例 3:

输入:start = “R", target = "R
输出:false
解释:字符串 start 中的片段只能向右移动,所以无法从字符串 start 得到 target 。

提示:

  • n = s t a r t . l e n g t h = t a r g e t . l e n g t h n = start.length = target.length n=start.length=target.length
  • 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105
  • starttarget 由字符 'L''R''_' 组成

解法:双指针

如果 start 能够转成 target,说明把 starttarget 中间的 _ 都去掉,二者还是相同的,否则不能进行转换。

接下来用两个指针 i i i j j j 分别指向,starttarget 的起始位置,开始遍历:

  • 如果 start[i] = '_' 或者 target[j] = '_',都跳过;
  • 如果 start[i] = 'L',并且 i < j i < j i<j,由于 'L'不能向 移动,所以此时不能转换,直接返回 false
  • 如果 start[i] = 'R',并且 i > j i > j i>j,由于 'R'不能向 移动,所以此时不能转换,直接返回 false

最后没问题就返回 true

时间复杂度: O ( n ) O(n) O(n)

C++代码:

class Solution {
public:bool canChange(string start, string target) {auto s = start , t = target;s.erase(remove(s.begin(),s.end(),'_'),s.end());t.erase(remove(t.begin(),t.end(),'_'),t.end());if(s != t) return false;int n = start.size();for(int i = 0,j = 0;i < n;i++){if(start[i] == '_') continue;while(j < n && target[j] == '_') j++;if(i != j){if(start[i] == 'L' && i < j) return false;else if(start[i] == 'R' && i > j) return false;}j++;}       return true; }
};

相关文章:

Leetcode.2337 移动片段得到字符串

题目链接 Leetcode.2337 移动片段得到字符串 rating : 1693 题目描述 给你两个字符串 start 和 target &#xff0c;长度均为 n n n 。每个字符串 仅 由字符 L、R 和 _ 组成&#xff0c;其中&#xff1a; 字符 L 和 R 表示片段&#xff0c;其中片段 L 只有在其左侧直接存在一…...

【vue】更改角色权限后,实现页面不刷新更改其可展示的导航菜单

登入的角色本身属于领导级别&#xff08;集团权限&#xff09;&#xff0c;没有下级的不同权限&#xff1a; 切换不同身份&#xff08;公司&#xff09;&#xff0c;以获得相应部门的不同导航菜单及权限 这里实现&#xff1a;更改角色权限后&#xff0c;实现页面 不刷新 更改…...

【G-LAB】网络工程师常用排错命令详细版

网络工程师在日常配置中难免出现各种配置错误&#xff0c;比如接口地址配错、掩码位数配错、接口忘记no shutdown。除去这些基础错误&#xff0c;在配置各种路由选择协议时也会因为网络类型、邻居类型、区域和路由器层级等各种问题使邻居无法建立、路由无法传递进而导致网络不通…...

Linux 桌面版关闭GUI桌面环境

持久打开和关闭 通过CtrlAltF1-F6快捷键进入命令行界面 执行以下命令&#xff0c;持久关闭Ubuntu桌面版的GUI环境&#xff1a; sudo systemctl set-default multi-user.target执行以下命令&#xff0c;持久开启Ubuntu桌面版的GUI环境 通过CtrlAltF7快捷键进入GUI界面 sudo s…...

ChatGPT能代替搜索引擎吗?ChatGPT和搜索引擎有什么区别?

ChatGPT和搜索引擎是两种在信息获取和交流中常用的工具&#xff0c;ChatGPT是一种基于人工智能技术的聊天机器人&#xff0c;而搜索引擎是一种在互联网上搜索信息的工具。尽管它们都是依托互联网与信息获取和交流有关&#xff0c;部分功能重合&#xff0c;但在很多方面存在着明…...

PHP海外代购管理系统mysql数据库web结构apache计算机软件工程网页wamp

一、源码特点 PHP 海外代购管理系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 代码下载 https://download.csdn.net/download/qq_41221322/88229435 论文 https://…...

游戏反外挂方案解析

近年来&#xff0c;游戏市场高速发展&#xff0c;随之而来的还有图谋利益的游戏黑产。在利益吸引下&#xff0c;游戏黑产扩张迅猛&#xff0c;已发展成具有庞大规模的产业链&#xff0c;市面上游戏受其侵扰的案例屡见不鲜。 据《FairGuard游戏安全2022年度报告》数据统计&…...

基于郊狼算法优化的BP神经网络(预测应用) - 附代码

基于郊狼算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于郊狼算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.郊狼优化BP神经网络2.1 BP神经网络参数设置2.2 郊狼算法应用 4.测试结果&#xff1a;5.Matlab代码 摘要…...

【腾讯云 TDSQL-C Serverless 产品测评】全面测评TDSQL-C Mysql Serverless

全面测评TDSQL-C Mysql Serverless 文章目录 全面测评TDSQL-C Mysql Serverless前言什么是TDSQL-C Mysql Serverless初始化 TDSQL-C Mysql Serverless新建数据库建立数据表开启外网访问 兼容性SQL文件 导入导出navicat 直接在线传输 构建测试环境准备Python测试脚本准备 Jmeter…...

Qt应用开发(基础篇)——纯文本编辑窗口 QPlainTextEdit

一、前言 QPlainTextEdit类继承于QAbstractScrollArea&#xff0c;QAbstractScrollArea继承于QFrame&#xff0c;是Qt用来显示和编辑纯文本的窗口。 滚屏区域基类https://blog.csdn.net/u014491932/article/details/132245486?spm1001.2014.3001.5501框架类QFramehttps://blo…...

数据结构-->栈

&#x1f495;休对故人思故国&#xff0c;且将新火试新茶&#xff0c;诗酒趁年华&#x1f495; 作者&#xff1a;Mylvzi 文章主要内容&#xff1a;详解链表OJ题 前言&#xff1a; 前面已经学习过顺序表&#xff0c;链表。他们都是线性表&#xff0c;今天要学习的栈也是一种线…...

强训第36天

C D C 193--1100 0001 194--1100 0010 196--1100 0100 198--1100 0110 能包括全部的且最小的为 1100 0xxx xxx为主机号&#xff0c;站三位 B MAC地址是绑定网卡的&#xff0c;全球唯一 D A C D IP网段 17为网络号 所以是 40.15.1aaa aaa(7位主机号).0 因为要划分2个子网 所以…...

PyTorch bug记录

1、RuntimeError: Input type (torch.FloatTensor) and weight type (torch.cuda.FloatTensor) should be the same 这个错误是因为模型的权重是在GPU上&#xff0c;但是输入数据在CPU上。在PyTorch中&#xff0c;Tensor的类型和所在的设备&#xff08;CPU或GPU&#xff09;需…...

js中的正则表达式(一)

目录 1.什么是正则表达式 2.正则表达式在JavaScript中的使用场景: 3.正则表达式的语法&#xff1a; 1.什么是正则表达式 正则表达式(Regular Expression&#xff09;是用于匹配字符串中字符组合的模式。在JavaScript中&#xff0c;正则表达式也是对象通常用来查找、替换那些符…...

免费开源使用的几款红黑网络流量工具,自动化的多功能网络侦查工具、超级关键词URL采集工具、Burpsuite被动扫描流量转发插件

免费开源使用的几款红黑网络流量工具&#xff0c;自动化的多功能网络侦查工具、超级关键词URL采集工具、Burpsuite被动扫描流量转发插件。 #################### 免责声明&#xff1a;工具本身并无好坏&#xff0c;希望大家以遵守《网络安全法》相关法律为前提来使用该工具&am…...

使用Mybatis Plus进行DAO层开发

一、特性 Mybatis应该大家现在都知道&#xff0c;而且在项目中都在使用&#xff0c;因为这块ORM框架让大家能专心业务SQL的编写&#xff0c;数据库的连接&#xff0c;连接池的使用都不用关心&#xff0c;极大的提高了生产效率。 今天要给大家介绍的另外一款ORM框架&#xff0…...

Android中如何不编译源生模块

如果想让自己的app 替换系统的app 比如使用闪电浏览器替换系统的Browser 首先把闪电浏览器放到 vendor/rockchip/common/apps Android.mk LOCAL_PATH : $(call my-dir) include $(CLEAR_VARS)LOCAL_MODULE : Lightning LOCAL_SRC_FILES : $(LOCAL_MODULE).apk LOCAL_MODULE_C…...

安装Vue_dev_tools

Vue控制台出现Download the Vue Devtools extension for a better development experience: 下载Vue_dev_tools,这里给出网盘链接&#xff0c;有Vue2和Vue3的&#xff0c;dev_tools 以Google浏览器为例 点击设置&#xff08;就是那三个点&#xff09;->扩展程序->管理扩…...

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)

【数据结构入门指南】二叉树顺序结构: 堆及实现&#xff08;全程配图&#xff0c;非常经典&#xff09; 一、前言&#xff1a;二叉树的顺序结构二、堆的概念及结构三、堆的实现&#xff08;本篇博客以实现小堆为例&#xff09;3.1 准备工作3.2 初始化3.3 堆的插入3.3.1 向上调…...

css实现三角形的几种方法

css实现三角形的方法&#xff1a;1、使用边框实现三角形&#xff0c;利用透明边框和实色边框的组合&#xff0c;可以创建不同方向和大小的三角形&#xff1b;2、使用伪元素实现三角形&#xff0c;通过使用伪元素来创建一个占据父元素一半大小的实心三角形&#xff1b;3、使用tr…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...