文章目录
◆ 博主： @此生决int
分享编程知识！深挖底层原理！持续原创更新！热门专栏：
深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++
算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线
快速复习系列：知识梳理、查漏补缺，考前冲刺必备
Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试
📌 本系列知识点前后关联较强，建议按照专栏顺序阅读哦
🎯 本系列主要面向的阅读人群
1，学完 C 语言，准备系统学习 C++ 的同学
2，已经学习过 C++，希望重新梳理知识体系的同学
3，想深入理解 C++ 设计思想与底层原理，而不仅仅停留在语法层面的同学
不止教你会写代码，更带你理解代码为什么这样设计！
---上期回顾
上一篇我们主要学习了 string类，重点掌握了 string类的成员变量和函数，以及模拟实现了string类。那么今天我们就来运用一下string的相关接口，做几道经典的算法题！
字符串相关算法题
前言
本节是上一节的实践内容，主要目的是熟悉字符串相关接口的使用以及了解一些基本的与字符串相关的容易出现的算法题！
本节算法题总览
- 917. 仅仅反转字母（双指针） ⭐⭐
- 387. 字符串中的第一个唯一字符（哈希计数） ⭐
- HJ1 字符串最后一个单词的长度（字符串基础） ⭐
- 415. 字符串相加（高精度加法） ⭐⭐
- 541. 反转字符串 II（字符串模拟 + 区间反转） ⭐⭐
- 557. 反转字符串中的单词 III（字符串模拟） ⭐⭐
- 43. 字符串相乘（高精度乘法） ⭐⭐⭐⭐
1，仅仅反转字母⭐⭐
题目链接
题目描述
给定一个字符串 s，反转其中所有英文字母的位置，非字母字符保持原来的位置不变。
解题思路
使用双指针分别从字符串两端寻找字母，遇到非字母直接跳过，当左右都找到字母后交换即可，直到两个指针相遇。
解题代码
class Solution {
public:
// 判断当前字符是否为英文字母
bool islettle(char a)
{
if(a >= 'a' && a <= 'z')
return true;
if(a >= 'A' && a <= 'Z')
return true;
return false;
}
string reverseOnlyLetters(string s) {
// 双指针分别从两端寻找需要交换的字母
int left = 0, right = s.size() - 1;
while(left < right)
{
// 左指针跳过非字母
while(!islettle(s[left]) && left < right)
{
left++;
}
// 右指针跳过非字母
while(!islettle(s[right]) && left < right)
{
right--;
}
// 两侧均为字母时进行交换
swap(s[left++], s[right--]);
}
return s;
}
};
没懂？看看大神的解题代码！！
大神解题代码（也要注释）
class Solution {
public:
string reverseOnlyLetters(string s) {
int left = 0;
int right = s.size() - 1;
while(left < right)
{
// 左指针寻找字母
while(left < right && !isalpha(s[left]))
left++;
// 右指针寻找字母
while(left < right && !isalpha(s[right]))
right--;
// 找到后交换
if(left < right)
swap(s[left++], s[right--]);
}
return s;
}
};
2，字符串中的第一个唯一字符⭐⭐
题目链接
题目描述
给定一个字符串 s，找到它的第一个不重复字符，并返回它的下标；如果不存在，则返回 -1。
解题思路
使用哈希计数思想，先统计每个字母出现次数，再遍历字符串，找到第一个出现次数为 1 的字符即可。
解题代码
class Solution {
public:
int firstUniqChar(string s) {
// Bug：原代码中的 arr 没有初始化，里面存放的是随机值，
// 统计次数前必须全部初始化为 0，否则结果不正确。
int arr[26] = {0};
// 统计每个字符出现的次数
for (auto ch : s)
{
arr[ch - 'a']++;
}
// 找到第一个只出现一次的字符
for (int i = 0; i < s.size(); i++)
{
if (arr[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
没懂？看看大神的解题代码！！
大神解题代码
class Solution {
public:
int firstUniqChar(string s) {
// 记录 26 个小写字母出现的次数
vector<int> cnt(26);
// 第一次遍历：统计频率
for (char ch : s)
cnt[ch - 'a']++;
// 第二次遍历：寻找第一个只出现一次的字符
for (int i = 0; i < s.size(); i++)
{
if (cnt[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
3，字符串最后一个单词的长度⭐
题目链接
题目描述
输入一行字符串，输出最后一个单词的长度。单词之间以空格分隔。
解题思路
利用 rfind() 找到最后一个空格的位置，最后一个单词的长度就是字符串总长度减去最后一个空格后的字符数。
解题代码
#include <iostream>
using namespace std;
int main() {
string s;
getline(cin, s);
// 找到最后一个空格的位置
int p = s.rfind(' ');
// 最后一个单词长度 = 字符串长度 - 最后一个空格的位置 - 1
cout << s.size() - p - 1;
return 0;
}
// 64 位输出请用 printf("%lld")
没懂？看看大神的解题代码！！
大神解题代码
#include <iostream>
using namespace std;
int main() {
string s;
getline(cin, s);
int len = 0;
// 从后向前统计字符，遇到空格说明最后一个单词结束
for (int i = s.size() - 1; i >= 0; i--)
{
if (s[i] == ' ')
break;
len++;
}
cout << len;
return 0;
}
4，字符串相加⭐⭐
题目链接
题目描述
给定两个非负整数形式的字符串 num1 和 num2，计算它们的和，并以字符串形式返回，不能使用任何内置的大整数库。
解题思路
先将两个字符串逆置，模拟竖式加法。从最低位开始逐位相加，并维护进位，最后处理最高位进位，再将结果逆置即可。
解题代码
class Solution {
public:
string addStrings(string num1, string num2) {
// 高精度加法
// 将字符串逆置，方便从最低位开始相加
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
string ret;
int c = 0; // 当前进位
int i = 0;
// 同时处理两个字符串都存在的部分
while (i < num1.size() && i < num2.size())
{
c += (num1[i] - '0') + (num2[i] - '0');
ret += (c % 10) + '0';
c /= 10;
i++;
}
// 处理 num1 剩余的数字
while (i < num1.size())
{
c += num1[i] - '0';
ret += (c % 10) + '0';
c /= 10;
i++;
}
// 处理 num2 剩余的数字
while (i < num2.size())
{
c += num2[i] - '0';
ret += (c % 10) + '0';
c /= 10;
i++;
}
// 如果最后还有进位，需要补到最高位
if (c == 1)
ret += '1';
// 当前结果是逆序的，需要翻转回来
reverse(ret.begin(), ret.end());
return ret;
}
};
没懂？看看大神的解题代码！！
大神解题代码
class Solution {
public:
string addStrings(string num1, string num2) {
string ret;
int i = num1.size() - 1;
int j = num2.size() - 1;
int carry = 0;
// 从最低位开始模拟竖式加法
while (i >= 0 || j >= 0 || carry)
{
if (i >= 0)
carry += num1[i--] - '0';
if (j >= 0)
carry += num2[j--] - '0';
// 当前位加入答案
ret += char(carry % 10 + '0');
// 更新进位
carry /= 10;
}
// 当前结果是逆序，翻转后返回
reverse(ret.begin(), ret.end());
return ret;
}
};
5，反转字符串 II⭐⭐
题目链接
题目描述
给定一个字符串 s 和整数 k，从字符串开头开始，每计数 2k 个字符，就反转前 k 个字符。如果剩余字符不足 k 个，则全部反转；如果剩余字符在 k 到 2k 之间，则只反转前 k 个字符。
解题思路
按照题意模拟即可。每次反转一段长度为 k 的区间，然后跳过后面的 k 个字符，不断重复这一过程直到遍历完整个字符串。
解题代码
class Solution {
public:
// 反转字符串中 [left, right] 区间
void reverse(int left, int right, string& s)
{
while (left < right)
{
swap(s[left++], s[right--]);
}
}
string reverseStr(string s, int k) {
// 如果字符串长度不足 k，则全部反转
if (s.size() < k)
{
reverse(0, s.size() - 1, s);
return s;
}
int left = 0, right = k - 1;
// 第一段一定需要反转
reverse(left, right, s);
// 每次跳过一个完整的 2k 区间，处理下一段需要反转的字符
while (left < s.size())
{
left += 2 * k;
right += 2 * k;
// 最后一段不足 k 个字符时，全部反转
right = right > s.size() ? s.size() - 1 : right;
if (left < s.size())
reverse(left, right, s);
}
return s;
}
};
没懂？看看大神的解题代码！！
大神解题代码
（也要注释，并且要让人可以看懂！）
class Solution {
public:
string reverseStr(string s, int k) {
// 每隔 2k 个字符，反转前 k 个字符
for (int i = 0; i < s.size(); i += 2 * k)
{
// 当前需要反转区间的右端点
int right = min(i + k, (int)s.size());
// STL 的 reverse 左闭右开，因此直接传入 right 即可
reverse(s.begin() + i, s.begin() + right);
}
return s;
}
};
6，反转字符串中的单词 III⭐⭐
题目链接
题目描述
给定一个字符串 s，请反转字符串中每个单词的字符顺序，同时保留空格和单词的初始顺序。
解题思路
遍历字符串，遇到空格时反转当前单词。由于最后一个单词后没有空格，因此遍历结束后还需要再反转一次最后一个单词。
解题代码
class Solution {
public:
// 反转字符串中 [left, right] 区间
void my_reverse(string& s, int left, int right)
{
while (left < right)
{
swap(s[left++], s[right--]);
}
}
string reverseWords(string s) {
int left = 0, right = 0;
// 遍历字符串，遇到空格说明一个单词结束
for (; right < s.size(); right++)
{
if (s[right] == ' ')
{
// 反转当前单词
my_reverse(s, left, right - 1);
// 更新下一个单词的起始位置
left = right + 1;
}
}
// 最后一个单词后没有空格，需要单独处理
my_reverse(s, left, right - 1);
return s;
}
};
没懂？看看大神的解题代码！！
大神解题代码
class Solution {
public:
string reverseWords(string s) {
int start = 0;
// 枚举每个字符，同时让 i 可以取到 s.size()，
// 用于统一处理最后一个单词
for (int i = 0; i <= s.size(); i++)
{
// 到达空格或字符串末尾，说明一个单词结束
if (i == s.size() || s[i] == ' ')
{
int left = start;
int right = i - 1;
// 原地反转当前单词
while (left < right)
{
swap(s[left++], s[right--]);
}
// 更新下一个单词的起始位置
start = i + 1;
}
}
return s;
}
};
7，字符串相乘⭐⭐⭐⭐
题目链接
题目描述
给定两个非负整数 num1 和 num2，它们以字符串形式表示，返回它们的乘积，同样以字符串形式表示，不能使用任何内置的大整数库。
解题思路
模拟竖式乘法。先计算每一位数字相乘的结果保存到数组中，再统一处理进位，最后去除高位多余的 0，逆置得到最终答案。
解题代码
class Solution {
public:
string multiply(string num1, string num2) {
// 为了方便从个位开始计算，先将两个字符串逆置
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// arr[i] 表示第 i 位上的乘积结果（逆序存储）
vector<int> arr(num1.size() + num2.size() + 1);
// 模拟竖式乘法，先统计所有位的乘积
for (int i = 0; i < num1.size(); i++)
{
for (int j = 0; j < num2.size(); j++)
{
arr[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}
// 统一处理进位
for (int i = 0; i < arr.size() - 1; i++)
{
arr[i + 1] += arr[i] / 10;
arr[i] %= 10;
}
// 去掉最高位多余的 0，至少保留一个数字
int j = arr.size() - 1;
while (j > 0 && arr[j] == 0)
{
arr.pop_back();
j--;
}
string ret;
// 将数字数组转换为字符串
for (auto it : arr)
ret += to_string(it);
// 当前结果为逆序，需要翻转回来
reverse(ret.begin(), ret.end());
return ret;
}
};
没懂？看看大神的解题代码！！
大神解题代码
class Solution {
public:
string multiply(string num1, string num2) {
// 任意一个数为 0，结果一定为 0
if (num1 == "0" || num2 == "0")
return "0";
int n = num1.size();
int m = num2.size();
// ans[i] 表示结果第 i 位上的数字
vector<int> ans(n + m);
// 模拟竖式乘法，同时完成乘积累加和进位
for (int i = n - 1; i >= 0; i--)
{
for (int j = m - 1; j >= 0; j--)
{
int sum = (num1[i] - '0') * (num2[j] - '0') + ans[i + j + 1];
ans[i + j + 1] = sum % 10;
ans[i + j] += sum / 10;
}
}
string ret;
int i = 0;
// 去除结果前导 0
while (i < ans.size() && ans[i] == 0)
i++;
// 转换为字符串
while (i < ans.size())
{
ret += char(ans[i] + '0');
i++;
}
return ret;
}
};
下期预告
vector
结语
本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。
欢迎订阅我的深入理解 C++系列：专栏，我会结合大量示例，从「是什么、为什么、怎么实现」三个角度，带你系统学习 C++，真正理解每一个知识点背后的设计思想与底层原理。
如果你希望快速复盘知识体系、梳理重点难点，也欢迎关注我的快速复习系列：专栏，帮助你高效回顾、查漏补缺。
如果你想系统学习算法，从基础题型到常见算法模板，再到算法思想与竞赛技巧，也欢迎订阅我的 算法系列：专栏。
如果本文对你有所帮助，欢迎三连支持一下哦！
愿每一次敲下键盘，都比昨天更进一步；愿每一份坚持，都终将有所收获！
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2502_94353935/article/details/163084599
