《STL 六大组件之容器探秘：深入剖析 string》

一、string 类简介
二、string 类的常用接口
- 1. 构造函数（constructor function）
- 2. 与容量相关的接口（capacity）
- 3. 与迭代器有关的接口（iterator）
- 4. 与元素访问有关的接口（element access）
- 5. 与内容修改有关的接口（modify)
- 6. 与 string 对象操作有关的接口（operation）
- 7. string 类的关系运算符重载接口
- 8. string 类的输入输出
三、与 string 类相关的精选习题
- 1. 把字符串转换成整数（atoi）
- 2. 字符串相加
- 3. 仅仅反转字母
- 4. 字符串中的第一个唯一字符
- 5. 字符串最后一个单词的长度
- 6. 验证回文串
- 7. 反转字符串Ⅱ
- 8. 反转字符串中的单词Ⅲ
- 9. 字符串相乘

一、string 类简介

string 是 C++ 标准库中的一个类，该类专门用来管理字符串。相比于 C 语言中使用字符数组来管理字符串，string 类使用方便且更加强大。
不同于 C 风格字符串，string

二、string 类的常用接口

string 类一共有一百多个接口，而常用的接口也就二十来个。所以需要牢牢掌握这常用的二十来个结构，剩下的接口在需要的时候会查询文档即可。

1. 构造函数（constructor function）

以下是 C++ 标准库中 string 类的构造函数，上半部分是常用的构造函数，需要掌握且熟练运用；而下半部分不常用的构造函数只需了解即可。

（1）函数原型

// 构造函数

// 常用的构造函数
string();  // 默认构造函数
string(const string& str);  // 复制构造函数
string(const char* str)  // 用 C 字符串 s 初始化
string(const char* s, size_t n);  // 用 C 字符串 s 的前 n 个字符初始化
string(size_t n, char c);  // 用 n 个字符 c 初始化

// 不常用的构造函数
string (const string& str, size_t pos, size_t len = npos);  // 用 string 类对象 str 的下标为 pos 开始的长度为 len 的子串初始化
template <class InputIterator>  string  (InputIterator first, InputIterator last);  // 用迭代器[first, last)范围内的字符串初始化

（2）使用演示

// string 构造函数使用演示
void test1()
{
	// 默认构造函数
	string str1;
	cout << "str1 = " << str1 << endl;
	// 使用 C 字符串初始化
	string str2("apple");
	cout << "str2 = " << str2 << endl;
	// 复制构造函数
	string str3(str2);
	cout << "str3 = " << str3 << endl;
	// 用 C 字符串的前 n 个字符初始化
	string str4("aaabbb", 3);
	cout << "str4 = " << str4 << endl;
	// 用 n 个字符 c 初始化
	string str5(5, 'e');
	cout << "str5 = " << str5 << endl;
}

（3）运行结果
在这里插入图片描述

2. 与容量相关的接口（capacity）

与 C 字符串相比 string 类的一个明显的优势在于它可以根据字符串的长度进行自动增容。而 C 字符串需要提前计算好字符串的长度而开辟相应大小的字符数组。

（1）函数原型

// 常用的与容量有关的接口
size_t size() const;  // 返回当前 string 类对象的长度（与其他 STL 组件保持一致）
size_t length() const;  // 返回当前 string 类对象的长度（未把 string 列为 STL 之前使用的成员函数）
void resize(size_t n);  // 把当前 string 对象的 size 修改至 n
void resize(size_t n, char c);  // 把当前 string 对象的 size 修改至 n，并把新增的字符全部设置为 c
size_t capacity() const;  // 返回当前 string 类对象的容量
void reserve(size_t n = 0);  // 把当前 string 类对象的容量修改为 n
bool empty() const;  // 判断当前 string 类对象是否为空，若为空返回 true，否则返回 false

// 不常用的与容量有关的接口
size_t max_size() const;  // 返回 string 类对象的最大容量（可以容纳的最长字符数）
void clear();  // 把当前 string 类对象的内容清空，长度变为 0，容量不变
void shrink_to_fit();  // 请求字符串减小容量来适应 size 的大小

