算法力扣刷题

您所在的位置：网站首页 › 刷题方法和心得 › 算法力扣刷题

算法力扣刷题

2024-07-10 07:11| 来源: 网络整理| 查看: 265

前言

字符串章节部分跟随学习结束，作出总结。

一、题目及方法总结

（1）反转字符串：双指针法。

反转全部字符串，i在开头，j在结尾；判断条件i < j ;每隔2k反转前k个字符，i++改成i += 2k；调用反转函数，给出start，end，左闭右开可以。

（2）替换数字：逆向操作数组。先扩容，再修改，i指向size-1开始，k指向扩容的末尾：

如果遇到数字字符，number也倒着填充k- -。这里填充需要覆盖，但是不会影响没操作的字符。

（3）翻转字符串中的单词：

先删除多余空格：双指针法。fast和slow都从0出发，如果s[fast] == ’ '时，slow不动；不等于空格时，s[slow] = s[fast]，slow++，这一步是while不是if。额外处理单词之间的一个空格，if(slow != 0)。整体反转；单个单词反转。

（4）右旋字符串

整体反转，再分两段反转

（5）匹配字符串

KMP算法，构造next前缀表。初始化——不相等时，j = next[j-1]；相等时j++。j指向前缀结束的后一位。i指向后缀末尾。遇到不相同元素，查看next[j-1]后，j = next[j-1]，while。再if(s[j] == s[i])，满足j++。if(j == 模式串size)，return。

（6）重复子字符串

利用前缀表含义：前缀=后缀，并且长度最长。

总结：完成字符串题目和思路回顾。

二、 C++中string类

参考链接：cplusplus.com/reference/string/string/ 记录常用用法：

定义

（1）#include < string > 依然是一个类，使用string就是创建对象调用函数实现功能。（2）“字符串”：字符序列，偶尔可以看作和数组相通，数组中类型是char。

typedef basic_string string; //basic_string是类模板，把类型定义成char，就是string （1）构造函数

很多种方法可以构造string，所以对应的函数原型有很多：

(1) string();//默认构造函数：size=0；还没有放字符。 (2) string (const string& str); //拷贝构造函数：得到和参数一样的字符串 (3) string (const string& str, size_t pos, size_t len = npos);//复制参数的str，从pos开始（包括pos），长度可以指定，默认到字符串末尾。 (4) string (const char* s);//把C风格的字符串转换成string，C风格的'\0'结尾不转换。 (5) string (const char* s, size_t n);//指定前n个字符，肯定包含空格。 (6) string (size_t n, char c);//指定长度，用字符c初始化 (7) template string (InputIterator first, InputIterator last);//[first，last)，迭代器类型指定范围。（8）初始化列表作为参数；（2）重载=运算符

和（1）构造同理，也用来定义string。“=”后面三种类型：string、char*、char

(1) string& operator= (const string& str); (2) string& operator= (const char* s); (3) string& operator= (char c); （3）iterator

可以用iterator只做指向，不去修改。（前两个就可以直接用）。

begin();——end();//正向，如果修改了常量string，也会报错。 rbegin();——rend();//逆向 cbegin();——cend();//不能修改const。 crbegin();——crend();//不能修改const。（4）大小 size();//和length();一样。 max_size();//string类的最大范围 capacity();//当前给string分了多少 void resize(size_t n);//改变长度到n，如果n小于原有size，超出部分删掉；如果n比原有size大，用空字符扩展 void resize(size_t n，char c);//如果n比原有size大，用指定的c初始化扩展的字符。 clear();//清空 empty();//判断是否为空（5）访问元素

直接用下标最方便

char& oprator[](size_t pos);//通过下标访问，返回是字符的引用，所以对原字符操作。 char& at (size_t pos);//比如：str.at(4)；返回是字符的引用，所以对原字符操作。 char& back();//返回string的最后一个字符引用 char& front();//返回string的第一个字符引用（6）修改字符串

末尾增加string：前两个可以追加多个字符；push_back只能增加一个字符。

string& operator+=();//末尾追加。参数类型可以是string、char*、char string& append();//函数原型众多，类似构造函数的（2）~（7），参数类型等同于构造函数的（2）~（7） void push_back (char c);//只能增加一个字符。

覆盖原有string，替换新值，全部覆盖换新。assign和append一样，参数类似构造函数（2）~‘（7）

string& assign();

指定位置插入字符：第一个参数得指定位置，在这个位置之前插入不定数量的字符/字符串。剩余参数还是和构造函数（2）~（7）一个性质。

