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

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

一.字符串的定义方式

第一种：

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;}}
}