双指针法02

2024-09-07 12:12
文章标签 指针 02

本文主要是介绍双指针法02,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

844. 比较含退格的字符串

给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

示例 1:

输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。

示例 2:

输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。

示例 3:

输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。

提示:

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶:

  • 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?

遇到这道题,我第一反应是利用栈,顺序进栈而后遇到'#'则出栈,以下则用StringBuilder实现进栈与出栈的过程

class Solution {public boolean backspaceCompare(String s, String t) {return getResult(s).equals(getResult(t));}public String getResult(String res) {StringBuilder sb = new StringBuilder();for (int i = 0; i < res.length(); i++){if(res.charAt(i) != '#') {sb.append(res.charAt(i)); // 进栈}else {if(sb.length() > 0) {sb.deleteCharAt(sb.length() - 1); // 出栈}}}return sb.toString();}
}

这里利用StringBuilder的append 和 deleteCharAt 方法实现了元素的进栈和出栈。但我们细细思考(看过题解) 会发现其实还有其他解法,双指针就是一个效率很高的解法。

class Solution {public boolean backspaceCompare(String s, String t) {int i = s.length() - 1 , j = t.length() - 1;int skipS = 0 , skipT = 0;// ***********************************************************// 这里利用双指针的思想,跳过'#' 和一些被删除的元素while(i >= 0 || j >= 0) {while(i >= 0){if(s.charAt(i) == '#') {skipS++;i--;}else if(skipS > 0) {skipS--;i--;}else {break;}}while(j >= 0) {if(t.charAt(j) == '#') {skipT++;j--;}else if(skipT > 0) {skipT--;j--;} else {break;}}// **********************************************************// 这里从后往前依次比较,对应位置字符不同则返回falseif(i >= 0 && j >= 0) {if (s.charAt(i) != t.charAt(j)) {return false;}}else {  // 这里则是为了避免ca#abc 和 abc 可能返回true的错误if(i >= 0 || j >= 0) {return false;}}i--;j--;}return true;}
}

 

这篇关于双指针法02的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145023

相关文章

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

Git 的特点—— Git 学习笔记 02

文章目录 Git 简史Git 的特点直接记录快照,而非差异比较近乎所有操作都是本地执行保证完整性一般只添加数据 参考资料 Git 简史 众所周知,Linux 内核开源项目有着为数众多的参与者。这么多人在世界各地为 Linux 编写代码,那Linux 的代码是如何管理的呢?事实是在 2002 年以前,世界各地的开发者把源代码通过 diff 的方式发给 Linus,然后由 Linus

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

MySQL record 02 part

查看已建数据库的基本信息: show CREATE DATABASE mydb; 注意,是DATABASE 不是 DATABASEs, 命令成功执行后,回显的信息有: CREATE DATABASE mydb /*!40100 DEFAULT CHARACTER SET utf8mb3 / /!80016 DEFAULT ENCRYPTION=‘N’ / CREATE DATABASE myd

【C++】作用域指针、智能指针、共享指针、弱指针

十、智能指针、共享指针 从上篇文章 【C++】如何用C++创建对象,理解作用域、堆栈、内存分配-CSDN博客 中我们知道,你的对象是创建在栈上还是在堆上,最大的区别就是对象的作用域不一样。所以在C++中,一旦程序进入另外一个作用域,那其他作用域的对象就自动销毁了。这种机制有好有坏。我们可以利用这个机制,比如可以自动化我们的代码,像智能指针、作用域锁(scoped_lock)等都是利用了这种机制。

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 (1)任务并行 (2)数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间,需要在两者之间相互传输数据。 (1)分配GPU内存 (2)将CPU上的数据复制到GPU上 (3)在GPU上对数据进行计算操作 (4)将计算结果从GPU复制到CPU上 (5)释放GPU内存 CUDA内存管理API (1)分配内存 cudaErro

MFC中App,Doc,MainFrame,View各指针的互相获取

纸上得来终觉浅,为了熟悉获取方法,我建了个SDI。 首先说明这四个类的执行顺序是App->Doc->Main->View 另外添加CDialog类获得各个指针的方法。 多文档的获取有点小区别,有时间也总结一下。 //  App void CSDIApp::OnApp() {      //  App      //  Doc     CDocument *pD

C和指针:结构体(struct)和联合(union)

结构体和联合 结构体 结构体包含一些数据成员,每个成员可能具有不同的类型。 数组的元素长度相同,可以通过下标访问(转换为指针)。但是结构体的成员可能长度不同,所以不能用下标来访问它们。成员有自己的名字,可以通过名字访问成员。 结构声明 在声明结构时,必须列出它包含的所有成员。 struct tag {member-list} variable-list ; 定义一个结构体变量x(包含

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis