代码随想录算法训练营day09|| 字符串总结 、双指针回顾

字符串总结

  • 什么是字符串

字符串是若干字符组成的有限序列,也可以理解为是一个字符数组,但是很多语言对字符串做了特殊的规定,

  • 要不要使用库函数

打基础的时候,不要太迷恋于库函数。

甚至一些同学习惯于调用substr,split,reverse之类的库函数,却不知道其实现原理,也不知道其时间复杂度,这样实现出来的代码,如果在面试现场,面试官问:“分析其时间复杂度”的话,一定会一脸懵逼!

所以建议如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。

如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。

  • 双指针法

在344.反转字符串 (opens new window),我们使用双指针法实现了反转字符串的操作,双指针法在数组,链表和字符串中很常用。

接着在字符串:替换空格 (opens new window),同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。

其实很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。

那么针对数组删除操作的问题,其实在27. 移除元素 (opens new window)中就已经提到了使用双指针法进行移除操作。

同样的道理在151.翻转字符串里的单词 (opens new window)中我们使用O(n)的时间复杂度,完成了删除冗余空格。

一些同学会使用for循环里调用库函数erase来移除元素,这其实是O(n^2)的操作,因为erase就是O(n)的操作,所以这也是典型的不知道库函数的时间复杂度,上来就用的案例了。

  •  反转系列

在反转上还可以在加一些玩法,其实考察的是对代码的掌控能力。

541. 反转字符串II (opens new window)中,一些同学可能为了处理逻辑:每隔2k个字符的前k的字符,写了一堆逻辑代码或者再搞一个计数器,来统计2k,再统计前k个字符。

其实当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章

只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点,这样写程序会高效很多。

在151.翻转字符串里的单词 (opens new window)中要求翻转字符串里的单词,这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。

这道题目通过 先整体反转再局部反转,实现了反转字符串里的单词。

后来发现反转字符串还有一个牛逼的用处,就是达到左旋的效果。

在字符串:反转个字符串还有这个用处? (opens new window)中,我们通过先局部反转再整体反转达到了左旋的效果。

  • KMP

KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。

KMP的精髓所在就是前缀表,在KMP精讲 (opens new window)中提到了,什么是KMP,什么是前缀表,以及为什么要用前缀表。

前缀表:起始位置到下标i之前(包括i)的子串中,有多大长度的相同前缀后缀。

那么使用KMP可以解决两类经典问题:

  1. 匹配问题:28. 实现 strStr()(opens new window)
  2. 重复子串问题:459.重复的子字符串(opens new window)

再一次强调了什么是前缀,什么是后缀,什么又是最长相等前后缀。

前缀:指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀:指不包含第一个字符的所有以最后一个字符结尾的连续子串。

然后针对前缀表到底要不要减一,这其实是不同KMP实现的方式,我们在KMP精讲 (opens new window)中针对之前两个问题,分别给出了两个不同版本的的KMP实现。

其中主要理解j=next[x]这一步最为关键!

  • 总结

字符串类类型的题目,往往想法比较简单,但是实现起来并不容易,复杂的字符串题目非常考验对代码的掌控能力。

双指针法是字符串处理的常客。

KMP算法是字符串查找最重要的算法,但彻底理解KMP并不容易,我们已经写了五篇KMP的文章,不断总结和完善,最终才把KMP讲清楚。

双指针法总结

相信大家已经对双指针法很熟悉了,但是双指针法并不隶属于某一种数据结构,我们在讲解数组,链表,字符串都用到了双指针法,所有有必要针对双指针法做一个总结。

  • 数组篇

在数组:就移除个元素很难么? (opens new window)中,原地移除数组上的元素,我们说到了数组上的元素,不能真正的删除,只能覆盖。

一些同学可能会写出如下代码(伪代码):

for (int i = 0; i < array.size(); i++) {
    if (array[i] == target) {
        array.erase(i);
    }
}

这个代码看上去好像是O(n)的时间复杂度,其实是O(n^2)的时间复杂度,因为erase操作也是O(n)的操作。

所以此时使用双指针法才展现出效率的优势:通过两个指针在一个for循环下完成两个for循环的工作。

  •  字符串篇

在字符串:这道题目,使用库函数一行代码搞定 (opens new window)中讲解了反转字符串,注意这里强调要原地反转,要不然就失去了题目的意义。

使用双指针法,定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。,时间复杂度是O(n)。

在替换空格 (opens new window)中介绍使用双指针填充字符串的方法,如果想把这道题目做到极致,就不要只用额外的辅助空间了!

思路就是首先扩充数组到每个空格替换成"%20"之后的大小。然后双指针从后向前替换空格。

有同学问了,为什么要从后向前填充,从前向后填充不行么?

从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组(字符串)填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。

那么在字符串:花式反转还不够! (opens new window)中,我们使用双指针法,用O(n)的时间复杂度完成字符串删除类的操作,因为题目要删除冗余空格。

在删除冗余空格的过程中,如果不注意代码效率,很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。

主要还是大家用erase用的比较随意,一定要注意for循环下用erase的情况,一般可以用双指针写效率更高!

  • 链表篇

翻转链表是现场面试,白纸写代码的好题,考察了候选者对链表以及指针的熟悉程度,而且代码也不长,适合在白纸上写。

在链表:听说过两天反转链表又写不出来了? (opens new window)中,讲如何使用双指针法来翻转链表,只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表。

思路还是很简单的,代码也不长,但是想在白纸上一次性写出bugfree的代码,并不是容易的事情。

在链表中求环,应该是双指针在链表里最经典的应用,在链表:环找到了,那入口呢? (opens new window)中讲解了如何通过双指针判断是否有环,而且还要找到环的入口。

使用快慢指针(双指针法),分别定义 fast 和 slow指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。

那么找到环的入口,其实需要点简单的数学推理,我在文章中把找环的入口清清楚楚的推理的一遍,如果对找环入口不够清楚的同学建议自己看一看链表:环找到了,那入口呢? (opens new window)。

  • N数之和篇

在哈希表:解决了两数之和,那么能解决三数之和么? (opens new window)中,讲到使用哈希法可以解决1.两数之和的问题

其实使用双指针也可以解决1.两数之和的问题,只不过1.两数之和求的是两个元素的下标,没法用双指针,如果改成求具体两个元素的数值就可以了,大家可以尝试用双指针做一个leetcode上两数之和的题目,就可以体会到我说的意思了。

使用了哈希法解决了两数之和,但是哈希法并不使用于三数之和!

使用哈希法的过程中要把符合条件的三元组放进vector中,然后在去去重,这样是非常费时的,很容易超时,也是三数之和通过率如此之低的根源所在。

去重的过程不好处理,有很多小细节,如果在面试中很难想到位。

时间复杂度可以做到O(n^2),但还是比较费时的,因为不好做剪枝操作。

所以这道题目使用双指针法才是最为合适的,用双指针做这道题目才能就能真正体会到,通过前后两个指针不算向中间逼近,在一个for循环下完成两个for循环的工作。

只用双指针法时间复杂度为O(n^2),但比哈希法的O(n^2)效率高得多,哈希法在使用两层for循环的时候,能做的剪枝操作很有限。

在双指针法:一样的道理,能解决四数之和 (opens new window)中,讲到了四数之和,其实思路是一样的,在三数之和的基础上再套一层for循环,依然是使用双指针法。

对于三数之和使用双指针法就是将原本暴力O(n^3)的解法,降为O(n^2)的解法,四数之和的双指针解法就是将原本暴力O(n^4)的解法,降为O(n^3)的解法。

同样的道理,五数之和,n数之和都是在这个基础上累加

 总结:

本文中一共介绍了leetcode上九道使用双指针解决问题的经典题目,除了链表一些题目一定要使用双指针,其他题目都是使用双指针来提高效率,一般是将O(n^2)的时间复杂度,降为$O(n)$。

建议大家可以把文中涉及到的题目在好好做一做,琢磨琢磨,基本对双指针法就不在话下了。

双指针题目练习:

27.移除元素

344.反转字符串

卡码网54.替换数字

151.翻转字符串里的单词

206.反转链表

19.删除链表的倒数第N个节点

160.链表相交(面试题 02.07. 链表相交)

