力扣字符串--总结篇

前言

字符串学了三天,七道题。初窥kmp,已经感受到算法的博大精深了。

内容

对字符串的操作可以归结为以下几类:

字符串的比较、连接操作(不同编程语言实现方式有所不同);

涉及子串的操作,比如前缀,后缀等;

字符串间的匹配操作,如 KMP 算法、BM 算法等。

一些注意点 

注意双引号和单引号

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

Go 语言中的字符串和其他高级语言(Java、C#)一样,默认是不可变的(immutable)。字符串不可变有很多好处:

如天生线程安全,大家使用的都是只读对象,无须加锁;

再者,方便内存共享,而不必使用写时复制(Copy On Write)等技术;

字符串 hash 值也只需要制作一份。

修改字符串时,可以将字符串转换为 []byte 进行修改。

[]byte 和 string 可以通过强制类型转换互转。

不要太迷恋于库函数

一些思路
双指针
整体+局部思想

先整体操作,后局部操作;或者先局部操作,再整体操作。

如将整个字符串反转,再将每个单词反转。

构建新的字符串

如复制原字符串str=s+s

kmp算法

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

前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配

什么是前缀表:记录下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。

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

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

构造next数组其实就是计算模式串s,前缀表的过程。 主要有如下三步:

初始化

处理前后缀不相同的情况

处理前后缀相同的情况

主要是把前缀表next[ ]求出来,然后根据题目要求,利用和前缀表的关系求解

最后

下一站,栈与队列!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Electron-vue出现GET http://localhost:9080/__webpack_hmr net::ERR_ABORTED解决方案

GET http://localhost:9080/__webpack_hmr net::ERR_ABORTED解决方案 使用版本解决方案解决总结 使用版本 以下是我解决此问题时使用的electron和vue等的一些版本信息 【附】经过测试 electron 的版本为 13.1.4 时也能解决 解决方案 将项目下的 .electron-vue/dev-runner.js…

【PWN · ret2csu】[HNCTF 2022 WEEK2]ret2csu

记一道ret2csu 一、题目 二、思路 1.ret2csu用write泄露write的真实地址->泄露libc->获得system的真实地址 2.ret2csu用read写/bin/sh字符串到bss段上 3.ret2csu用write将system的真实地址写到bss段上 4.ret2csu调用system 三、exp from pwn import * from pwn impo…

[100天算法】-最短无序连续子数组(day 70)

题目描述 给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。你找到的子数组应是最短的,请输出它的长度。示例 1:输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要…

Linux下内网穿透实现云原生观测分析工具的远程访问

📑前言 本文主要是Linux下内网穿透实现云原生观测分析工具的远程访问设置的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是青衿🥇 ☁️博客首页:CSDN主页放风讲故事 &…

[C/C++]数据结构 链表OJ题:环形链表(如何判断链表是否有环)

题目描述: 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&…

Docker+K8s基础(重要知识点总结)

目录 一、Docker的核心1,Docker引擎2,Docker基础命令3,单个容器运行多个服务进程4,多个容器运行多个服务进程5,备份在容器中运行的数据库6,在宿主机和容器之间共享数据7,在容器之间共享数据8&am…

OSG交互:选中场景模型并高亮显示

1、目的 可以在osg视图中选中指定模型实体,并高亮显示。共分为两种,一种鼠标点选,一种框选。 2、鼠标点选 2.1 功能说明 生成两组对象,一组cow对象可以被选中,另一组robot不能被选中;点击cow对象被选中高亮,点击robot被选中不高亮;点击空白处,弹出“select nothing!…

P6入门:项目初始化2-项目详情之日期Date

前言 使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等&…

STM32H743XX/STM32H563XX芯片烧录一次后,再次上电无法烧录

近期在使用STM32H563ZIT6这款芯片在开发板上使用正常,烧录到自己打的板子就遇到了芯片烧录一次后,再次上电无法烧录的问题。 遇到问题需要从以下5点进行分析。 首先看下开发板的原理图 1.BOOT0需要拉高。 2.NRST脚在开发板上是悬空的。这里我建议大家…

远程电脑未连接显示器时分辨率太小的问题处理

背景:单位电脑显示器坏了,使用笔记本通过向日葵远程连接,发现分辨率只有800*600并且不能修改,网上找了好久找到了处理方法这里记录一下,主要用到的是一个虚拟显示器软件usbmmidd_v2 1)下载usbmmidd_v2 2)…

2022年12月 Python(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 有n个按名称排序的商品,使用对分查找法搜索任何一商品,最多查找次数为5次,则n的值可能为?()(2分) A.5 B.15 C.30 D.35 答案:C 答案解析:对分查找最多查找次数m与个数之间n的…

【星海随笔】SDN neutron (一)

一、SDN的原理: 控制平面与数据平面分离:传统网络中,网络设备同时承担控制和数据转发功能,而SDN将这两个功能分离,使得网络控制集中在一个中心控制器上。 中心控制器:SDN架构中的中心控制器负责网络的全局…

一个“Hello, World”Flask应用程序

如果您访问Flask网站,会看到一个非常简单的示例应用程序,只有5行代码。为了不重复那个简单的示例,我将向您展示一个稍微复杂一些的示例,它将为您编写大型应用程序提供一个良好的基础结构。 应用程序将存在于包中。在Python中&…

aosp定制android系统

目录 AOSP 准备工作(配置) 确定机型和版本 初始化 git安装 curl安装 同步源码 环境变量 创建aosp目录 指定同步版本 解下来安装编译需要的依赖 编译aosp源码 刷入系统 AOSP 全称 Android Open Source Project 是指Android开源项目,它是由Google主导的…

gird 卡片布局

场景一:单元格大小相等 这承载了所有 CSS Grid 中最著名的片段,也是有史以来最伟大的 CSS 技巧之一: 等宽网格响应式卡片实现 .section-content {display: grid;grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));gap: 10px; …

list部分接口模拟实现(c++)

List list简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造 push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator->() insert()erase()clear()析构函数迭代器区间构造拷贝构造operator() list简介 - list可以在…

使用 pubsub-js 进行消息发布订阅

npm 包地址 github 包地址 pubsub-js 是一个轻量级的 JavaScript 基于主题的消息订阅发布库 ,压缩后小于1b。它具有使用简单、性能高效、支持多平台等优点,可以很好地满足各种需求。 功能特点: 无依赖同步解耦ES3 兼容。pubsub-js 能够在…

Angular 由一个bug说起之一:List / Grid的性能问题

在angular中,MatTable构建简单,使用范围广。但某些时候会出现卡顿 卡顿情景: 1:一次性请求太多的数据 2:一次性渲染太多数据,这会花费CPU很多时间 3:行内嵌套复杂的元素 4:使用过多的…

11月份 四川汽车托运报价已经上线

中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到💥 核算下来不过几毛钱💰 相比起自驾的漫长和疲惫🚗 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …

LeetCode 17. 电话号码的字母组合 中等

题目 - 点击直达 1. 17. 电话号码的字母组合 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 3. 知识与收获 1. 17. 电话号码的字母组合 中等 1. 题目详情 1. 原题链接 LeetCode 17. 电话号码的字母组合 中等 2. 题目要…