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

string类在OJ的使用

news 2025/2/28 12:34:32

练习题1：仅仅反转字母

1.思路描述

2.代码实现

3.注意事项

练习题2：找字符串中第一个只出现一次的字符

1.思路1

1.1.思路描述

1.2.代码实现

2.思路2

2.1.思路描述

2.2.代码实现

3.思路3

3.1.思路描述

3.2.代码实现

4.总结

练习3：字符串里面最后一个单词的长度

1.注意事项

2.思路描述

3.代码实现

3.1.写法1

3.2.写法2

练习4：验证一个字符串是否是回文串

1.思路描述

2.代码实现

练习5：字符串相加

1.大数运算的介绍

2.思路分析

2.1.思路1：使用Insert函数进行头插。不考虑扩容带来的性能消耗。

(1)思路描述

(2)代码实现

2.2.思路2：使用operator+=函数尾插完后，再使用reverse函数逆序。为了防止在执行插入操作时扩容带来的性能消耗，则在进行插入操作之前使用reserve来提取开空间来避免扩容。

(1)思路描述

(2)reserve 函数预先开空间的作用

(3)代码实现

练习6：字符串相乘

1.思路1

1.1.思路描述

1.2.代码实现

练习7：翻转字符串II：区间部分翻转

1.思路

2.代码实现

练习8：翻转字符串III：翻转字符串中的单词

1.思路描述

2.代码实现

练习题1：仅仅反转字母

. - 力扣（LeetCode）

1.思路描述

该算法的核心思路是使用双指针法，通过两个指针分别从字符串的首尾开始向中间移动，在移动过程中忽略非英文字母，只对英文字母进行交换操作，从而实现仅反转字符串中字母的目的。

2.代码实现

#include<iostream>
#include<string>
using namespace std;//解题思路：虽然有3种遍历方式，但是在这里更加合适使用下标[]运算符重载函数operator[]访问数据，
//由于范围for循环是从前往后遍历，所以在该题是不用这种方式进行遍历的。这道题的思路和单趟的快速排序很像。class Solution 
{
public://判断字符是否为英文字母(包括大小写)的函数//参数 ch 是待判断的字符bool isLetter(char ch){//若字符ch是英文字母就返回trueif (ch >= 'a' && ch <= 'z')return true;if (ch >= 'A' && ch <= 'Z')return true;//若字符ch不是英文字母就返回falsereturn false;}//仅反转字符串中字母的函数//参数 S 是待处理的字符串string reverseOnlyLetters(string S){//检查输入的字符串 S 是否为空。如果为空，则直接返回该字符串，//因为空字符串无需进行反转操作。if (S.empty())return S;//注意：该题的解题思路有点类似于快速排序的单趟思路即左边找大右边找小后就停下来交换，而且写法也有点类似。//只不过该道题是左边找英文字母右边也找英文字母后就停下来交换。size_t begin = 0, end = S.size() - 1;//注意：size()返回值是字符串最后一个字符的下一个位置。while (begin < end)//注：若begin = end就相遇了则此时就不用交换英文字母了。{//注：这里可以访问单趟排序的思路，即让begin先从左找，找到后就停下，//然后再让end从右找，找到后就停下，最后begin和end位置的字符就交换。//begin从左往右找英文字母，找到就停下来。或者 begin 与 end 相遇，//begin也会停下来。while (begin < end && !isLetter(S[begin]))++begin;//不是字母，begin就往右走一步。//end从右往左找英文字母，找到就停下来。或者 begin 与 end 相遇，end也会停下来。while (begin < end && !isLetter(S[end]))--end;//不是字母，end就往左走一步。//当 begin 和 end 都指向字母字符时，使用 swap 函数交换这两个字符的位置。swap(S[begin], S[end]);//交换成功后，更新begin、end的值。++begin;--end;}//当 begin 不再小于 end 时，说明已经完成了所有字母字符的反转操作，//此时返回反转后的字符串 S。return S;}
};

复杂度分析

时间复杂度：该算法只对字符串进行了一次遍历，每个字符最多被访问两次（一次是移动 begin 指针时，一次是移动 end 指针时），因此时间复杂度为，其中是字符串的长度。
空间复杂度：只使用了常数级的额外变量 begin 和 end，没有使用额外的数组来存储数据，所有操作都是在原字符串上进行的，因此空间复杂度为。

3.注意事项

(1)常见报错案例：超出时间限制

解析：一般出现超出时间限制的报错信息的原因有以下几种情况

情况1：不是说代码性能不行，而是逻辑有问题导致死循环，此时的报错信息很少。
情况2：代码性能实在是不匹配，即时间复杂度不符合要求，此时的报错信息很长。

该代码错误原因：swap(s[begin], s[end])交换后，没有begin++、没有end--。

(2)跟string类相关题目，我们对string类的使用要求不是很高。对于string类的要求大多数都是修改 + 遍历，而遍历的使用的是下标运算符重载函数operator[]更加合适。

练习题2：找字符串中第一个只出现一次的字符

. - 力扣（LeetCode）

1.思路1

1.1.思路描述

该算法的核心思路是通过两层嵌套循环，对字符串中的每个字符进行逐一检查。对于字符串中的每一个字符，都将其与字符串中的其他所有字符进行比较，如果没有找到与之相同的其他字符，那么这个字符就是唯一的。由于是按照字符串的顺序依次检查每个字符，所以第一个被判定为唯一的字符就是我们要找的第一个不重复的字符。

1.2.代码实现

时间复杂度O(N ^ 2)；空间复杂度O(1).

#include <string>class Solution
{
public://该函数用于找出字符串 s 中第一个不重复字符的索引//如果不存在不重复的字符，则返回 -1int firstUniqChar(string s){//外层循环，遍历字符串 s 中的每个字符//cur 表示当前正在检查的字符的索引for(int cur = 0; cur < s.size(); cur++){//内层循环的索引，用于与当前字符进行比较int cmp = 0;//内层循环，遍历字符串 s 中的每个字符，用于和当前字符 s[cur] 进行比较for(cmp = 0; cmp < s.size(); cmp++){//如果当前比较的字符索引 cmp 不等于当前正在检查的字符索引 cur//并且这两个位置的字符相等，说明当前字符 s[cur] 不是唯一的//此时跳出内层循环if((cmp != cur) && (s[cur] == s[cmp]))break;}//如果内层循环正常结束（即没有因为找到重复字符而跳出）//说明 cmp 等于 s.size()，也就意味着当前字符 s[cur] 在字符串中是唯一的//返回该字符的索引 curif(cmp == s.size())return cur;}//如果遍历完整个字符串都没有找到唯一的字符，返回 -1return -1;}
};

2.思路2

2.1.思路描述

要找到字符串中第一个不重复的字符，关键在于统计每个字符的出现次数，然后依据统计结果找出第一个仅出现一次的字符。为了实现这个目标，我们将借助一个大小为 128 的数组（因为 ASCII 码表涵盖 128 个字符），数组的下标对应字符的 ASCII 码值，数组元素用于记录对应字符的出现次数。之后再次遍历字符串，对于字符串中的每个字符，我们通过该字符的 ASCII 码值找到其在数组中对应的出现次数；如果这个次数为 1，说明该字符在字符串中只出现了一次，且由于我们是按照字符串的顺序进行遍历的，所以它就是第一个不重复的字符；此时，我们返回该字符在字符串中的索引 i 即可。

2.2.代码实现

时间复杂度O(N)；空间复杂度O(1).

class Solution 
{
public://该函数用于找到字符串 s 中第一个不重复字符的索引//参数 s 是待处理的字符串int firstUniqChar(string s){//1.初始化字符计数数组//该数组用于统计每个字符出现的次数.//由于 ASCII 编码表只有 128 个字符，所以开辟一个大小为 128 的整型数组 countA//数组的下标对应字符的 ASCII 码值，数组元素用于记录该字符出现的次数.int countA[128] = { 0 };//获取字符串 s 的长度int size = s.size();//统计每个字符出现的次数//遍历字符串 s 中的每个字符for (int i = 0; i < size; ++i){//将字符 s[i] 对应的 ASCII 码值作为数组 countA 的下标, 并将该下标对应的//数组元素值加 1,表示该字符出现的次数加 1.这样，countA 数组中每个元素的值//就代表了对应字符在字符串中出现的次数。countA[s[i]] += 1;}//3.查找第一个只出现一次的字符//按照字符在字符串中的次序从前往后找只出现一次的字符for (int i = 0; i < size; ++i){//检查当前字符 s[i] 出现的次数是否为 1. 如果是，说明该字符只出现了一次，//此时返回该 字符的在字符串中的索引 i .if (1 == countA[s[i]])return i;}//如果遍历完整个字符串都没有找到只出现一次的字符，说明字符串中不存在//只出现一次的字符，返回 -1return -1;}
};

3.思路3

3.1.思路描述

该算法的核心思路是利用数组来统计字符串中每个小写字母的出现次数，然后通过再次遍历字符串，根据统计结果找出第一个仅出现一次的字符。由于题目限定字符串仅包含小写字母，而小写字母共有 26 个，所以可以使用一个大小为 26 的数组来记录每个字母的出现频次。通过字符与 'a' 的 ASCII 码差值，能够将每个小写字母映射到数组的一个特定位置，从而方便地进行计数和查找操作。
注意：思路3和思路2是类似的，只是写法不同而已。

3.2.代码实现

#include<iostream>
#include<string>
using namespace std;class Solution
{
public://该函数用于找到字符串 s 中第一个不重复字符的索引//参数 s 是待处理的字符串int firstUniqChar(string s){//1. 初始化计数数组//由于题目假设字符串仅包含小写字母，小写字母共 26 个，所以创建一个//大小为 26 的整型数组 countA，用于统计每个小写字母的出现次数.//数组的每个元素初始化为 0int countA[26] = { 0 };//2. 统计每个小写字母出现的次数//遍历字符串 s 中的每个字符//这里使用范围 for 循环，ch 依次代表字符串 s 中的每个字符for (auto ch : s){//字符 'a' 的 ASCII 码值为 97，'b' 为 98，以此类推//ch - 'a' 可以得到该字符在字母表中的相对位置（从 0 开始）//例如，若 ch 为 'a'，ch - 'a' 结果为 0，对应 countA 数组的第一个元素//每次遇到该字符，将其对应的数组元素值加 1，实现计数功能countA[ch - 'a']++;}//3. 查找第一个只出现一次的字符//再次遍历字符串 s，这次使用普通的 for 循环，i 为字符的索引for (int i = 0; i < s.size(); ++i)//注意：由于这里要返回字符的索引，所以这里不用范围for遍历字符串。{//同样通过 s[i] - 'a' 得到当前字符在字母表中的相对位置,检查该位置对应的 countA 数组元素的值是否为 1,//如果为 1，说明该字符在字符串中只出现了一次，且由于是按顺序遍历字符串，所以第一个满足条件的字符就是//第一个不重复的字符，则此时返回该字符的索引 i .if (1 == countA[s[i] - 'a'])return i;}//4. 处理没有唯一字符的情况//如果遍历完整个字符串都没有找到只出现一次的字符，说明字符串中不存在不重复的字符，返回 -1.return -1;}
};

4.总结

(1)思路2和思路3的解题思路有点类似于计算排序。而这里可以使用计算排序思想是因为字母的类型char也是属于整形数据，而计算排序思想只能适用于整形数据。

练习3：字符串里面最后一个单词的长度

字符串最后一个单词的长度_牛客题霸_牛客网

1.注意事项

(1)在 C++ 中，std::getline 常与 while 循环结合使用，以持续从输入流（如标准输入 std::cin 或文件输入流 std::ifstream）中读取多行数据。下面详细介绍不使用 while 循调用 std::getline 时的结束条件判断方法。

从标准输入读取多行数据：当从标准输入（键盘）读取多行数据时，可通过判断 std::getline 的返回值来确定是否继续读取。std::getline 返回输入流对象的引用，在布尔语境下，若读取成功则为 true，遇到文件结束符（EOF）或发生错误时为 false。在 Windows 系统中，可通过按下 Ctrl + Z 再按回车键来发送 EOF；在 Unix/Linux 系统中，按下 Ctrl + D 即可。

#include<string>
#include<iostream>
using namespace std;int main()
{string line;while (getline(cin, line)){//处理读取到的每一行数据cout << "你输入的行是: " << line << endl;}cout << "输入结束。" << endl;return 0;
}

在上述代码中，while (getline(cin, line)) 这个条件会在每次调用 getline 后进行判断。只要读取成功，循环就会继续执行；当遇到 EOF 时，getline 的返回值在布尔语境下为 false，循环终止。

(2)cin、scanf和getline在读取带有空格字符串时存在明显区别，具体如下：

注意：当我们通过标准输入流读取数据时，cin 和 scanf 会默认以空格、制表符或换行符作为分隔符来区分多个输入项。

读取方式

cin：cin是 C++ 中用于输入的流对象，它在读取字符串时，会将空格、制表符和换行符作为分隔符，遇到这些字符就会停止读取，只读取到分隔符之前的内容。例如，当输入 “Hello World” 时，cin只会读取到 “Hello”，“World” 则留在输入缓冲区中等待后续读取操作。
scanf：scanf是 C 语言中的标准输入函数，在使用%s格式控制符读取字符串时，也会把空格、制表符和换行符当作分隔符，它会跳过前导的空白字符，从第一个非空白字符开始读取，遇到空白字符就停止。例如，对于输入 “Hello World”，scanf会忽略开头的空格，读取到 “Hello”，同样 “World” 会留在输入缓冲区。
getline：getline是 C++ 中用于读取一行字符串的函数，它会从输入流中读取字符，直到遇到换行符为止，并且会将换行符从输入缓冲区中移除，在读取过程中，空格会被正常读取，作为字符串的一部分。比如，输入 “Hello World”，getline会将整个 “Hello World” 作为一个完整的字符串读取进来。

对输入缓冲区的处理

cin：当cin读取完一个字符串后，分隔符（空格、制表符或换行符）会留在输入缓冲区中，等待下一次输入操作。如果下一次输入操作是getline等需要读取整行的函数，可能会因为缓冲区中的分隔符导致问题，比如getline可能会读取到一个空字符串。
scanf：与cin类似，scanf在读取字符串时遇到分隔符停止后，分隔符也会留在输入缓冲区中，可能会影响后续的输入操作。
getline：getline会读取并移除输入缓冲区中的换行符，使得输入缓冲区在读取完一行后处于一个相对 “干净” 的状态，不会留下换行符干扰下一次输入操作，但如果输入中存在多个连续的换行符，后续的getline调用可能会受到影响。

注意事项：

若在 cin 或 scanf 之后立即调用 getline，可能因输入缓冲区中残留的换行符导致 getline 直接读取空字符串。此时需通过 cin.ignore() 清除缓冲区中的残留换行符。
getline 的默认分隔符是换行符，若需自定义分隔符（如逗号），可使用 getline(cin, str, ',') 形式

(3)当我们想从标准输入流读取字符串时，若字符串中含有空格字符，则不能直接使用cin读取，因为cin会在遇到空格、制表符或换行符时停止读取，仅能读取到第一个分隔符前的内容。此时应使用getline函数来读取包含空格的完整字符串。getline函数会读取从当前位置到换行符（包括换行符）的所有字符，并将换行符从输入缓冲区中移除。注意：若在cin之后立即使用getline，可能因cin未读取换行符导致getline直接读取空字符串。此时需先通过cin.ignore()清除输入缓冲区中的残留换行符。

案例：分别使用string类成员函数cin、C++库提供的getline函数从标准输入流中读取含有空格字符的字符

结论：当从标准输入流输入的字符串含有空格字符时不能使用cin读取，而是必须使用getline读取带空格的字符串。

2.思路描述

该代码的核心思路是利用字符串处理函数找到句子中最后一个空格的位置，然后通过字符串的总长度和最后一个空格的位置来计算最后一个单词的长度。具体来说，使用 rfind 函数从字符串的末尾开始查找最后一个空格，因为最后一个单词是从最后一个空格之后开始到字符串末尾结束的，所以用字符串的总长度减去最后一个空格的位置再减 1（减去空格本身）就可以得到最后一个单词的长度。

3.代码实现

3.1.写法1

#include<string>
#include<iostream>
using namespace std;int main()
{string line; // 定义一个字符串变量 line，用于存储输入的一行句子//不要使用 cin >> line，因为 cin >> line 遇到空格就会停止读取输入//这里使用 getline(cin, line) 来读取一整行输入，直到遇到换行符为止//循环会不断读取输入，直到输入结束（例如在命令行中按下 Ctrl+Z）while (getline(cin, line)){//使用 rfind 函数从字符串的末尾开始查找最后一个空格的位置//rfind 函数返回找到的空格的位置，如果未找到则返回 string::npossize_t pos = line.rfind(' ');//计算最后一个单词的长度//line.size() 是整个字符串的长度//pos 是最后一个空格的位置//line.size() - pos - 1 就是最后一个单词的长度cout << line.size() - pos - 1 << endl;}return 0;  
}

3.2.写法2

#include <string>  
#include <iostream>  
using namespace std;  int main()
{string str; // 定义一个 string 类型的变量 str，用于存储输入的句子//使用 getline 函数从标准输入读取一行内容，并将其存储到 str 中//getline 函数会读取整行，直到遇到换行符，这样可以处理包含空格的句子getline(cin, str);//使用 rfind 函数从字符串的末尾开始查找最后一个空格的位置//rfind 函数返回找到的空格的位置，如果未找到则返回 string::npossize_t pos = str.rfind(' ');//检查是否找到了空格if (pos != string::npos){//如果找到了空格，说明句子中至少有两个单词//最后一个单词的长度等于字符串的总长度减去最后一个空格的位置再减 1（减去空格本身）cout << str.size() - pos - 1 << endl;}else{//如果没有找到空格，说明句子中只有一个单词//此时最后一个单词（也就是唯一的单词）的长度就是字符串的总长度cout << str.size() << endl;}return 0;  
}

练习4：验证一个字符串是否是回文串

125. 验证回文串 - 力扣（LeetCode）

1.思路描述

该算法的核心思路是先对字符串进行预处理，将所有小写字母转换为大写字母，然后使用双指针法，分别从字符串的首尾开始向中间移动，在移动过程中跳过非字母数字字符，比较对应位置的字符是否相等。如果在整个过程中都没有发现不相等的字符，则说明该字符串是回文串；否则，不是回文串。

2.代码实现

#include <string>
#include <iostream>
using namespace std;class Solution 
{
public://判断字符是否为字母或数字的函数//参数 ch 是待判断的字符bool isLetterOrNumber(char ch){//若字符是数字（ASCII码范围 '0' 到 '9'）//或者是小写字母（ASCII码范围 'a' 到 'z'）//或者是大写字母（ASCII码范围 'A' 到 'Z'），则返回 truereturn (ch >= '0' && ch <= '9')|| (ch >= 'a' && ch <= 'z')|| (ch >= 'A' && ch <= 'Z');}//判断字符串 s 是否为回文串的函数bool isPalindrome(string s) {//遍历字符串 s 中的每个字符for (auto& ch : s){//如果字符是小写字母，将小写字母转换为大写字母，因为 'a' 到 'A' 的 ASCII 码差值为 32，所以减去 32.if (ch >= 'a' && ch <= 'z'){ch -= 32;}}//初始化两个指针，begin 指向字符串的起始位置int begin = 0;//end 指向字符串的末尾位置int end = s.size() - 1;//当begin 小于 end 时，继续进行比较while (begin < end){//begin指针从左向右移动，跳过非字母数字字符while (begin < end && !isLetterOrNumber(s[begin]))++begin;//end指针从右向左移动，跳过非字母数字字符while (begin < end && !isLetterOrNumber(s[end]))--end;//如果 begin 和 end 指针指向的字符不相等,说明该字符串不是回文串，返回 falseif (s[begin] != s[end]){return false;}else{//若相等，将 begin 指针右移一位++begin;//end 指针左移一位--end;}}//若循环结束都没有发现不相等的情况，说明是回文串，返回 truereturn true;}
};

练习5：字符串相加

415. 字符串相加 - 力扣（LeetCode）

1.大数运算的介绍

注意：该题的本质是个大数运算。

大数运算是涉及比普通计算机整数类型所能表示的范围更大的整数的数学运算。在计算机科学中，标准的整数类型（如 int、long、long long 等）通常有固定的位数限制，例如：

int 类型通常为 32 位，可以表示的整数范围大约是 -2,147,483,648 到 2,147,483,647。
long long 类型通常为 64 位，可以表示的整数范围大约是 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,808。

当需要处理的数字超出这些范围时，就需要使用大数运算。以下是一些大数运算的例子：

大数加法：两个非常大的数相加，结果可能超出标准整数类型的表示范围。
大数减法：从一个大数中减去另一个大数，结果可能超出标准整数类型的表示范围。
大数乘法：两个非常大的数相乘，结果可能超出标准整数类型的表示范围。
大数除法：一个大数除以另一个大数，结果可能超出标准整数类型的表示范围。
大数模运算：一个大数对另一个大数取模，结果可能超出标准整数类型的表示范围。

为了处理大数运算，通常有以下几种方法：

字符串表示：使用字符串或字符数组来表示大数，然后实现字符串版本的加法、减法、乘法等运算。
数组表示：使用整数数组，每个数组元素存储大数的一部分，通常是按位或按段（例如，每10位一段）。
库函数：使用专门的库来处理大数运算，如 GMP（GNU Multiple Precision Arithmetic Library）。

在编程中，大数运算通常用于密码学、科学计算、金融计算等领域，这些领域经常需要精确地处理非常大的数字。

2.思路分析

注意事项：在处理字符串数字相加的题目时，不能简单地将字符串转换为整形后再进行相加，然后把相加结果转换回字符串。这是因为整形类型在表示数据大小时是有范围限制。当遇到两个非常大的数字以字符串形式给出，若将它们转换为整形进行加法运算，一旦数值超出整形能够表达的范围，就会引发溢出问题。溢出后，程序得到的计算结果将不再是正确的两数之和，而是一个错误的数值，这与我们期望的计算结果不符，从而导致程序出现逻辑错误。所以，在这种情况下，需要采用其他合适的算法，如模拟人工加法的方式来处理字符串数字相加的问题，以避免因整形数据范围限制而产生的溢出问题。

算法思想：本题只需要模拟两个整数「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是如下图将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位。因此我们只要将这个过程用代码写出来即可。

2.1.思路1：使用Insert函数进行头插。不考虑扩容带来的性能消耗。

(1)思路描述

该算法的核心思路是模拟手工加法的过程。从两个字符串的末尾开始，逐位相加，同时考虑进位。对于每一位，将两个字符串对应位置的数字以及前一位的进位相加，得到当前位的和。然后计算新的进位和当前位保留的数字，将当前位的结果插入到结果字符串的开头。最后，如果还有进位，将进位插入到结果字符串的开头。

(2)代码实现

注意事项：

在模拟手工加法过程中：在手工进行两个整数相加时，若两个数的位数不同，位数少的数高位会用 0 补齐。例如计算 123 + 45 时，会把 45 看成 045 再与 123 相加。代码中通过将超出范围的 val1 或 val2 设置为 0，来模拟这种高位补 0 的操作，保证加法运算能正确进行。
在处理不同长度的字符串时：当两个字符串 num1 和 num2 长度不同时，在相加过程中，较短字符串会先遍历完。比如 num1 = "123"，num2 = "45"，当遍历到 num2 的末尾时，end2 会变为 -1 超出范围，此时将 val2 设置为 0，就可以继续和 num1 剩余的位相加，即相当于在 num2 高位补 0 后继续参与运算。
在进行加法运算时一定要把遍历到的字符转换为数字：在进行加法运算时，我们需要对数字进行操作，而不是字符本身。在 C++ 中，字符在内存中以 ASCII 码的形式存储，字符 '0' 到 '9' 的 ASCII 码是连续的。通过将字符减去 '0'，可以将字符转换为对应的数字。例如，字符 '3' 的 ASCII 码减去字符 '0' 的 ASCII 码，结果就是数字 3。

#include <string>class Solution 
{
public://该函数用于实现两个字符串形式的非负整数相加，并返回相加结果的字符串形式string addStrings(string num1, string num2) {//end1 指向 num1 字符串的最后一个字符int end1 = num1.size() - 1;//end2 指向 num2 字符串的最后一个字符int end2 = num2.size() - 1;//next 用于记录进位，初始化为 0int next = 0; //strRet 用于存储最终的相加结果，初始为空字符串string strRet;//从后往前遍历字符串//只要 end1 和 end2 其中一个还未遍历完对应字符串，就继续进行相加操作。while(end1 >= 0 || end2 >= 0) {//注意：//1.当两个字符串 num1 和 num2 长度不同时，在相加过程中，较短字符串会先遍历完。//比如 num1 = "123"，num2 = "45"，当遍历到 num2 的末尾时，end2 会变为 -1 超出范围，//此时将 val2 设置为 0，就可以继续和 num1 剩余的位相加，即相当于在 num2 高位补 0 后继续参与运算。//2.在进行加法运算时，我们需要对数字进行操作，而不是字符本身。在 C++ 中，字符在内存中以 ASCII 码的形式存储，//字符 '0' 到 '9' 的 ASCII 码是连续的。通过将字符减去 '0'，可以将字符转换为对应的数字。例如，字符 '3' 的 ASCII 码//减去字符 '0' 的 ASCII 码，结果就是数字 3。//若 end1 小于 0，表示已经遍历完 num1 ，则此时 val1 设置为 0，就可以继续和 num2 剩余的位相加，//即相当于在 num1 高位补 0 后继续参与运算。//若 end1 大于等于 0，说明 num1 还有字符未处理，则通过 num1[end1] - '0' 将该字符转换为对应的数字int val1 = end1 >= 0 ? num1[end1] - '0' : 0;//若 end2 小于 0，表示已经遍历完 num2 ，则此时 val2 设置为 0，就可以继续和 num1 剩余的位相加，//即相当于在 num2 高位补 0 后继续参与运算。//若 end2 大于等于 0，说明 num2 还有字符未处理，则通过 num2[end2] - '0' 将该字符转换为对应的数字int val2 = end2 >= 0 ? num2[end2] - '0' : 0;//计算当前位的和：当前位的数字相加val1 + val2，再加上之前的进位 next.int ret = val1 + val2 + next;//计算新的进位：更新进位，通过 ret / 10 得到.next = ret / 10;//计算当前位相加后保留的数字，取模 10 得到的余数就是当前位的结果ret = ret % 10;//将当前位的结果转换为字符并插入到结果字符串 strRet 的开头.//这里 '0'+ret 是将数字转换为对应的字符。strRet.insert(0, 1, '0'+ret);//移动 num1 的指针到前一个字符--end1;//移动 num2 的指针到前一个字符--end2;}//当 while 循环结束后，检查进位 next 是否为 1。如果为 1，说明最后还有进位未处理，//需要在结果字符串的开头插入字符 '1' 来完成进位。if(next == 1)//将进位 1 转换为字符 '1' 插入到结果字符串的开头strRet.insert(0, 1, '1');//返回相加后的结果字符串return strRet;}
};

复杂度分析

时间复杂度：O(max(m,n))，其中 m 和 n 分别是 num1 和 num2 的长度。因为需要从最低位开始逐位相加，最多需要遍历较长的那个字符串。
空间复杂度：O(max(m,n))，主要用于存储最终的相加结果字符串。

2.2.思路2：使用operator+=函数尾插完后，再使用reverse函数逆序。为了防止在执行插入操作时扩容带来的性能消耗，则在进行插入操作之前使用reserve来提取开空间来避免扩容。

(1)思路描述

该算法模拟了我们手动进行加法运算的过程。从两个字符串表示的数字的最低位（即字符串的最后一个字符）开始，逐位相加，同时考虑每一步相加产生的进位。将每一位相加的结果逐步组合成一个新的字符串，最后处理可能剩余的进位，再将结果字符串反转成正确的顺序，得到最终的相加结果。

(2)`reserve` 函数预先开空间的作用

代码里使用 reserve 函数预先为字符串 strRet 分配空间，主要是为了优化性能，下面从几个方面详细解释这样做的原因：

①避免频繁的内存重新分配

std::string 是一个动态数组，当向 std::string 中添加字符时，如果当前分配的内存空间不足以容纳新添加的字符，std::string 会自动进行内存重新分配。具体过程如下：

分配一块更大的内存区域。
将原字符串中的内容复制到新的内存区域。
释放原来的内存区域。

这种内存重新分配操作的开销是比较大的，尤其是当需要多次添加字符时，频繁的内存重新分配会导致性能显著下降。例如，在字符串长度不断增长的过程中，每次内存重新分配可能会使内存空间翻倍，这不仅涉及到大量的数据复制，还可能会造成内存碎片。

②提高程序的运行效率

通过 reserve 函数，我们可以预先估计最终结果字符串的最大可能长度，并一次性分配足够的内存空间。在 addStrings 函数中，结果字符串的最大长度为较长字符串的长度加 1（考虑可能产生的进位），所以使用以下代码进行内存预分配：

strRet.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);

这样，在后续向 strRet 中追加字符的过程中，由于已经有了足够的内存空间，就不会再发生内存重新分配的情况，从而避免了数据复制和内存释放等开销，提高了程序的运行效率。

(3)代码实现

#include <string>
#include <algorithm>//引入 reverse 函数所需的头文件class Solution 
{
public://该函数用于实现两个字符串形式的非负整数相加，并返回相加结果的字符串形式string addStrings(string num1, string num2) {//end1 指向 num1 字符串的最后一个字符，用于从后往前遍历 num1int end1 = num1.size() - 1;//end2 指向 num2 字符串的最后一个字符，用于从后往前遍历 num2int end2 = num2.size() - 1;//next 用于记录加法过程中的进位，初始化为 0int next = 0; //strRet 用于存储最终的相加结果，初始为空字符串string strRet;//预先为 strRet 分配足够的内存空间//结果字符串的长度最大为较长字符串的长度加 1（考虑可能产生的进位）strRet.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1 );//开始逐位相加，只要 end1 和 end2 其中一个还未遍历完对应字符串，就继续进行相加操作。while(end1 >= 0 || end2 >= 0) {//若 end1 小于 0，表示已经遍历完 num1 ，则此时 val1 设置为 0，就可以继续和 num2 剩余的位相加，//即相当于在 num1 高位补 0 后继续参与运算。//若 end1 大于等于 0，说明 num1 还有字符未处理，则通过 num1[end1] - '0' 将该字符转换为对应的数字int val1 = end1 >= 0 ? num1[end1] - '0' : 0;//若 end2 小于 0，表示已经遍历完 num2 ，则此时 val2 设置为 0，就可以继续和 num1 剩余的位相加，//即相当于在 num2 高位补 0 后继续参与运算。//若 end2 大于等于 0，说明 num2 还有字符未处理，则通过 num2[end2] - '0' 将该字符转换为对应的数字int val2 = end2 >= 0 ? num2[end2] - '0' : 0;//计算当前位的和：当前位的数字相加val1 + val2，再加上之前的进位 next.int ret = val1 + val2 + next;//计算新的进位：更新进位，通过 ret / 10 得到.next = ret / 10;//计算当前位相加后保留的数字，取模 10 得到的余数就是当前位的结果ret = ret % 10;//将当前位的结果转换为字符并追加到结果字符串 strRet 的末尾strRet += ('0'+ret);//移动 num1 的指针到前一个字符--end1;//移动 num2 的指针到前一个字符--end2;}//当 while 循环结束后，检查进位 next 是否为 1。如果为 1，说明最后还有进位未处理，//则此时直接把字符 '1' 追加到结果字符串末尾来完成进位.if(next == 1)strRet += '1';//由于之前是从后往前逐位相加并将结果追加到末尾，所以结果字符串是逆序的//使用 reverse 函数将结果字符串反转成正确的顺序reverse(strRet.begin(), strRet.end());//返回相加后的正确结果字符串return strRet;}
};