（2）使用演示

// string 类与容量有关的函数使用演示
void test2()
{
	string str1("C++");
	// 原 size 和 capacity
	cout << "Size: " << str1.size() << endl;
	cout << "Capacity: " << str1.size() << endl;
	cout << "Length: " << str1.length() << endl;
	// 修改 size 并指定字符
	str1.resize(5, 'a');
	cout << "\nstr1 = " << str1 << endl;
	cout << "Size: " << str1.size() << endl;
	cout << "Capacity: " << str1.size() << endl;

	// 修改 capacity
	str1.reserve(18);
	cout << "\nstr1 = " << str1 << endl;
	cout << "Size: " << str1.size() << endl;
	cout << "Capacity: " << str1.size() << endl;

	// 清空并判断当前 string 对象是否为空
	str1.clear();
	cout << "\nstr1 = " << str1 << endl;
	cout << "Size: " << str1.size() << endl;
	cout << "Capacity: " << str1.size() << endl;
	if (str1.empty())
		cout << "Current string is empty.\n";
}

（3）运行结果
在这里插入图片描述

3. 与迭代器有关的接口（iterator）

迭代器是所有 STL 容器都支持的一种访问手段，迭代器的实质可以是指针也可以是其他自定义类型。支持迭代器也就支持范围 for。

（1）函数原型

// 常用的迭代器接口
iterator begin();  // 返回普通 string 对象的开头迭代器
iterator end();  // 返回普通 string 对象的尾后迭代器
const_iterator begin() const;  // 返回 const string 对象的开头迭代器
const_iterator end() const;  // 返回 const string 对象的尾后迭代器
reverse_iterator rbegin();  // 返回普通 string 对象最后一个元素的迭代器
reverse_iterator rend();  // 返回普通 string 对象第一个元素前一个元素的迭代器
const_reverse_iterator rbegin() const;  // 返回 const string 对象最后一个元素的迭代器
const_reverse_iterator rend(); const  // 返回 const string 对象第一个元素前一个元素的迭代器

// 还有几个前缀 c 的不常用的迭代器接口，用来返回 const 类型的迭代器，也就等价于上述四个返回 const 迭代器的接口。感兴趣的可以自己去查询一下文档
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;

（2）使用演示
对迭代器可以使用解引用操作符（*）获得当前位置的元素。下面展示可以访问 string 元素的几种方法。

// string 类迭代器相关函数使用演示
// string 类迭代器相关函数使用演示
void test3()
{
	string str("Good night, everyone !");
	// 使用迭代器正序遍历
	string::iterator it = str.begin();
	while (it != str.end())
	{
		cout << *it;
		++it;
	}
	cout << endl;
	// 使用迭代器逆序遍历
	string::reverse_iterator rit = str.rbegin();
	while (rit != str.rend())
	{
		cout << *rit;
		++rit;
	}
	cout << endl;
	// 使用范围 for 遍历（编译器在编译阶段会替换成迭代器）
	for (const auto& it : str)
		cout << it;
	cout << endl;
	// 普通 string 类对象可以使用 const 迭代器
	string::const_iterator cit = str.begin();
	// const string 类不可以使用普通迭代器
	const string str1("C++");
	//it = str1.begin();  // 报错
	cit = str1.begin();  // 正确，const 对象只能使用 const 迭代器
}

（3）运行结果
在这里插入图片描述

4. 与元素访问有关的接口（element access）

string 类通过使用下标运算符访问其类对象的元素，当然还有其他几个不常用的接口；

（1）函数原型

// 常用的访问元素有关的接口
char& operator[](size_t pos);  // 返回普通 string 对象 pos 下标处的字符引用
const char& operator[](size_t pos) const;  // 返回 const string 对象 pos 下标出的字符引用

// 不常用的访问元素有关的接口
// at 接口与上面两个函数的区别在于，at 检查下标时会发出异常，而下标运算符使用断言
char& at(size_t pos);
const char& at(size_t pos) const;
// 返回当前 string 对象的最后一个字符的引用
char& back();
const char& back() const;
// 返回当前 string 对象的第一个字符的引用
char& front();
const char& front() const;

（2）使用演示

// （4）string 类访问元素相关的接口
void test4()
{
	string str("little fool");
	// 使用下标运算符访问 str 的每个字符元素
	for (int i = 0; i < str.size(); ++i)
		cout << str[i];
	cout << endl;
}

（3）运行结果
在这里插入图片描述

5. 与内容修改有关的接口（modify)

string 类修改内容的接口有很多个，但最常用的是 += 操作符重载，该操作符重载既可以在末尾拼接字符串，也可以在末尾拼接单个字符。

（1）函数原型

// 常用的 string 修改内容的接口
string& operator+=(const string& str);  // 在当前 string对象末尾拼接一个 string 对象 str
string& operator+=(const char* s);  // 在当前 string 对象末尾拼接一个 C 风格字符串 s
string& operator+=(char c);  // 在当前 string 对象末尾拼接一个字符 c
void push_back(char c);  // 在当前 string 对象末尾拼接一个字符 c
string& append(const string& str);  // 在当前 string 对象末尾拼接一个 string 对象
string& append(const char* s);  // 在当前 string 对象末尾拼接一个 C 风格字符串
string& append(size_t n, char c);  // 在当前 string 对象末尾拼接 n 个字符 c
// insert() 接口有多个重载，需要的时候需要查阅相关文档
string& insert(size_t pos, const string& str);  // 在当前 string 对象的下标 pos 处插入一个 string 对象 str
string& insert(size_t pos, const char& s);  // 在当前 string 对象的下标 pos 处插入一个 C 风格字符串
string& erase(size_t pos = 0, size_t len = npos);  // 删除当前 string 对象从 pos 位置开始的长度为 len 的子串
iterator erase(iterator p);  // 删除当前迭代器位置对应的字符，返回下一个字符的迭代器
void swap(string& str);  // 把当前 string 对象和 str 交换
void pop_back();  // 删除当前 string 对象的最后一个字符

// 不常用的 string 修改内容的接口
iterator erase(iterator first, iterator last);  // 删除该迭代器区间的所有字符，返回 last 后一个位置的迭代器
// assign() 接口，给当前 string 对象重新赋值，但 string 类主要使用赋值运算符重载给 string 对象重新赋值
string& assign(const string& str);
string& assign(const char* s);
// replace() 接口，替换当前 string 对象的部分内容
string& replace(size_t pos, size_t len, const string& str);  // 从当前 string 对象的下标 pos 开始，使用 str 的前 len 个字符替换

（2）使用演示

// （5）string 类修改内容有关的接口
void test5()
{
	string str("Hello");
	// string 类的 += 操作符重载演示
	str += ' ';
	str += "world";
	string str1(" !");
	str += str1;
	cout << "str = " << str << endl;
	// 尾插和尾删
	str.push_back('A');
	cout << "str = " << str << endl;
	str.pop_back();
	cout << "str = " << str << endl;
	// 在任意位置插入
	string str2("A");
	str2.insert(1, "apple");
	cout << "str2 = " << str2 << endl;
	int end = (int)str2.size();
	str2.insert(end, ".");
	cout << "str2 = " << str2 << endl;
	// 在任意位置删除
	int len = (int)str2.size() - 1;
	str2.erase(1, len);
	cout << "str2 = " << str2 << endl;
	// 交换两个 string 对象
	string str3("Java");
	string str4("python");
	cout << "str3 = " << str3 << endl;
	cout << "str4 = " << str4 << endl;
	str3.swap(str4);
	cout << "str3 = " << str3 << endl;
	cout << "str4 = " << str4 << endl;
}

（3）运行结果
在这里插入图片描述

6. 与 string 对象操作有关的接口（operation）

虽然 stirng 类对象不需要以空字符结尾，但是由于 C++ 兼容 C，所以其结尾依旧保留空字符，而使用 c_str() 接口，可以获得其 C 风格字符串的形式，也就是字符指针（char*)。

（1）函数原型

// 常用的与 string 对象操作有关的接口
const char* c_str() const;  // 返回当前 string 对象首字符的地址
size_t find(const string& str, size_t pos = 0) const;  // 在当前 string 对象的 pos 位置开始，寻找 stirng 对象 str 首次出现的位置
size_t find(const char* s, size_t pos = 0) const;  // 在当前 string 对象 pos 位置开始，寻找 C 风格字符串 s 首次出现的位置
size_t find(char c, size_t pos = 0) const;  // 在当前 string 对象 pos 位置开始，寻找字符 c
// 下面三个函数和前面三个 find 函数一致，只不过是从后往前查找
size_t rfind(const string& str, size_t pos = 0) const;
size_t rfind(const char* s, size_t pos = 0) const;
size_t rfind(char c, size_t pos = 0) const;

// 不常用的与 string 对象操作相关的接口
string substr(size_t pos = 0, size_t len = npos) const;  // 返回当前 string 对象 pos 位置开始的长度为 len 的子串

（2）使用演示

// （6）与 string 对象操作相关的接口
void test6()
{
	string str("You are very good!");
	// 获取 C 风格字符串
	const char* s = str.c_str();
	cout << "str = " << str << endl;
	cout << "s  = " << s << endl;
	// 在 str 中查找字符
	size_t pos = str.find('a');
	for (size_t i = pos; i < str.size(); ++i)
		cout << str[i];
	cout << endl;
	// 在 str 中查找字符串
	pos = str.find("very");
	for (size_t i = pos; i < str.size(); ++i)
		cout << str[i];
	cout << endl;
}

（3）运行结果
在这里插入图片描述

7. string 类的关系运算符重载接口

string 类重载了所有关系运算符，可以直接使用这些关系运算符对两个 string 对象进行比较，这些接口会按照字典顺序进行比较，返回布尔值。

（1）函数原型

// string 类关系运算符重载
bool operator<(const string& str) const;  // 当前 string 对象和 str 比较，若比 str 小则返回 true；否则返回 false
// 下面的接口同第一个接口
bool operator>(const string& str) const;
bool operator<=(const string& str) const;
bool operator>=(const string& str) const;
bool operator==(const string& str) const;
bool operator!=(const string& str) const;

（2）使用演示

// string 类关系运算符重载
void test7()
{
	string str1("C++");
	string str2("Java");
	// 开始比较
	cout << "str1 > str2 = " << (str1 > str2) << endl;
	cout << "str1 >= str2 = " << (str1 >= str2) << endl;
	cout << "str1 < str2 = " << (str1 < str2) << endl;
	cout << "str1 <= str2 = " << (str1 <= str2) << endl;
	cout << "str1 == str2 = " << (str1 == str2) << endl;
	cout << "str1 != str2 = " << (str1 != str2) << endl;
}

（3）运行结果
在这里插入图片描述

8. string 类的输入输出

string 类的对象可以直接使用 cin 和 cout 搭配流提取运算符（>>）和流插入运算符（<<）进行输入和输出，因为 string 类重载了流插入和流提取运算符。string 类和 C 风格字符串在使用 cin 和流提取运算符进行输入时也只能输入一个单词，遇到空白就停止输入。
如果需要获取多个单词的输入，就需要使用 istream 类的 getline 方法来获取一行输入。

（1）函数原型

istream& operator>>(istream& is, string& str);  // 流提取运算符重载
ostream& operator<<(ostream& os, const string& str);  // 流插入运算符重载

（2）使用演示

// （8）string 类的输入输出
void test8()
{
	string str;
	// 输入一个单词
	cout << "Please enter a word.\n";
	cin >> str;
	cout << "The word is " << str << endl;
	// 注意：上一次的输入会把换行符留在输入流，所以需要把遗留的换行符扔掉
	cin.get();
	// 输入一句话
	cout << "Please enter a sentence.\n";
	getline(cin, str);
	cout << "The sentence is " << str << endl;
}

（3）运行结果
在这里插入图片描述

三、与 string 类相关的精选习题

1. 把字符串转换成整数（atoi）

题目链接：link

题目描述： 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

示例：
在这里插入图片描述
提示：=

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成

（1）解题思路：

首先使用 while 循环跳过前面的前导空格；
使用 if 语句检查下一个非空格字符是否为负号，如果不是负号则为正数；
开始读取数字，直到遇到第一个非数字字符。如果没有数字字符，则为 0；
如果整数超过 INT_MAX 则为 INT_MAX，如果整数小于 INT_MIN 则为 INT_MIN;
返回结果整数。

（2）解题代码：

class Solution {
public:
    int myAtoi(string str) {
        // 舍弃前面的前导空格
        int i = 0;
        while (' ' == str[i])
            ++i;
        // 判断正负号
        int flag = 1;
        if ('-' == str[i])
        {
            flag = -1;
            ++i;
        }
        else if ('+' == str[i])
        {
            flag = 1;
            ++i;
        }
        // 开始计算
        int len = str.size();
        long long result = 0;
        while (i < len)
        {
            // 是数字字符则加入计算
            if (isdigit(str[i]))
            {
                result = result * 10 + str[i] - '0';
                // 判断计算结果
                if (result > INT_MAX)
                {
                    if (1 == flag)
                        return INT_MAX;
                    else
                        return INT_MIN;
                }
            }
            else  // 否则结束计算
            {
                break;
            }
            // 下一个字符
            ++i;
        }
        // 返回计算结果
        return result * flag;
    }
};

2. 字符串相加

题目链接：link

题目描述：

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

示例：
在这里插入图片描述

提示：

1 <= num1.length, num2.length <= 104
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零

（1）解题思路：

参考数字的加法运算，从两个字符串的最后一个字符开始相加，分别计算当前位置和进位，然后把当前位置拼接到结果字符串中，直到其中一个字符串达到末尾；
把剩下没到末尾的字符串剩下的字符继续拼接到结果字符串中，最后把整个字符串逆置；
返回结果字符串。

（2）解题代码：

class Solution {
public:
    string addStrings(string num1, string num2) {
        // 所需变量
        string result;
        int i1 = num1.size() - 1, i2 = num2.size() - 1;
        int carry = 0;
        // 开始拼接
        while (i1 >= 0 || i2 >= 0)
        {
            // 计算当前两位
            int n1 = (i1 >= 0? num1[i1--] - '0' : 0);
            int n2 = (i2 >= 0? num2[i2--] - '0' : 0);
            // 拼接
            result += (n1 + n2 + carry) % 10 + '0';
            // 计算进位
            carry = (n1 + n2 + carry) / 10;
        }
        // 如果两个字符串同时结束，但是 carry 不为 0
        if (carry)
            result += carry + '0';
        // 逆置结果字符串
        reverse(result.begin(), result.end());
        // 返回结果字符串
        return result;
    }
};

3. 仅仅反转字母

题目链接：link

题目描述： 给你一个字符串 s ，根据下述规则反转字符串：

所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s 。

示例：
在这里插入图片描述
提示：
4. 1 <= s.length <= 100
5. s 仅由 ASCII 值在范围 [33, 122] 的字符组成
6. s 不含 ‘"’ 或 ‘\’

（1）解题思路：

使用两个指针，分别指向字符串的首尾，当两个指针未相遇并且都指向字母字符时交换，当两个指针相遇或者错开时则结束；
返回交换完毕的字符串；

（2）解题代码：

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int left = 0, right = s.size() - 1;
        // 开始交换
        while (left < right)
        {
            // 左右寻找字母字符
            while (left < right && !isalpha(s[left]))
                ++left;
            while (left < right && !isalpha(s[right]))
                --right;
            // 交换
            swap(s[left], s[right]);
            // 下一组
            ++left;
            --right;
        }
        // 返回交换完成的字符串
        return s;
    }
};

4. 字符串中的第一个唯一字符

题目链接：link

题目描述： 给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。

示例：
在这里插入图片描述
提示:

1 <= s.length <= 105
s 只包含小写字母

（1）解题思路：

由于字符串只有小写字母，那么创建一个包含 26 个元素的 int 数组，对应 26 个小写字母的出现次数；
遍历一遍数组，计算每个字符出现的次数，再遍历一遍数组，找出第一个出现一次的字符；
返回对应的下标；

（2）解题代码：

class Solution {
public:
    int firstUniqChar(string s) {
        int times[26] = {0};
        // 计算每个字符出现的次数
        for (const auto& e : s)
        {
            ++times[e - 'a'];
        }
        // 找到第一个出现一次的字符
        int len = s.size();
        for (int i = 0; i < len; ++i)
        {
            if (1 == times[s[i] - 'a'])
                return i;
        }
        // 没有找到返回 -1
        return -1;
    }
};

5. 字符串最后一个单词的长度

题目链接：link

题目描述： 对于给定的若干个单词组成的句子，每个单词均由大小写字母混合构成，单词间使用单个空格分隔。输出最后一个单词的长度。

输入描述：
在一行上输入若干个字符串，每个字符串代表一个单词，组成给定的句子。
除此之外，保证每个单词非空，由大小写字母混合构成，且总字符长度不超过 10³。

输出描述：
在一行上输出一个整数，代表最后一个单词的长度。

（1）解题思路：

创建一个 string 对象接受输入，每次输入一个单子并计算其长度，直到遇到换行符；
返回此时的长度，也就是最后一个单词的长度。

（2）解题代码：

// 头文件
#include <iostream>
#include <string>

// using 声明
using std::string;
using std::cin;
using std::cout;
using std::endl;

int main() {
    int len = 0;
    string str;
    // 输入单词并计算长度
    while (cin >> str)
    {
        len = str.size();
    }
    // 输出最后一个单词的长度
    cout << len << endl;
}
// 64 位输出请用 printf("%lld")

6. 验证回文串

题目链接：link

题目描述： 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例：
在这里插入图片描述

提示：

1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成

（1）解题思路：

首先遍历一遍字符串，把所有大写字母转换成小写字母，然后把所有字母数字字符拼接到一个新的字符串后头；
然后使用两个指针正着和倒着遍历来验证新的字符串是否为回文字符串；
返回验证的结果；

（2）解题代码：

class Solution {
public:
    bool isPalindrome(string s) {
        string tmp;
        // 小写转大写并把所有的字母数字字符拼接到新的字符串后面
        for (int i = 0; i < s.size(); ++i)
        {
            if (isalnum(s[i]))
            {
                tmp += tolower(s[i]);
            }
        }
        // 验证新的字符串
        int left = 0, right = tmp.size() - 1;
        while (left < right)
        {
            // 判断当前这组字符
            if (tmp[left] != tmp[right])
            {
                return false;
            }
            // 下一组字符
            ++left;
            --right;
        }
        // 是回文串
        return true;
    }
};

7. 反转字符串Ⅱ

题目链接：link

题目描述： 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例：
在这里插入图片描述

提示：

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

（1）解题思路：

while 循环，前后指针法，cur 指针往前走，pre 指针不动，当 cur 指针与 pre 指针的距离达到 2k-1 时，逆置前 k 个字符并更新 pre 指针的位置；
当 cur >= s.size() 时跳出循环，并根据此时 cur - pre 的值判断最后一组的情况；
返回逆置完成的字符串。

（2）解题代码：

// 逆置函数
void reverse(char* left, char* right)
{
    while (left < right)
    {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        // 下一组
        ++left;
        --right;
    }
}

class Solution {
public:
    string reverseStr(string s, int k) {
        // 使用前后指针遍历字符串，每当两个指针相隔 2k 时，反转
        int pre = 0, cur = 0;
        int len = s.size();
        while (cur < len)
        {
            if (cur - pre == 2 * k - 1)
            {
                // 反转前 k 个字符
                reverse(&s[pre], &s[pre + k - 1]);
                // 更新 pre
                pre = cur + 1;
            }
            // cur 前进
            ++cur;
        }
        // 判断最后的一段字符
        if (cur - pre < k)
            reverse(&s[pre], &s[cur - 1]);
        else
            reverse(&s[pre], &s[pre + k - 1]);
        // 返回逆置完毕的字符串
        return s;
    }
};

