文章目录
【写在前面】
到这里我们就要学会能自己能看文档了，因为就这个 string 类来说就有一百多个接口函数，那肯定记不住呀，我们平时用的大概就二十个，一般我们都是学习它比较常用的，其它的大概熟悉它们有哪些功能，真要用到时再去查文档。可以看到其实 string 就是一个管理字符数组的顺序表，因为字符数组的使用广泛，C++ 就专门给了一个 string 类，由于编码原因，它写的是一个模板。针对 string，一般情况它有三个成员 —— char* _str、size_t _size、size_t _capacity，我们在下面模拟实现 string 时就会看到，其次在学习深浅拷贝时我们只用 char* _str。
C++ 的文档库严格来说有两个：注意前者并不是 C++ 的官网文档，后者才是。这里我们对于官方文档就作为参考，因为它比较乱，平时就用 cplusplus 也够了。
此外对于类和对象还有一个深浅拷贝的知识我们将会再这里补充。
一、为什么学习string类
💦 C语言中的字符串
C 语言中，字符串是以 ‘\0’ 结尾的一些字符的集合，为了操作方便，C 标准库中提供了一些 str 系列的库函数，
但是这些库函数与字符串是分离开的，不太符合 OOP 的思想，而且底层空间需要用户自己管理，稍不留神可
能还会越界访问。
💦 两个面试题(暂不讲解)
在 OJ 中，有关字符串的题目基本以 string 类的形式出现，而且在常规工作中，为了简单、方便、快捷，基本都使用 string 类，很少有人去使用 C 库中的字符串操作函数。
二、标准库中的string类
💦 string类(了解)
- 字符串是表示字符序列的类。
- 标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作单字节字符字符串的设计特性。
- string 类是使用 char(即作为它的字符类型，使用它的默认 char_traits 和分配器类型 (关于模板的更多信息，请参阅 basic_string)。
- string 类是 basic_string 模板类的一个实例，它使用 char 来实例化 basic_string 模板类，并用 char_traits 和 allocator 作为 basic_string 的默认参数(根于更多的模板信息请参考 basic_string)。
- 注意，这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如 UTF-8) 的序列，这个类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作。
总结：
- string 是表示字符串的字符串类。
- 该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作 string 的常规操作。
- string 在底层实际是：basic_string 模板类的别名，typedef basic_string<char, char_traits, allocator> string;。
- 不能操作多字节或者变长字符的序列。
- 在使用 string 类时，必须包含 string 头文件以及 using namespace std;。
#include<string> #include<iostream> using namespace std; int main() { cout << sizeof(char) << endl; cout << sizeof(wchar_t) << endl; char arr1[] = "hello bit"; char arr2[] = "比特"; return 0; }
📝说明
对于字符，C++ 里提出了两个类型，现阶段接触的是第一个。
可以看到结果一个是 1 和 2，这个东西与编码有关系。
编码 ❓
计算机中存储只有二进制 0 和 1，如何去表示文字呢 ？？？
这时就建立出对应的编码表：
- ASCII > 支持英文
1Byte = 8Bit，0 - 255 ASCII 编码表就是对 256 个值建立一个对应的表示值
- GBK > 我国制定的，常用于 windows 下
早期 windows 为了打入中国市场，就使用这个编码 - utf-8 > 通用，兼容 ASCII，常用于 Linux 下
世界各国都开始使用计算机了，而早期计算机中只能表示英文，不能表示其它国家的文字，所以需要建立自己的编码表，但各自搞各自的就非常乱，所以就出现了 utf-8，早期是 UniCode
所以据不完全统计汉字大约有十万个左右，所以我们这里用 2 个字节，大概表示 6 万种状态
💦 string类的常用接口说明(只讲最常用的)
1、string类对象的常见构造
| (constructor) 函数名称 | 功能说明 |
| string() —— 重点 | 构造空的 string 类对象，即空字符串 |
| string(const char* s) —— 重点 | 用 C-string 来构造 string 类对象 |
| string(size_t n, char c) | string 类对象中包含 n 个字符 c |
| string(const string& s) —— 重点 | 拷贝构造函数 |
#include<string> #include<iostream> using namespace std; //大概原理 template<class T> class basic_string { T* _arr; int _size; int _capacity; }; //typedef basic_string<char> string; int main() { string s1; string s2("hello"); string s3("比特"); string s4(10, 'a'); string s5(s2); //对于string它重载了流提取和流插入等，这里就可以直接用 cout << s1 << endl; cout << s2 << endl; cout << s3 << endl; cout << s4 << endl; cout << s5 << endl; //赋值 ———— 深拷贝 s1 = s5; cout << s1 << endl; }
📝说明
basic_string ❗
string s1; || string s2(“hello”); ❗
通过调试我们发现 s1 虽然是无参的，但并不是啥都没有，且会在第一个位置放一个 \0。
2、string类对象的容量操作
| 函数名称 | 功能说明 |
| size —— 重点 | 返回字符串有效字符长度 |
| length | 返回字符串有效字符长度 |
| capacity | 返回空间总大小 |
| empty —— 重点 | 检测字符串释放为空串，是返回 true，否则返回 false |
| clear —— 重点 | 清空有效字符 |
| reserve —— 重点 | 为字符串预留空间 |
| resize —— 重点 | 将有效字符的个数改成 n 个，多出的空间用字符 c 填充 |
 |
#include<string> #include<iostream> using namespace std; void test_string1() { //1、size | length string s1("hello world"); cout << s1.size() << endl; cout << s1.length() << endl; cout << "----------cut----------" << endl; //2、max_size string s2; cout << s1.max_size() << endl; cout << s2.max_size() << endl; cout << "----------cut----------" << endl; //3、capacity cout << s1.capacity() << endl; cout << "----------cut----------" << endl; //4、resize string s3("hello world"); cout << s3.size() << endl; cout << s3 << endl; //s3.resize(20);//n大于当前的字符串的长度且没有指定c，所以hello world\0\0\0\0... //s3.resize(5);//n小于当前的字符串的长度， 它会删除掉从n开始的这些字符 s3.resize(20, 'x');//n大于当前的字符串的长度且指定c，所以hello worldxxxx... cout << s3.size() << endl; cout << s3 << endl; cout << "----------cut----------" << endl; //5、reserve string s4("hello world"); s4.reserve(20); cout << s4 << endl; cout << s4.size() << endl; cout << s4.capacity() << endl; s4.reserve(10); cout << s4 << endl; cout << s4.size() << endl; cout << s4.capacity() << endl; cout << "----------cut----------" << endl; //6、clear | empty string s5("hello world"); cout << s5 << endl; cout << s5.empty() << endl;; s5.clear(); cout << s5 << endl; cout << s5.empty() << endl; cout << "----------cut----------" << endl; //7、shrink_to_fit 暂且不演示 } void test_string2() { string s; size_t sz = s.capacity(); cout << "making s grow:\n" << sz << endl; for(int i = 0; i < 500; ++i) { s.push_back('c'); if(sz != s.capacity()) { sz = s.capacity(); cout << "capacity changed:" << sz << '\n'; } } cout << "----------cut----------" << endl; } int main() { test_string1(); test_string2(); return 0; }
📝说明
size || length ❗
两者的功能相同，一般我们比较常用的是 size。
对于 string 是在 STL 这个规范前被设计出来的，因此在 Containers 下并没有 string：
早期说要算字符串字符的长度，所以早期提供的接口就叫 length，至于后面要加 size 的原因是后面增加了 map、set 这样的树，所以用 length 去表示它的数据个数就不合适了。
max_size ❗
它也是早期设计比较早的，属于一个没用的接口 —— 从操作系统中获取最大的长度。本意是想告诉你这个字符串最大你能定义多长， 这个接口在设计的时候其实不好实现，它没有办法标准的去定义这个接口，因为它有很多不确定的因素。所以它这个地方是直接给你 232 ，也就是 4G。所以没什么价值，以后再遇到就直接跳过了。
capacity ❗
对于 string 对象而言，如果 capacity 是 15，意味着它有 16 个字节的空间，因为有一个位置是 \0 的。对于 capacity 它会随着字符串的大小而增容，这里默认是 15。
resize ❗
resize 的前者版本可以让字符串的长度变成 n；后者可以让字符串的 n 个长度变成 c。
如果 n 是小于当前的字符串的长度， 它就会缩减到 n 个字符，删除掉从 n 开始的这些字符。
如果 n 是大于当前的字符串的长度，通过在末尾插入尽可能多的内容来扩展当前内容，倘若指定了 c，则新元素被初始化为 c 的副本，否则它们就是值初始化字符 (空字符 \0)。
对于 s3.resize(20); s3[19] 是有效位置，因为对于 operator[] 里它会 assert(pos < _size)。
reserve ❗
请求 capacity。
注意这里不是你要多少 capacity 它就给多少 capacity，它在增容时还要对照不同编译器下自己的增容规则，最终容量不一定等于字符串长度，它可能是相等的，也可能是更大的。
如果 n 大于当前字符串的 capacity，那么它会去扩容。
如果 n 小于当前字符串的 capacity，这里跟不同的平台有关系。文档里是这样说的：其他情况下 (小于或等于)，有可能它会缩容(开一块新空间，将数据拷贝，释放原有空间)，也有可能不对当前空间进行影响，只是变换 capacity 的值。已证，VS 和 Linux 下不会缩容，STL 的标准也是这样规定的，这是实现 STL 的人决定的。
对于 s4.reserve(20); s4[19] 是无效位置，因为对于 operator[] 里它会 assert(pos < _size)。
string 增容是怎么增的 ❓
test_string2()：
可以看到 Windows VS 下初始容量是 15 ，除了第一次，其余的大概是以 1.5 倍增容。
g++ ？？？
可以看到在不同的编译器下增容规则也不同，Linux g++ 下初始容量是 0，其余是以 2 倍增容的。
clear | empty ❗
清理字符串 | 判空字符串
resize 和 reserve 有什么价值 ❓
对于 resize，既要开空间，还要对这些空间初始化，就可以用 resize —— s.resize(20, ‘x’);
对于 reserve，明确知道需要多大空间的情况，可以提前把空间开好，以减少增容所带来的代价 —— s.reserve(500);
3、string类对象的访问及遍历操作
| 函数名称 | 功能说明 |
| operator[] —— 重点 | 返回 pos 位置的字符，const string 类对象调用 |
| begin + end | begin 获取一个字符的迭代器，end 获取最后一个字符下一个位置的迭代器 |
| rbegin + rend | begin 获取一个字符的迭代器，end 获取最后一个字符下一个位置的迭代器 |
| 范围 for | C++11 支持更简洁的范围 for 的新遍历方式 |
 |
#include<assert.h> #include<string> #include<iostream> using namespace std; //大概原理 template<class T> class basic_string { public: char& operator[](size_t pos) { assert(pos < _size);//检查越界：s2[20] -> err return _arr[pos]; } private: T* _arr; int _size; int _capacity; }; //typedef basic_string<char> string; int main() { //逐一遍历字符串 //1、operator[] string s1("hello world"); for(size_t i = 0; i < s1.size(); ++i) { s1[i] += 1;//写 } for(size_t i = 0; i < s1.size(); ++i) { cout << s1[i] << " ";//读 } cout << endl; //2、范围for string s2("hello world"); for(auto& e : s2) { e += 1;//写 } for(auto e : s2) { cout << e << " ";//读 } cout << endl; //3、迭代器 string s3("hello world"); string::iterator it = s3.begin(); while(it != s3.end()) { *it += 1;//写 ++it; } it = s3.begin(); while(it != s3.end()) { cout << *it << " ";//读 ++it; } cout << endl; return 0; }
📝说明
operator [] | at ❗
operator[] 和 at 的价值是一样的，但是不一样的地方是对于越界：operator[] 直接使用断言报错，比较粗暴；而 at 则会抛异常。
范围 for ❗
这是 C++11 中提出的新语法，比较抽象，对于它的原理，后面会再模拟实现它。
注意 auto e : s3 只能读，不能写；auto& e : s3 可读可写。
迭代器 ❗
它是 STL 中六大组件中的核心组件，这里先见个面。
begin() 返回第一个有效数据位置的迭代器；
end() 返回最后一个有效数据的下一个位置的迭代器；
目前可以认为它类似于指针，—— 有可能是指针，有可能不是指针，因为不仅仅 string 有迭代器，其它容器里也有迭代器。
while(it != s3.end()) 也可以 while(it < s3.end())，但不建议。这里是数组，换成小于它依然没问题，但是如果是链表，小于就不行了。所以这里统一就用不等于。
迭代器的好处是可以用统一类似的方式去访问修改容器 (也就意味着会了 string 的迭代器就等于会了其它容器的迭代器)：
为什么这里要提供三种遍历方式 ❓
其实只提供了两种，因为范围 for 本质是迭代器，也就是说一个容器支持迭代器才会支持范围 for，后面会演示。
operator [] 可以像数组一样去访问，这种方式对于 vector 连续的数据结构是支持的，但是不支持 list。
迭代器这种方式是任何容器都支持的方式，所以迭代器才是容器通用的访问方式。
再简单了解迭代器 ❗
#include<string> #include<iostream> using namespace std; void Print1(const string& s)//不需要写 { string::iterator it = s.begin();//err,普通迭代器 //string::const_iterator it = s.begin();//ok,const迭代器 //string::const_iterator it = s.cbegin();//ok,C++11提供的cbegin while(it != s.end()) { cout << *it << " "; ++it; } cout << endl; } void Print2(const string& s) { string::reverse_iterator rit = s.rbegin();//err,普通反向迭代器 //string::const_reverse_iterator rit = s.rbegin();//ok,const反向迭代器 //auto rit = s.rbegin();//ok,auto的体现 while(rit != s.rend()) { cout << *rit << " "; ++rit;//注意这里不是-- } cout << endl; } void test_string() { string s1("hello"); Print1(s1); string s2("hello"); Print2(s2); } int main() { test_string(); return 0; }
📝说明
这里利用迭代器打印 s1：
查文档：begin 有两个版本
所以报错的原因是：s 是 const 对象，返回的是 const 迭代器，而这里使用普通迭代器来接收。解决方法就是用 const 迭代器接收。
在文档中看到 C++11 中又提供了一个 cbegin ？？？
为什么 C++11 把 const 迭代器单独拎出来，大概原因应该是 begin 里有普通 / const 迭代器不太明确，容易误导。不知道大家是怎么想的，我是觉得有点画蛇添足了。
rbegin：
rbegin 就是反向迭代器，顾名思义就是反向遍历。
auto 的价值 ❗
到了迭代器这里我们就可以用 auto 来替代比较长的类型，auto 的价值得以体现。
4、string类对象的修改操作
| 函数名称 | 功能说明 |
| push_back | 在字符串后尾插字符 c |
| append | 在字符串后追加一个字符串 |
| operator+= —— 重点 | 在字符串后追加字符串 str |
| c_str —— 重点 | 返回 c 格式字符串 |
| find + npos —— 重点 | 从字符串 pos 位置开始往后找字符 c，返回该字符在字符串中的位置 |
| rfind | 从字符串 pos 位置开始往前找字符 c，返回该字符在字符串中的位置 |
| substr | 在 str 中从 pos 位置开始，截取 n 个字符，然后将其返回 |
 |