string& insert (size_t pos, const string& str); string& insert (size_t pos, const string& str, size_t subpos, size_t sublen); string& insert (size_t pos, const char* s); string& insert (size_t pos, const char* s, size_t n); string& insert (size_t pos, size_t n, char c); iterator insert (const_iterator p, char c); template iterator insert (iterator p, InputIterator first, InputIterator last); string& insert (const_iterator p, initializer_list il);

删除：erase时间复杂度O(n)。三种方式。

erase: string& erase (size_t pos = 0, size_t len = npos);//给位置和长度，这个位置后面的所有都删掉 iterator erase (const_iterator p);//给一个iterator，删掉p指定的字符 iterator erase (const_iterator first, const_iterator last);//给一个范围，iterator类型的范围 viod pop_back();//删掉最后一个，但是没有返回值。

替换replace：指定长度和范围，以及用什么替换，在原有的基础上覆盖。长度和范围可以是pos和len结合，也可以是iterator类型，左闭右开；用什么替换，对象类型类似构造函数（2）~（7）。

交换两个str类型的内容：

void swap (string& str); （7）字符串操作（建立string对象和C-字符串的关系）

通过构造函数可以把C-字符串作为参数传递给string对象，相当于把C-字符串转换成string类型；那么也可以把string类型转换成C-字符串：

const char* c_str();//str.c_str();没有参数，string对象直接调用；返回一个字符数组，C-字符串。 const char* data();//和c_str函数作用一样，返回一个C数组。相当于转换成C-字符串。

从string复制字符序列：用char* 数组存放。但是要手动添加’\0’。

size_t copy (char* s, size_t len, size_t pos = 0) const; 解释：参数：第一个是字符复制后存放的数组，第二个指定长度，第三个指定开始位置（包括pos）。注意：和（6）指定位置和长度参数前后相反：（6）中基本上是位置在前，长度在后；copy是len在第二个，pos在第三个。返回值：复制给s数组的字符数量。

find：类似strchr和strstr函数的功能。（rfind）

//以下返回值都是：size_t，如果找到，就返回第一个匹配字符的位置（下标）；没找到，返回npos=-1。 //和strchr和strstr返回类似，如果找到，返回char* 指向首个字符；没找到char* 指向NULL。 size_t find (const string& str, size_t pos = 0) const noexcept; //在str中找另一个str参数，默认位置从0开始，可以自己指定pos，那么从包含pos之后开始找。str1.find(str2,0); size_t find (const char* s, size_t pos = 0) const; //参数可以给string对象，也可以给char* 数组。 size_t find (const char* s, size_t pos, size_type n) const; //多了一个n，指定匹配多长的字符 size_t find (char c, size_t pos = 0) const noexcept; //等同与strchr功能，找一个字符。 rfind函数：参数和find一样，同样有4个函数原型；但是的逆向找。类似strrchr函数功能。

总结：前三个可以用来找字符串，多个字符，必须全字匹配，单个匹配不行，等同strstr函数功能；最后一个用来找单个字符，等同strchr函数功能。

那么不需要全字匹配的话：使用find_first_of，参数和find相同，区别：找到参数包含字符的其中一个就可以，无需全字匹配，等同于strpbrk函数。自然和rfind对应的有：find_last_of。

再进一步：找不匹配的第一个字符，没有在参数中指定。正向：find_first_not_of，等同于strspn函数；倒向：find_last_not_of。

生成子字符串：substr。类似strtok函数。

string substr (size_t pos = 0, size_t len = npos) const; 传递参数：指定位置和长度。返回一个string对象。对比strtok函数： char* strtok_s(char* s;const char *_Delimiter, char **_Context);

比较字符串：类似strcmp函数。返回值：（1）等于0，代表相等；（2）大于0，代表大于：ASCII码更大或者长度更长；（3）小于0，调用者小于参数。ASCII码更小或者长度更短；

int compare (const string& str) const noexcept; //传递string，可以。 int compare (size_t pos, size_t len, const string& str) const; //先对调用者指定位置和长度，和string比较。 int compare (const char* s) const; //传递char*类型，可以。融合C-字符串 int compare (size_t pos, size_t len, const char* s, size_t n) const; //对调用者指定位置和长度，再对char指定比较长度。（8）非成员函数的功能重载，针对string类型

重载+，起到连接的作用。

string operator+ (const string& lhs, const string& rhs); //+两端是string类型 string operator+ (const string& lhs, const char* rhs); //+一端是string类型，一端是C-字符串 string operator+ (const string& lhs, char rhs); //+一端是string类型，一端是字符char。

关系运算符：==、!=、=、。还是调用compare函数，但是直接用运算符更方便。

可以调用swap，传递一个参数交换string内容；也可以用swap传递两个string参数交换：

void swap (string& x, string& y);

重载运算符：>>、str; cout

【本文地址】

算法力扣刷题

算法力扣刷题

今日新闻

推荐新闻