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

数据结构----结构--线性结构--字符串

数据结构----结构–线性结构–字符串

一.字符串的定义方式

第一种:

char* str1="Hello"

第二种:

char  str2[]="Hello";

区别

1.所在区域不同

//str1在常量区//str2在这里的写法是在栈区

2.元素是否可改

//str1中的元素不可改//str2中的元素可改//第一种
//用下标进行修改//第二种
//用strcpy函数进行修改

3.str1和str2是否可改

//str1可改,它是指针可以改变指向
str1="Haha";//str2不可改,它是地址不可改

4.大小不同

sizeof(str1);//4个字节sizeof(str2);//6个字节

二.关于字符串替换的问题

题目:

将一个足够长的字符串的空格替换成win,原字符串为 "only lovers left alive "(此字符串是无限长的 'e’字符后面有无限的空间)

方法:

1.暴力 申请一块新空间大小为 strlen(字符串)+额外要用的空间

​ 对原字符串进行遍历,遇到空格就在新空间存入win,不是的话就存入原字符

​ 时间复杂度 O(n) 空间复杂度 O(n)

2.字符串切割,拼接

​ 切割的函数为strtok

​ 连接的函数为strcat

​ 时间复杂度 O(n) 空间复杂度 O(n)

3.栈 时间复杂度 O(n) 空间复杂度 O(n)

4.队列 时间复杂度 O(n) 空间复杂度 O(n)

5.暴力(优化)

​ 1.在原有空间上定义两个指针

​ 2.一个指向最后一个字符的位置,另一个指向替换完空格后的地方(此位置为strlen(字符串)+额外要用的空间)

​ 3.两个指针同时向前移动,遇到空格,就在后面指针指向的位置替换成win(先替换n然后指针向前移动以此类推,直到替换完成),不是空格就把前面指针指向的位置的内容,替换到后面指针指向的位置,然后两个指针一起向前移动,直到前一个指针的下一个不是此字符串中的元素了。

​ 时间复杂度 O(n) 空间复杂度 O(1)

三.关于字符串单词倒置的问题

题目:

将一个字符串 “only lovers left alive"进行单词倒置 倒置后的字符串为"alive left lovers only”

方法:

1.数组

​ 定义两个指针,一个指向字符串从后往前第一个不为空格的字符,另一个最开始也是指向这里,然后向前遍历,当找到空格时,将这一段的字符全部都放到新的数组里,然后后面的指针来到第一个指针的位置,从此位置向前再次找到第一个不为空格的字符,之后另一个也指向这里,接着向前遍历,当找到空格时再将这一段的字符全部都放到新的数组里

​ 两个指针一直重复上面的过程,直到前面指针指向了字符串中的首元素,看两个指针是否指向统一元素,如果不是就将这一段的字符全部都放到新的数组里倒置完成,如果是的话倒置完成。

​ 时间复杂度 O(n) 空间复杂度 O(n)

2.倒置

​ 先将整个字符串进行倒置,然后将每个单词进行倒置

​ 时间复杂度 O(n) 空间复杂度 O(1)

3.链表

​ 将每一个单词都用一个链表存,然后将链表从前到后采用头插法,变成一个新链表即可

​ 时间复杂度 O(n) 空间复杂度 O(n)

4.栈

​ (1)一个栈+数组

​ 将字符串入栈,如果遇到空格,就将栈内元素出栈放到数组中(数组提前申请好空间)

​ 如果字符串为空了就将栈内元素出栈放到数组中

​ 时间复杂度 O(n) 空间复杂度 O(n)

​ (2)两个栈

​ 将字符串全部入到第一个栈中,然后将第一个栈中元素弹出,入到第二个栈中,

​ 如果遇到空格,就将第二个栈中的元素,替换到原字符串的相应位置上(这里会有一个指针来进行字符的替换,每替换完一个,指针就向后移动一位,指针最开始指向字符串的首元素),然后进行将第一个栈中的元素弹出

​ 直到第一个栈中没有元素了,如果第二个栈中有元素就将第二个栈中元素全部弹出,替换原字符串中的相应位置上

​ 时间复杂度 O(n) 空间复杂度 O(n)

5.字符串切割,拼接

升级版于字符串单词倒置问题(此题的网址为https://leetcode.cn/problems/reverse-words-in-a-string/)

题目:

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意:**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

运用到上面分析的倒置的方法代码如下:

//这里的代码是c++语言下的
class Solution {
public:string reverseWords(string s) {//删除首尾的空格s.erase(0, s.find_first_not_of(" "));s.erase(s.find_last_not_of(" ")+1);//整体进行翻转int begin1 = 0;int end1 = s.size() - 1;while (begin1 < end1) {char a = s[begin1];s[begin1] = s[end1];s[end1] = a;begin1++;end1--;}//每个单词进行翻转int begin = 0;int end = 0;char* p = &s[0];int index = 0;int bool1 = 1;int bool2 = 1;int bool3 = 0;int bool4 = 0;int bool5 = 0;while (*p != '\0') {if (*p != ' ' && *(p + 1) != ' '&&bool1%2==1) {begin = index;bool1++;bool3 = 1;}if ((*p == ' ' && *(p - 1) != ' ' && bool1 % 2 == 0)) {end = index - 1;bool1++;bool4 = 1;}if (*(p + 1) == '\0' && *p !=' ' && bool1 % 2 == 0) {end = index;bool1++;bool4 = 1;}int begin2 = begin;int end2 = end;while (begin2 < end2&& bool3&& bool4) {bool5 = 1;char a = s[begin2];s[begin2] = s[end2];s[end2] = a;begin2++;end2--;}if (bool5) {bool3 = 0;bool4 = 0;bool5 = 0;}p++;index++;}//去除字符串间的空格string::iterator ite = s.begin();while (ite!=s.end()) {if (*ite == ' ' && *(ite + 1) == ' ') {ite=s.erase(ite);}else if (*ite == ' ' && *(ite - 1) == ' ') {ite = s.erase(ite);}else {ite++;}}return s;}
};

四.关于字符串的一道题

题目:

​ 一个字符串”abcdefgh“ ,输入一个k,将前k个字符移到字符串的后面,且移动的k个字符顺序不变,当k等于3时,移动后的字符串为”defghabc“

方法:

​ 1.队列/栈

​ 2.链表/数组

​ 3.字符串切割,拼接

​ 4.倒置

​ 先将整个字符串进行倒置,然后将0 ~ 第k-1字符包括它们之间的字符进行倒置,将 k ~ 最后一个字符包括它们之间的进行倒置

​ 时间复杂度 O(n) 空间复杂度 O(1)

五.关于字符串查找的问题

1.根据经验总结出下面四大查找问题

1.在一个串中找符合某个条件的字符

2.在一个串中找符合条件的某个串/某些串

3.在多个串中找某个串/某些串

4.在两个串中找符合条件的某些公共串

1.第一大查找问题中的题

题目:

找到第一个只出现一次的字符

解决:

1.队列+计数器

2.map+遍历

3.hash+遍历

2.第二大查找问题中的题

题目:

找到字符串中最长回文子串

解决:

1.判断一个字符串是否是回文子串,从中间断开,然后翻转后面的字符串,然后两个字符串进行对比,看是否相等即可

2.然后再比较长度即可

3.第二大查找问题中的KMP算法

1.KMP算法的作用

KMP算法是用来找一个串(字串)在另一个串(主串)中出现的位置(首元素的位置)

2.KMP的实现
1.首先定义一个Next数组用来存字串中每个元素前面串的前缀字串和后缀字串相同最大的长度

1.定义两个相邻变量作为下标

2.如果后面那个下标所在的元素和前一个下标在next数组中充当下标所找到的元素相同,则此元素所在下标的nexrt数组的值就是前一个元素下标在next数组中所找到元素的值+1

3.如果不相同且前一个元素下标在标在next数组中所找到元素的值为0,那么此元素所在下标的nexrt数组的值为0

4.如果不相同且前一个元素下标在标在next数组中所找到元素的值不为0,那前一个变量就变为它所在下标在next数组中充当下标所找到的值-1,然后重复操作2,直到找到,或者找到子串的头节点还没找到结束

2.子串与主串进行匹配

1.如果子串元素与主串元素相同,继续往下比

2.如果子串元素与主串元素不相同,那子串中的元素就变为当前元素下标前面那个的元素下标的Next数组的所指的子串元素,如果到了子串的头元素也不相等,那匹配串重头开始

3.直到子串遍历完了或者主串遍历完了,结束

3.KMP代码的如下
//此代码是使用c写的
#include<stdio.h>
#include<stdlib.h>int* GetNext(const char* match) {int* pNext = (int*)malloc(sizeof(int) * strlen(match));pNext[0] = 0;int i = 1;int j = i - 1;while (i < strlen(match)) {if (match[i] == match[pNext[j]]) {pNext[i] = pNext[j] + 1;i++;j = i - 1;}else if (pNext[j] == 0) {pNext[i] = 0;i++;j = i - 1;}else {j = pNext[j] - 1;}}return pNext;
} int KMP(const char* src, const char* match) {if (src == NULL || match == NULL) return -1;//获得Next数组int* pNext = GetNext(match);//匹配int i = 0;int j = 0;while (i < strlen(match) && j < strlen(src)) {if (src[i] == match[j]) {i++;j++;}else {//匹配串跳转if (j == 0) {i++;}else {j = pNext[j - 1];}}}if (j == strlen(match)){return i - j;}else {return -1;}
}int main() {printf("%d\n", KMP("abcabcgweu3abcabcdusabcabcsfh", "abcabc"));//测试样例return 0;
}

4.第二大查找问题中的Sunday算法

1.Sunday算法的作用

KMP算法是用来找一个串(字串)在另一个串(主串)中出现的位置(首元素的位置)

2.Sunday的实现
1.首先申请一个256个空间大小的inr型的数组Next(因为字符一共有256个,所以可以定义一个有限长度的数组)

1.申请完数组后将数组中的元素全部赋值为-1

2.遍历一遍子串,给数组中的元素进行赋值,存的是子串中每个元素在子串中从右往左第一次出现的下标

2.子串与主串进行匹配

1.定义两个变量用来遍历主串和子串,还有一个标记变量用来找每回主串与子串匹配来时的那个下标

2.主串与子串进行匹配,如果相同,那么继续下一个,如果不相同,那子串从头开始,主串则是从k所在下标加上子串长度然后减去当前所获得的字符在Next数组中充当下标的值开始

3.直到子串遍历完了或者主串遍历完了,结束

3.Sunday代码的如下
//此代码是使用c++写的
#include <iostream>
#include <string>
using namespace std;int Next[256];//申请一个Next数组,用来存匹配串中各个元素的下标void funzhi(string a) {//初始化Next数组for (int i = 0; i < a.size(); i++) {Next[a[i]] = i;}
}
int peidui(string zhu, string pi) {//进行配对int i = 0;//主串int j = 0;//匹配串int length = pi.size();//匹配串长度int k = 0;//用来标记匹配串在主串中首元素的下标while (1) {if (zhu[i] != pi[j]) {//如果主串元素与匹配串元素不相同if (k + length >= zhu.size()) {//如果超出了主串的范围return -1;}k = k + length - Next[zhu[k + length]];i = k;j = 0;}else {//如果主串元素与匹配串元素相同i++;j++;}if (j >= pi.size()) {//如果子串遍历完了return k;}}
}

相关文章:

数据结构----结构--线性结构--字符串

数据结构----结构–线性结构–字符串 一.字符串的定义方式 第一种&#xff1a; char* str1"Hello"第二种&#xff1a; char str2[]"Hello";区别 1.所在区域不同 //str1在常量区//str2在这里的写法是在栈区2.元素是否可改 //str1中的元素不可改//st…...

数据工厂-生成接口通用用例

章节目录&#xff1a; 一、背景介绍二、前置准备三、设计思路四、代码具体实现五、执行效果六、其他说明七、结束语 一、背景介绍 有哪些用例是可以通用且固定的&#xff1f; 针对之前提到的接口用例设计思路&#xff0c;拆分为三个切入点&#xff1a; 举个例子&#xff1a; {…...

N 字形变换

N 字形变换 题目: 将一个给定字符串 s 根据给定的行数 numRows &#xff0c;以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时&#xff0c;排列如下&#xff1a;P A H N A P L S I I G Y I R 之后&#xff0c;你的输…...

STM32+RTThread配置以太网无法ping通,无法获取动态ip的问题

记录一个非常蠢的问题&#xff0c;今天在移植rtthread的以太网驱动的时候出现无法获取动态ip的问题&#xff0c;问题如下&#xff1a; 设置为动态ip时不管是连接路由器还是电脑主机都无法ping通&#xff0c;也无法获取dns地址。 设置为静态ip时无法ping通主机。 使用wireshark…...

python编写MQTT订阅程序

Download | Eclipse Mosquitto 1、下载&#xff1a; https://mosquitto.org/files/binary/win64/mosquitto-2.0.17-install-windows-x64.exe 2、安装&#xff1a; 3、conf配置 1)使用notepad打开“C:\Program Files\mosquitto\mosquitto.conf”另存为c:\myapp\msquitto\mo…...

mysql 中 cast 函数用法

在 MySQL 中&#xff0c;CAST() 函数用于将一个表达式转换为指定的数据类型。它可以用于多种场景&#xff0c;例如将字符串转换为数字&#xff0c;或者将日期时间转换为特定格式。 以下是 CAST() 函数的基本语法&#xff1a; CAST(expression AS datatype) 其中&#xff0c…...

MongoDB 的简介

MongoDB 趋势 对于 MongoDB 的认识 Q&A QA什么是 MongoDB&#xff1f; 一个以 JSON 为数据模型的文档数据库一个以 JSON 为数据模型的文档数据库文档来自于“JSON Document”&#xff0c;并非我们一般理解的 PDF&#xff0c;WORD谁开发 MongDB&#xff1f; 上市公司 MongoD…...

是否在业务中使用大语言模型?

ChatGPT取得了巨大的成功&#xff0c;在短短一个月内就获得了1亿用户&#xff0c;并激发了企业和专业人士对如何在他们的组织中利用这一工具的兴趣和好奇心。 但LLM究竟是什么&#xff0c;它们如何使你的企业受益?它只是一种炒作&#xff0c;还是会长期存在? 在这篇文章中我…...

37. 交换字符(第三期模拟笔试)

题目&#xff1a; 给定一个01串&#xff08;仅由字符0和字符1构成的字符串&#xff09;。每次操作可以交换两个相邻的字符。 例如&#xff1a;对于字符串"001110"来说&#xff0c; 可以交换第二个字符0和第三个字符1&#xff0c;交换之后的字符串变成了"0101…...

git 查看当前分支最近一次提交的commit SHA

获取当前分支最近一次commit SHA &#xff08;长度为40个16进制数字的字符&#xff09;命令如下&#xff1a; git rev-parse HEAD 获取简写&#xff08;短&#xff09; commit SHA git rev-parse --short HEAD...

LuatOS 开发指南

NDK 开发 官方教程 官方例程 API 下载软件 下载官方NDK例程压缩包到本地&#xff0c;并解压。可以看到目录如下&#xff1a; doc: 文档教程 env: 编译环境 example: NDK示例 platform: 需要编译的平台&#xff08;air72x/air8xx&#xff09; tools: 其他辅助软件 VSCode 使…...

maven推包The environment variable JAVA_HOME is not correctly set

解决办法&#xff1a; 打开idea查看jdk安装位置 1.在/etc下面创建&#xff08;如果存在就是更新&#xff09;launchd.conf。里面添加一行&#xff1a; setenv JAVA_HOME /Library/Java/JavaVirtualMachines/jdk1.8.0_351.jdk/Contents/Home #JAVA_HOME后面是我的java安装路径…...

Python VScode 配置

在上一章节中我们已经安装了 Python 的环境&#xff0c;本章节我们将介绍 Python VScode 的配置。 准备工作&#xff1a; 安装 VS Code安装 VS Code Python 扩展安装 Python 3 安装 VS Code VSCode&#xff08;全称&#xff1a;Visual Studio Code&#xff09;是一款由微软…...

【vue2第九章】组件化开发和根组件以及style上的scoped作用

组件化开发和根组件 什么是组件化开发&#xff1f; 一个页面可以拆分为多个组件&#xff0c;每个组件有自己的样式&#xff0c;结构&#xff0c;行为&#xff0c;组件化开发的好处就是&#xff0c;便于维护&#xff0c;利于重复利用&#xff0c;提升开发的效率。 便于维护&…...

从零开始的Hadoop学习(五)| HDFS概述、shell操作、API操作

1. HDFS 概述 1.1 HDFS 产出背景及定义 1&#xff09;HDFS 产生背景 随着数据量越来越大&#xff0c;在一个操作系统存不下所有的数据&#xff0c;那么就分配到更多的操作系统管理的磁盘中&#xff0c;但是不方便管理和维护&#xff0c;迫切 需要一种系统来管理多台机器上的…...

【spark】序列化和反序列化,transient关键字的使用

序列化 Spark是基于JVM运行的进行&#xff0c;其序列化必然遵守Java的序列化规则。 序列化就是指将一个对象转化为二进制的byte流&#xff08;注意&#xff0c;不是bit流&#xff09;&#xff0c;然后以文件的方式进行保存或通过网络传输&#xff0c;等待被反序列化读取出来。…...

2.4 Vector<T> 动态数组(随机访问迭代器)

C自学精简教程 目录(必读) 该 Vector 版本特点 这里的版本主要是使用模板实现、支持随机访问迭代器&#xff0c;支持std::sort等所有STL算法。(本文对随机迭代器的支持参考了 复旦大学 大一公共基础课C语言的一次作业) 随机访问迭代器的实现主要是继承std::iterator<std:…...

Ubuntu下运行QEMU模拟riscv64跑Debian

1.安装QEMU 下载地址&#xff1a; https://www.qemu.org/download/ 建议选择稳定版本&#xff0c;下载后解压&#xff0c;然后make wget https://download.qemu.org/qemu-8.0.3.tar.xz tar xjvf qemu-8.0.3.tar.xz cd qemu-8.0.3 ./configure --enable-kvm --enable-virtfs …...

移动基站ip的工作原理

原理介绍 Basic Principle 先说一下概念&#xff0c;大家在不使用 WIFI 网络的时候&#xff0c;使用手机通过运营商提供的网络进行上网的时候&#xff0c;目前都是在用户端使用私有IP&#xff0c;然后对外做 NAT 转换&#xff0c;这样的情况就导致大家统一使用一些 IP 段进行访…...

Kubernetes技术--使用kubeadm搭建高可用的K8s集群(贴近实际环境)

1.高可用k8s集群架构(多master) 2.安装硬件要求 一台或多台机器,操作系统 CentOS7.x-86_x64 硬件配置:2GB或更多RAM,2个CPU或更多CPU,硬盘30GB或更多 注: 这里属于教学环境,所以使用三台虚拟机模拟实现。 3.部署规划 4.部署前准备 (1).关闭防火墙 systemctl stop fi…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...