#include<string> #include<iostream> using namespace std; void test_string1() { //1、push_back | append | operator += string s1("hello"); string s2("world"); s1.push_back('+'); s1.append("world"); cout << s1 << endl; s1 += '+'; s1 += "bit+"; s1 += s2; cout << s1 << endl; cout << "----------cut----------" << endl; //2、insert | erase string s3("hello"); s3.insert(0, "bit "); cout << s3 << endl; //s3.erase(5);//从5删到nops s3.erase(5, 2);//从5往后删2个 cout << s3 << endl; cout << "----------cut----------" << endl; } void test_string2() { //要求取出文件的后缀 string file1("test.txt"); string file2("test.c"); string file3("test.txt.zip");//对test.txt文件打了个包 size_t pos1 = file1.find('.'); if(pos1 != string::npos)//当find的返回值不等于npos就找到了 { //1、substr string sub1 = file1.substr(pos1);//同substr(pos1, file1.size()-pos1);,但没必要，因为这里是取后缀，而substr有缺省参数npos cout << sub1 << endl; } size_t pos2 = file2.find('.'); if(pos2 != string::npos) { string sub2 = file2.substr(pos2); cout << sub2 << endl; } //由此可见对于file3,以上代码不适用 size_t pos3 = file3.find('.'); if(pos3 != string::npos) { string sub3 = file3.substr(pos3); cout << sub3 << endl; } //更适用的来说取文件的后缀应当使用另一个接口rfind size_t pos4 = file3.rfind('.'); if(pos4 != string::npos) { string sub4 = file3.substr(pos4); cout << sub4 << endl; } cout << "----------cut----------" << endl; } void test_string3() { //取出url中的protocol、domain、uri ———— 网址 = 协议 + 域名 + 资源定位 string url("http://www.cplusplus.com/reference/string/string/find/"); size_t i1 = url.find("://");//find也可以找串 if(i1 != string::npos) { string protocol = url.substr(0, i1 - 0); cout << "protocol:" << protocol << endl; } size_t i2 = url.find('/', i1 + 3);//find的第四个版本 if(i2 != string::npos) { string domain = url.substr(i1 + 3, i2 - (i1 + 3)); cout << "domain:" << domain << endl; } size_t i3 = url.find('/', i2); if(i3 != string::npos) { string uri = url.substr(i3); cout << "uri:" << uri << endl; printf("uri:%s\n", uri.c_str());//C语言去输出string做不到,但是提供了c_str } } int main() { test_string1(); //3、find test_string2(); test_string3(); return 0; }
📝说明
push_back | append | operator+= ❗
如果你要尾插一个字符用 push_back，如果你要尾插一个字符串用 append。个人感觉这是 string 设计的不好的地方，为什么不再重载一个 push_back 呢，非要去搞一个 append 来恶心人，而 append 又重载了六个版本，也没啥太大的价值，比较常用的也就三、四版本。
相对于 push_back、append 更推荐使用 operator+=，因为它可以追加一个字符，也可以追加一个字符串，还可以追加一个对象。
这里我们发现 string 里面没有头插、头删，但它有中间插入、删除。
insert | erase ❗
可以看到实现了七个版本，这里就了解了解较为常用的，其余简单提一下。
它不仅仅可以中间插入、也可以在头上插入，还可以在尾部插入。
但是对于 insert 能不用就不用，因为效率比较低，它需要挪动数据。
与 insert 对应的是 erase。
erase 的第一个版本参数中的 npos 比较特殊，它给的是一个缺省参数，nops 是这个类里的静态成员变量，它是 -1，但实际上不是 -1，因为这个 -1 给了 size_t，所以它转换为补码就是整型的最大的值。
find | rfind ❗
对于 find 的返回值，一般是 int，找到返回下标，找不到返回 -1。这里用 size_t 的想法是，找到返回下标，找不到会返回 nops，但是正常的字符不可能有那么长。
查找字符串中内容的最后一次出现：
substr ❗
生成子串。
c_str ❗
它可以和 C语言配合使用。
5、string类非成员函数
| 函数 | 功能说明 |
| operator+ | 尽量少用，因为传值返回，导致深拷贝效率低 |
| operator>> —— 重点 | 输入运算符重载 |
| operator<< —— 重点 | 输出运算符重载 |
| getline —— 重点 | 获取一行字符串 |
| relational operators —— 重点 | 大小比较 |
 |