8. 反转字符串中的单词Ⅲ

题目链接：link

题目描述： 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：
在这里插入图片描述

提示：

1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里至少有一个词。
s 中的所有单词都用一个空格隔开。

（1）解题思路：

while 循环，前后指针法，pre 不动，cur 前进，当 cur 遇到空格时，逆置前面的单词后更新 pre，直到 cur 超出 s 末尾；
返回逆置完毕的 s。

（2）解题代码：

// 逆置函数
void reverse(char* left, char* right)
{
    while (left < right)
    {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        // 下一组
        ++left;
        --right;
    }
}

class Solution {
public:
    string reverseWords(string s) {
        int pre = 0, cur = 0, len = s.size();
        while (cur < len)
        {
            // 如果 cur 是空格，则逆置前面的单词
            if (' ' == s[cur])
            {
                reverse(&s[pre], &s[cur-1]);
                // 更新 pre
                pre = cur + 1;
            }
            // cur 前进
            ++cur;
        }
        // 逆置最后一个单词
        reverse(&s[pre], &s[cur-1]);
        // 返回逆置的字符串
        return s;
    }
};

9. 字符串相乘

题目链接：link

题目描述： 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例：
在这里插入图片描述
提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

（1）解题思路：

用其中一个字符串的每一位去乘以另一个字符串，然后把结果存在一个临时字符串中，最后加到结果字符串中去；
需要对不同的位进行补 0，个位不补，十位补一个 0，以此类推；
字符串的加法前面的习题中已经写过了，本题只是在其基础上进行了一些复杂的变化，难度没有什么提升；
返回最终的结果字符串。

（2）解题代码：
本题思路没有问题，但是代码写的一般般，大家可以参考自己修改完善一下。

// 字符串相加函数
string add_string(const string& num1, const string& num2)
{
    // 所需变量
    int i1 = num1.size() - 1;
    int i2 = num2.size() - 1;
    int carry = 0;
    string result;
    // 开始相加
    while (i1 >= 0 || i2 >= 0)
    {
        // 计算两个数字字符串当前位的值
        int n1 = (i1 >= 0 ? num1[i1] - '0' : 0);
        int n2 = (i2 >= 0 ? num2[i2] - '0' : 0);
        // 计算当前位
        int cur = n1 + n2 + carry;
        // 拼接当前位
        result += cur % 10 + '0';
        // 计算进位
        carry = cur / 10;
        // 下一组位
        --i1;
        --i2;
    } 
    // 判断是否存在进位
    if (carry)
        result += carry + '0';
    // 逆置
    reverse(result.begin(), result.end());
    // 返回结果
    return result;
}

class Solution {
public:
    string multiply(string num1, string num2) {
        // 若一个数为 0，则结果为 0
        if ("0" == num1 || "0" == num2)
            return "0";
        // 所需变量
        int i = num1.size() - 1;
        string result;
        // 用 num1 的每一位去乘以 num2
        while (i >= 0)
        {
            char cur = num1[i];
            string cur_result;
            int carry = 0;
            // 当前位开始相乘
            for (int j = num2.size() - 1; j >= 0; --j)
            {
                // 相乘
                int mul = (cur - '0') * (num2[j] - '0') + carry;
                // 计算本位并拼接到当前结果
                cur_result += mul % 10 + '0';
                // 计算进位
                carry = mul / 10;
            }
            // 补上进位
            if (carry)
                cur_result += carry + '0';
            // 逆置当前结果
            reverse(cur_result.begin(), cur_result.end());
            // 补零
            int n = num1.size() - i - 1;
            while (n--)
                cur_result += '0';
            // 把当前结果加到最终结果
            result = add_string(result, cur_result);
            // 下一位
            --i;
        }
        // 返回相乘的结果
        return result;
    }
};