142.环形链表II

15. 三数之和

18. 四数之和

参考链接:代码随想录

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/373020.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

uWSGI、灰度发布、网站数据指标分析、网站限速

1 案例1&#xff1a;部署Python网站项目 1.1 问题 配置Nginx使其可以将动态访问转交给uWSGI&#xff1a; 1.2 方案 安装Python工具及依赖 安装uWSGI并编写配置文件 1.3 步骤 实现此案例需要按照如下步骤进行。 步骤一&#xff1a; 首先$教学资料目录/python拷贝到虚拟…

Python程序设计 函数

简单函数 函数&#xff1a;就是封装了一段可被重复调用执行的代码块。通过此代码块可以实现大量代码的重复使用。 函数的使用包含两个步骤&#xff1a; 定义函数 —— 封装 独立的功能 调用函数 —— 享受 封装 的成果 函数的作用&#xff0c;在开发程序时&#xff0c;使用…

Unity3d Shader篇(一)— 顶点漫反射着色器解析

文章目录 前言一、顶点漫反射着色器是什么&#xff1f;1. 顶点漫反射着色器的工作原理 二、编写顶点漫反射着色器1. 定义属性2. 创建 SubShader3. 编写着色器程序段4. 完成顶点着色器5. 完成片段着色器 三、效果四、总结 前言 在 Unity 中&#xff0c;Shader 可以用来实现各种…

jmeter设置关联

一、为什么要设置关联&#xff1f; http协议本身是无状态的&#xff0c;客户端只需要简单向服务器请求下载某些文件&#xff0c;无论是客户端还是服务端都不去记录彼此过去的行为&#xff0c;每一次请求之间都是独立的。如果jmeter需要设置跨线程组脚本&#xff0c;就必须设置…

【问题篇】activiti工作流转办并处理备注问题

当处理activiti转办问题时&#xff0c;需要做的就是处理审批人和备注问题。 处理的思路是&#xff0c;先将当前环节标志成转办标签&#xff0c;再通过BUSINESS_KEY_找到流程实例的历史记录&#xff0c;找到最新的一条复制一份出来&#xff0c;表示需要转办到的人的历史记录并设…

APP专项测试方法总结

APP专项测试 1、网络测试 可使用抓包工具辅助网格测试推荐&#xff1a;fiddler&#xff0c;Charles 网络切换&#xff1a; 2G-3G-4G-wifi-网络信号差–无网 网络信号弱&#xff1a; 关注是否出现ANR、crash 2、中断测试 意外中断&#xff1a; 来电&#xff1b;短信&am…

不需英文基础也可以轻松学编程,中文编程开发工具免费版下载,编程工具构件箱之扩展控制面板构件用法

不需英文基础也可以轻松学编程&#xff0c;中文编程开发工具免费版下载&#xff0c;编程工具构件箱之扩展控制面板构件用法 一、前言 编程入门视频教程链接 https://edu.csdn.net/course/detail/39036 编程工具及实例源码文件下载可以点击最下方官网卡片——软件下载——常…

ShardingSphere 5.x 系列【3】分库分表中间件技术选型

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Spring Boot 版本 3.1.0 本系列ShardingSphere 版本 5.4.0 源码地址&#xff1a;https://gitee.com/pearl-organization/study-sharding-sphere-demo 文章目录 1. 前言2. My Cat3. ShardingSphe…

C++ 类与对象(下)

目录 1. 再谈构造函数 1.1 构造函数体赋值 1.2 初始化列表 1.3 explicit关键字 2. static成员 2.1 概念 2.2 特性 3.友元 3.1友元函数 3.2 友元类 4. 内部类 5.匿名对象 6.拷贝对象时的一些编译器优化 7. 再次理解类和对象 【本节目标】 1. 再谈构造函数 2. Static成员…

【产品升级】SmartPipe升级到版本2.0

在近一个月的攻关和测试下&#xff0c;SmartPipe软件轴线自动识别算法的性能大幅提升&#xff0c;鲁棒性和稳定性进一步增强。近一年来客户累计反馈的多种复杂管路&#xff08;包括带有支管管路、带有压瘪段管路、推弯管、装配管、带有复杂孔洞管路等&#xff09;现在均能够正确…

通过消息队列实现进程之间通信代码

#include <myhead.h> struct msgbuf {long int mtype; char mtext[1024]; }; //定义一个消息大小 #define MSGSIZE sizeof(struct msgbuf)-sizeof(long int) int main(int argc, const char *argv[]) {//1、创建key值以便创建消息队列key_t key ftok("/", k)…

Bootstrap5 图片轮播

Bootstrap5 轮播样式表使用的是CDN资源 <title>亚丁号</title><!-- 自定义样式表 --><link href"static/front/css/front.css" rel"stylesheet" /><!-- 新 Bootstrap5 核心 CSS 文件 --><link rel"stylesheet"…

STM32WLE5JC

Sub-GHz 无线电介绍 sub-GHz无线电是一种超低功耗sub-GHz无线电&#xff0c;工作在150-960MHz ISM频段。 在发送和接收中采用LoRa和&#xff08;G&#xff09;FSK调制&#xff0c;仅在发送中采用BPSK/(G)MSK调制&#xff0c;可以在距离、数据速率和功耗之间实现最佳权衡。 这…

freeswitch对接FunASR实时语音听写

1、镜像启动 通过下述命令拉取并启动FunASR软件包的docker镜像&#xff1a; sudo docker pull \registry.cn-hangzhou.aliyuncs.com/funasr_repo/funasr:funasr-runtime-sdk-online-cpu-0.1.7 mkdir -p ./funasr-runtime-resources/models sudo docker run -p 10096:10095 -i…

【Gephi项目实战-带数据集】利用gephi绘制微博肖战超话120位用户关系图,并计算整体网络指标与节点指标

数据集在评论区&#xff0c;B站演示视频在评论区&#xff01; 简介 最近2天需要用到gephi做社会网络分析&#xff0c;于是从0开始接触gephi并摸索出了gephi的基本使用指南。下面将结合真实的节点文件与边文件&#xff0c;利用gephi绘制社会网络并计算相关测量指标。整个过程会…

我们都是宇宙的奇迹

我们都是独一无二的个体&#xff0c;是宇宙的奇迹 如果我不关注自我&#xff0c;那我在这个宏大的宇宙中有什么意义&#xff1f; 关于你的问题&#xff0c;我想没有一个简单的答案&#xff0c;因为不同的人可能有不同的看法和感受。有些人可能认为&#xff0c;如果不关注自我&…

jbdc的简单了解

JDBC JDBC所处的位置 JDBC的本质 Java操作数据库的一套接口。 补充 ddl:数据库定义语言,例如建表,创建数据库等。 dml:数据库操作语言,例如增删改。 dql:数据库查询语言,例如查询语句。 注意 在创建Java项目后的第一个步骤是导入jar包。 导入jar包的步骤 1 创建l…

【C语言】const修饰指针的不同作用

目录 const修饰变量 const修饰指针变量 ①不用const修饰 ②const放在*的左边 ③const放在*的右边 ④*的左右两边都有const 结论 const修饰变量 变量是可以修改的&#xff0c;如果把变量的地址交给⼀个指针变量&#xff0c;通过指针变量的也可以修改这个变量。 但…

TCP/IP详细介绍以及TCP/IP寻址

目录 ​编辑 1. TCP/IP 介绍 2. 计算机通信协议&#xff08;Computer Communication Protocol&#xff09; 3. 什么是 TCP/IP&#xff1f; 4. 在 TCP/IP 内部 5. TCP 使用固定的连接 6. IP 是无连接的 7. IP 路由器 8. TCP/IP 9. TCP/IP 寻址 10. IP地址 …

LeetCode、1137. 第 N 个泰波那契数【简单,动态规划】

文章目录 前言LeetCode、1137. 第 N 个泰波那契数【简单&#xff0c;动态规划】题目与分类思路一维动态规划 资料获取 前言 博主介绍&#xff1a;✌目前全网粉丝2W&#xff0c;csdn博客专家、Java领域优质创作者&#xff0c;博客之星、阿里云平台优质作者、专注于Java后端技术…
最新文章