复杂度分析

时间复杂度：该算法主要进行了一次对两个字符串的遍历操作，时间复杂度为 O(max(m,n))，其中 m 和 n 分别是 num1 和 num2 的长度。另外，反转字符串的操作时间复杂度也为 O(max(m,n))，因此总体时间复杂度为。
空间复杂度：主要的额外空间是用于存储结果字符串 strRet，其长度最大为 max(m,n) + 1（考虑可能的进位），所以空间复杂度为 O(max(m,n))。

其他写法

#include <string>
#include <algorithm>class Solution 
{
public:string addStrings(string num1, string num2) {int end1 = num1.size() - 1, end2 = num2.size() - 1;int next = 0;string strRet;strRet.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);while (end1 >= 0 || end2 >= 0) {int val1 = end1 >= 0 ? num1[end1] - '0' : 0;int val2 = end2 >= 0 ? num2[end2] - '0' : 0;int ret = val1 + val2 + next;//计算当前位的和与处理进位的思路2：//判断当前相加结果是否产生进位if (ret > 9){//如果 ret > 9，说明产生了进位，将进位标记为 1next = 1; //去掉进位部分，得到当前位实际保留的数字ret -= 10; }else{//如果没有产生进位，将进位标记为 0next = 0; }strRet += ('0' + ret);--end1;--end2;}if (next == 1)strRet += '1';reverse(strRet.begin(), strRet.end());return strRet;}
};

练习6：字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

1.思路1

1.1.思路描述

如果 num1 和 num2 之一为 0，则直接返回字符串 "0"。这是因为根据乘法基本性质，任何数与 0 相乘结果必然为 0。

若 num1 和 num2 均不为 0，那么可通过模拟「竖式乘法」来算出二者乘积。具体做法为：从右往左遍历 num2（乘数），将 num2 的每一位依次与 num1（被乘数）相乘。每完成一位相乘，都会得到一个对应结果。这些结果在累加时，需注意位置关系。

由于 num2 除最低位外，其余各位与 num1 相乘的结果在最终累加时，需在末尾补上相应数量的 0。例如，num2 的倒数第二位与 num1 相乘的结果，在累加时需在末尾补一个 0；倒数第三位与 num1 相乘的结果，在累加时需在末尾补两个 0，依此类推。这是为了模拟真实竖式乘法中，不同位相乘结果在最终累加时的正确位置。完成所有位的相乘与补零操作后，将每次得到的结果累加起来，就得到了 num1 和 num2 的乘积。

1.2.代码实现

总结：整体上，代码实现了两个字符串形式的非负整数的相加和相乘功能。

相加功能：addStrings 函数通过双指针从两个字符串的末尾开始逐位相加，处理进位，最后反转结果字符串得到正确的相加结果。
相乘功能：multiply 函数模拟竖式乘法，从 num1 的最低位开始逐位与 num2 相乘，处理进位和补零操作，将每次相乘的结果累加到最终结果中，累加过程调用 addStrings 函数。通过这种方式，避免了直接将字符串转换为整数，同时能处理大整数的乘法。

#include <string>
#include <algorithm>class Solution 
{
public://该函数用于实现两个字符串形式的非负整数相加，并返回相加结果的字符串形式string addStrings(string num1, string num2) {//end1 指向 num1 字符串的最后一个字符，用于从后往前遍历 num1int end1 = num1.size() - 1;//end2 指向 num2 字符串的最后一个字符，用于从后往前遍历 num2int end2 = num2.size() - 1;//next 用于记录加法过程中的进位，初始化为 0int next = 0; //strRet 用于存储最终的相加结果，初始为空字符串string strRet;//预先为 strRet 分配足够的内存空间//结果字符串的长度最大为较长字符串的长度加 1（考虑可能产生的进位）strRet.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1 );//开始逐位相加，只要 end1 和 end2 其中一个还未遍历完对应字符串，就继续进行相加操作。while(end1 >= 0 || end2 >= 0) {//若 end1 小于 0，表示已经遍历完 num1 ，则此时 val1 设置为 0，就可以继续和 num2 剩余的位相加，//即相当于在 num1 高位补 0 后继续参与运算。//若 end1 大于等于 0，说明 num1 还有字符未处理，则通过 num1[end1] - '0' 将该字符转换为对应的数字int val1 = end1 >= 0 ? num1[end1] - '0' : 0;//若 end2 小于 0，表示已经遍历完 num2 ，则此时 val2 设置为 0，就可以继续和 num1 剩余的位相加，//即相当于在 num2 高位补 0 后继续参与运算。//若 end2 大于等于 0，说明 num2 还有字符未处理，则通过 num2[end2] - '0' 将该字符转换为对应的数字int val2 = end2 >= 0 ? num2[end2] - '0' : 0;//计算当前位的和：当前位的数字相加val1 + val2，再加上之前的进位 next.int ret = val1 + val2 + next;//计算新的进位：更新进位，通过 ret / 10 得到.next = ret / 10;//计算当前位相加后保留的数字，取模 10 得到的余数就是当前位的结果ret = ret % 10;//将当前位的结果转换为字符并追加到结果字符串 strRet 的末尾strRet += ('0'+ret);//移动 num1 的指针到前一个字符--end1;//移动 num2 的指针到前一个字符--end2;}//当 while 循环结束后，检查进位 next 是否为 1。如果为 1，说明最后还有进位未处理，//则此时直接把字符 '1' 追加到结果字符串末尾来完成进位.if(next == 1)strRet += '1';//由于之前是从后往前逐位相加并将结果追加到末尾，所以结果字符串是逆序的//使用 reverse 函数将结果字符串反转成正确的顺序reverse(strRet.begin(), strRet.end());//返回相加后的正确结果字符串return strRet;}//实现两个字符串形式的非负整数相乘的函数string multiply(string num1, string num2) {//如果 num1 或 num2 为 其中一个数为"0"，则直接返回 "0"，//因为任何数与 0 相乘都为 0。if(num1 == "0" || num2 == "0")return "0";//初始化指针 end1 指向 num1 字符串的最后一个字符int end1 = num1.size() - 1;//初始化指针 end2 指向 num2 字符串的最后一个字符int end2 = num2.size() - 1;//strRet 初始化为 "0"，用于存储每次相乘结果的累加和。string strRet = "0"; //最终结果字符串//遍历 num1 的每一位，从 num1 的最低位开始逐位相乘while(end1 >= 0){//用于记录乘法过程中的进位，初始化为 0int next = 0; //tmpRet 用于存储 num1 当前位与 num2 相乘的临时结果。string tmpRet;//补零操作：根据 num1 当前位的位置，在 tmpRet 前面补零，以保证结果的位置正确。//例如，num1 的倒数第二位与 num2 相乘的结果需要在末尾补一个零。for(int j = 0; j < num1.size() - 1 - end1; j++)tmpRet += '0';//获取 num1 当前位对应的数字int val1 = num1[end1] - '0';//遍历 num2 的每一位，用 num1 当前位的数字乘以 num2 的每一位for(int i = end2; i >= 0; i--){//获取 num2 当前位的数字int val2 = num2[i] - '0'; //计算当前位相乘的结果，包含进位int ret = val1 * val2 + next;//计算新的进位next = ret / 10;//计算当前位保留的数字ret = ret % 10;//将当前位结果转换为字符添加到 tmpRet 末尾tmpRet += (ret + '0');}//若最后还有进位，添加到临时结果字符串 tmpRet 末尾if(next > 0) tmpRet += (next + '0');//由于临时结果是逆序添加的，，需要将其逆序，得到正确的顺序。reverse(tmpRet.begin(), tmpRet.end());//将当前位相乘的结果累加到最终结果中strRet = addStrings(strRet, tmpRet);//移动 num1 的指针到前一个字符end1--;}//最终返回累加得到的结果 strRetreturn strRet;}
};

练习7：翻转字符串II：区间部分翻转

541. 反转字符串 II - 力扣（LeetCode）

1.思路

反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。

2.代码实现

#include <string>
#include <algorithm>
using namespace std;class Solution 
{
public://该函数用于按照特定规则反转字符串 s 中的部分子串string reverseStr(string s, int k) {//获取字符串 s 的长度int n = s.size();//从字符串开头开始，以 2 * k 为步长进行遍历for (int i = 0; i < n; i += 2 * k) {//反转从 s.begin() + i 开始，长度为 k 或者剩余长度（如果不足 k）的子串//min(i + k, n) 用于确定反转的结束位置，同时确保不会越界//如果 i + k 小于等于 n，说明有足够的字符可以反转 k 个，反转到 i + k 位置//如果 i + k 大于 n，说明剩余字符不足 k 个，反转到字符串末尾 n 位置reverse(s.begin() + i, s.begin() + min(i + k, n));}//返回处理后的字符串return s;}
};

练习8：翻转字符串III：翻转字符串中的单词

557. 反转字符串中的单词 III - 力扣（LeetCode）

注意事项：在使用std库提供的reverse逆序函数时，要传左闭右开的迭代器区间给reverse。

1.思路描述

该思路的核心在于识别字符串中的每个单词，并对每个单词的字符顺序进行反转。通过查找空格来确定单词的边界，利用 reverse 函数对每个单词进行反转操作。

2.代码实现

代码整体思路：该算法的核心思想是通过查找字符串中的空格来确定每个单词的边界，然后对每个单词所在的子字符串进行反转操作。具体步骤是先检查字符串是否为空，若不为空则从字符串开头开始查找空格，以空格为分隔符确定每个单词的范围，对每个单词进行反转，最后处理最后一个单词（若最后没有空格）。

#include <string>
#include <algorithm>class Solution 
{
public://该函数用于反转字符串 s 中每个单词的字符顺序，同时保留空格和单词的初始顺序string reverseWords(string s) {//检查字符串 s 是否为空，如果为空则直接返回该字符串if (s.empty())return s;//查找字符串 s 中第一个空格的位置size_t pos = s.find(' ');//记录当前单词的起始位置，初始化为字符串的开头int start = 0;//当能找到空格时，继续循环处理单词while (pos != string::npos) {//反转从当前单词起始位置到空格位置之前的字符，也就是反转当前找到的这个单词reverse(s.begin() + start, s.begin() + pos);//更新下一个单词的起始位置为当前空格位置的下一个字符start = pos + 1;//从新的起始位置开始查找下一个空格的位置pos = s.find(' ', start);}//如果找不到空格了，说明处理到了最后一个单词if (pos == string::npos)//反转从最后一个单词起始位置到字符串末尾的字符，即反转最后一个单词reverse(s.begin() + start, s.begin() + s.size());//返回处理好的字符串return s;}
};

查看全文

http://www.mrgr.cn/news/92589.html