#include<string> #include<iostream> using namespace std; int main() { string s1("hello"); s1 + "world"; cout << s1 << endl; s1 += "world"; cout << s1 << endl; cout << "----------cut----------" << endl; return 0; }
📝说明
operator+ 和 operator+= ❗
它们的作用都是尾插，但是 operator+= 会改变当前字符串，而 operator+ 不改变当前字符串。
relational operators ❗
string 还提供了比较大小的接口，可以看到非常多的版本，比如对象跟对象比、字符串跟对象比，自我感觉比较冗余。
因为字符串是可以被隐式类型转换成 string 的：
string s1("hello");//正常写法,string支持单参数的构造函数 string s2 = "world";//隐式类型转换,先将字符串构造一个string,再将string拷贝构造s2。最后优化成直接构造
所以这里是想说就算是字符串跟对象比，字符串也可以隐式转换成对象，没必要再实现一个版本。
6、补充
| 函数 | 功能说明 |
| to_string | 数值转字符串 |
| stoi | 字符串转数值 |
#include<string> #include<iostream> using namespace std; int main() { int i = 1234; string str = to_string(i); cout << str << endl; int j = stoi(str); cout << j << endl; return 0; }
📝说明
to_string | stoi ❗
将数值转换为字符串(注意它不是 string 的成员函数，而是全局函数)：
在 C语言中有类似的函数 itoa，它需要自己提供空间，且有些 OJ 上还不支持，因为它不是标准的 C库，所以不够好用。
可以看到它还提供了将字符串转成整数：
💦 小试牛刀
1、仅仅反转字母＜难度系数⭐＞
📝 题述：给你一个字符串 s ，根据下述规则反转字符串：
- 所有非英文字母保留在原有位置。
- 所有英文字母 (小写或大写) 位置反转。
返回反转后的 s 。
💨示例1：
输入：s = “ab-cd”
输出：“dc-ba”
💨示例2：
输入：s = “a-bC-dEf-ghIj”
输出：s = “a-bC-dEf-ghIj”
💨示例3：
输入：s = “Test1ng-Leet=code-Q!”
输出：“Qedo1ct-eeLg=ntse-T!”
⚠ 提示
- 1 <= s.length <= 100
- s 仅由 ASCII 值在范围 [33, 122] 的字符组成
- s 不含 ‘"’ 或 ‘\’
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：
- 这里利用快排的思想 —— 下标完成
- 逻辑不变 —— 将下标改造成迭代器
1、
class Solution { public: bool isLetter(char ch)//判断是否为字母，如果是返回treu，否则返回false { if(ch >= 'a' && ch <= 'z') return true; if(ch >= 'A' && ch <= 'Z') return true; return false; } string reverseOnlyLetters(string s) { int begin = 0; int end = s.size() - 1; while(begin < end) { while(begin < end && !isLetter(s[begin]))//非英文字母，且保证最后begin和end重合 { ++begin; } while(begin < end && !isLetter(s[end]))//非英文字母，且保证最后begin和end重合 { --end; } swap(s[begin], s[end]);//交换 //交换后还要调整 ++begin; --end; } return s; } };
2、
class Solution { public: bool isLetter(char ch)//判断是否为字母，如果是返回treu，否则返回false { if(ch >= 'a' && ch <= 'z') return true; if(ch >= 'A' && ch <= 'Z') return true; return false; } string reverseOnlyLetters(string s) { auto begin = s.begin(); auto end = s.end() - 1; while(begin < end) { while(begin < end && !isLetter(*begin))//非英文字母，且保证最后begin和end重合 { ++begin; } while(begin < end && !isLetter(*end))//非英文字母，且保证最后begin和end重合 { --end; } swap(*begin, *end);//交换 //交换后还要调整 ++begin; --end; } return s; } };
2、字符串中第一个唯一字符＜难度系数⭐＞
📝 题述：给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
💨示例1：
输入：s = “leetcode”
输出：0
💨示例2：
输入: s = “loveleetcode”
输出: 2
💨示例3：
输入: s = “aabb”
输出: -1
⚠ 提示
- 1 <= s.length <= 105
- s 只包含小写字母
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：如果一个字符一个字符的去比较，效率很慢，最坏的情况是 O(N2)，所以我们这里建立一个映射关系去统计次数，原理同计数排序
class Solution { public: int firstUniqChar(string s) { int count[26] = {0}; //统计每个字符出现的次数 for(auto ch:s) { count[ch - 'a']++; } //找出字符串中第一个不重复的字符 for(int i = 0; i < s.size(); ++i) { if(count[s[i] - 'a'] == 1) { return i; } } return -1; } };
3、字符串里面最后一个单词的长度＜难度系数⭐⭐＞
📝 题述：计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于 5000。(注：字符串末尾不以空格为结尾)。
输入描述：输入一行，代表要计算的字符串，非空，长度小于 5000。
输出描述：输出一个整数，表示输入字符串最后一个单词的长度。
💨示例1：
输入：hello nowcoder
输出：8
⚠ 说明
最后一个单词为 nowcoder，长度为 8。
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：无
#include<string> #include<iostream> using namespace std; int main() { string s; //cin >> s; getline(cin, s); size_t pos = s.rfind(' '); if(pos != string::npos)//多个单词 { cout << s.size() - (pos + 1) << endl; } else//一个单词 { cout << s.size() << endl; } return 0; }
📝说明
scanf 和 cin 都有一个特点，默认遇到空格或换行，它会认为空格前后是两个独立的变量。
针对这种情况我们就不能用 cin 了，在 string 里提供了一个 getline：
它遇到换行才结束。
4、验证一个字符串是否是回文＜难度系数⭐＞
📝 题述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。本题中，我们将空字符串定义为有效的回文串。
💨示例1：
输入：“A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串
💨示例2：
输入: “race a car”
输出: false
解释：“raceacar” 不是回文串
⚠ 提示
- 1 <= s.length <= 2 * 105
- 字符串 s 由 ASCII 字符组成
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：
这道题数字是一个坑，对于字母比较我们可以用小的 + 32 或者全部转小写或大写。
- 常规写法，暴力求解，稍不注意就会写得比较复杂，然后过不了
- 先将所有的字母转大写或小写
1：
class Solution { public: bool IsLetterOrNun(char ch) { if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) { return true; } else { return false; } } bool isPalindrome(string s) { int begin = 0, end = s.size() - 1; while(begin < end) { while(begin < end && !IsLetterOrNun(s[begin]))//跳过非字母数字 { ++begin; } while(begin < end && !IsLetterOrNun(s[end]))//跳过非字母数字 { --end; } if(s[begin] != s[end]) { //有一个是数字，就不存在大小写比较问题 if(s[begin] < 'A' || s[end] < 'A') { return false; } else if(s[begin] < s[end] && s[begin] + 32 == s[end]) { ++begin; --end; } else if(s[end] < s[begin] && s[end] + 32 == s[begin]) { ++begin; --end; } else { return false; } } else { ++begin; --end; } } return true; } };
2：
class Solution { public: bool IsLetterOrNun(char ch) { if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) { return true; } else { return false; } } bool isPalindrome(string s) { //大写转小写 for(auto& ch : s) { if(ch >= 'A' && ch <= 'Z') { ch += 32; } } int begin = 0, end = s.size() - 1; while(begin < end) { while(begin < end && !IsLetterOrNun(s[begin])) { ++begin; } while(begin < end && !IsLetterOrNun(s[end])) { --end; } if(s[begin] != s[end]) { return false; } else { ++begin; --end; } } return true; } };
5、 字符串相加＜难度系数⭐＞
📝 题述：给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库 (比如 BigInteger：大数运算)， 也不能直接将输入的字符串转换为整数形式。
💨示例1：
输入：num1 = “11”, num2 = “123”
输出：“134”
💨示例2：
输入：num1 = “456”, num2 = “77”
输出：“533”
💨示例3：
输入：num1 = “0”, num2 = “0”
输出：“0”
⚠ 提示
- 1 <= num1.length, num2.length <= 104
- num1 和 num2 都只包含数字 0 - 9
- num1 和 num2 都不包含任何前导零
🧷 平台：Visual studio 2017 && windows
🍳 拓展：
有些语言里会提供一个库叫 BigInteger(大数运算)：顾名思义，就是很大的数值的数进行一系列的运算。由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。
我们平时表示较大整型时用的是 long long 或 int64，它们都是 8Byte，能表示的范围是 264，已经很大了，大概是一个 20 位的整数(严格来说是 19 位)，但是在一些高科技领域要进行科学计算，所以还远远不够，那么怎么处理呢？？？
这时有人就写出了 BigInteger，它用字符串来表示整数 —— 意味着无论多大的整数都可以表示。
可以看到这道题用 C语言去做，两个数字相加之和是多大，不好开空间，但是用 string 的话就可以不用管了，string 的底层实现了自动增容。
🔑 核心思想 1：
class Solution { public: string addStrings(string num1, string num2) { string retStr; int end1 = num1.size() - 1; int end2 = num2.size() - 1; int carry = 0; while(end1 >= 0 || end2 >= 0)//只要还有一位那么就继续 { int val1 = 0, val2 = 0; if(end1 >= 0) { val1 = num1[end1] - '0'; --end1; } if(end2 >= 0) { val2 = num2[end2] - '0'; --end2; } int ret = val1 + val2 + carry; if(ret > 9)//进位 { ret -= 10; carry = 1; } else { carry = 0; } //头插 retStr.insert(0, 1, '0' + ret); //retStr.insert(retStr.begin(), '0' + ret);//同上 } if(carry == 1)//还有一位的情况："1","9" { retStr.insert(retStr.begin(), '1'); } return retStr; } };
📝说明
假设 num1 和 num2 的长度为 n，则如上代码的时间复杂度是多少 ❓
O(N) ？？？
就思路来说时间复杂度是 O(N)，但是这里使用了 insert，所以原本是 O(N) 的时间复杂度硬是写成了 O(N2)
🧿 优化版本
🔑 核心思想 2：
每次将结果尾插，最后再逆置。
C++ 在算法这个头文件里提供了此类函数：
只要有迭代器，它就可以针对任何容器去使用：
class Solution { public: string addStrings(string num1, string num2) { string retStr; int end1 = num1.size() - 1; int end2 = num2.size() - 1; int carry = 0; while(end1 >= 0 || end2 >= 0)//只要还有一位那么就继续 { int val1 = 0, val2 = 0; if(end1 >= 0) { val1 = num1[end1] - '0'; --end1; } if(end2 >= 0) { val2 = num2[end2] - '0'; --end2; } int ret = val1 + val2 + carry; if(ret > 9)//进位 { ret -= 10; carry = 1; } else { carry = 0; } //尾插 retStr += ('0' + ret); } if(carry == 1)//还有一位的情况："1","9" { retStr += '1'; } //逆置 reverse(retStr.begin(), retStr.end()); return retStr; } };
📝说明
