C++优选算法十一 字符串
C++ 标准库中的 std::string 是一个用于表示和操作字符串的类。它提供了丰富的成员函数和运算符，使得字符串的处理变得既方便又高效。以下是一些关于 std::string 的关键特性和用法：
1. 引入头文件
要使用 std::string，你需要包含 <string> 头文件：
#include <string> |
2. 声明和初始化
你可以通过多种方式声明和初始化 std::string 对象：
std::string str1; // 声明一个空字符串 | |
std::string str2("Hello"); // 使用C风格字符串初始化 | |
std::string str3 = "World"; // 使用字符串字面量初始化 | |
std::string str4(str2); // 使用另一个std::string对象初始化 | |
std::string str5(5, 'c'); // 使用字符和重复次数初始化，得到 "ccccc" |
3. 字符串操作
std::string 提供了许多成员函数来操作字符串，例如：
-
长度：
size_t len = str.length(); // 或 str.size() -
访问字符：
char ch = str[0]; // 访问第一个字符，注意越界检查char ch2 = str.at(0); // 访问第一个字符，越界时会抛出 std::out_of_range 异常 -
拼接字符串：
str += " "; // 追加空格str += "World"; // 追加字符串str.append("!!!"); // 追加字符串 -
子字符串：
std::string substr = str.substr(1, 3); // 从索引1开始，长度为3的子字符串 -
查找：
size_t pos = str.find("World"); // 查找子字符串的位置if (pos != std::string::npos) {// 找到} -
替换：
std::string newStr = str.replace(0, 5, "Hi"); // 替换前5个字符为 "Hi" -
插入：
str.insert(1, "abc"); // 在索引1处插入 "abc" -
删除：
str.erase(1, 3); // 从索引1开始删除3个字符str.pop_back(); // 删除最后一个字符
4. 字符串比较
std::string 支持多种比较运算符：
if (str1 == str2) { | |
// 相等 | |
} | |
if (str1 != str2) { | |
// 不相等 | |
} | |
if (str1 < str2) { | |
// 小于 | |
} | |
if (str1 <= str2) { | |
// 小于等于 | |
} | |
if (str1 > str2) { | |
// 大于 | |
} | |
if (str1 >= str2) { | |
// 大于等于 | |
} |
5. 字符串流
你可以使用 std::stringstream 将字符串与其他数据类型进行转换：
#include <sstream> | |
int num; | |
std::string str = "12345"; | |
std::stringstream ss(str); | |
ss >> num; // 将字符串转换为整数 |
6. 非成员函数
C++ 标准库还提供了一些非成员函数来操作 std::string，例如 std::getline 用于从输入流中读取一行：
std::string line; | |
std::getline(std::cin, line); // 从标准输入读取一行 |
7. 性能注意事项
std::string 的实现通常基于动态数组（如 std::vector），因此它在大多数情况下性能很好，但在频繁进行拼接操作时，可能会因为内存重新分配而性能下降。在这种情况下，可以考虑使用 std::ostringstream 或预先分配足够的空间。
总结
std::string 是 C++ 标准库中非常强大且灵活的字符串处理类，它提供了丰富的成员函数和运算符，使得字符串的操作变得简单而高效。通过合理使用这些功能，你可以高效地处理各种字符串相关的任务。
8.示例题目
1.最长公共前缀. - 力扣（LeetCode）
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
解法:
算法思路:
解法一(两两比较):
然后拿这个最长公共前缀依次与后面的字符串比较，这样就我们可以先找出前两个的最长公共前缀，可以找出所有字符串的最长公共前缀。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
//解法一 两两比较
string ret=strs[0];
for(int i=0;i<strs.size();i++)
{
ret=findCommon(ret,strs[i]);
}
return ret;
}
string findCommon(string&s1,string& s2)
{
int i=0;
while(i<min(s1.size(),s2.size())&&s1[i]==s2[i])
i++;
return substr(0,i);//截取子串
}
};解法二(统一比较)
题目要求多个字符串的公共前缀，我们可以逐位比较这些字符串，哪一位出现了不同，就在哪一位截止。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
if(strs.size()==1)
return strs[0];
string str;
for(int i=0;i<strs[0].size();i++)
{
for(int j=0;j<strs.size()-1;j++)
{
if(strs[j][i]!=strs[j+1][i])
{
return strs[0].substr(0,i);
}
}
str+=strs[0][i];
}
return str;
}
};2.最长回文子串. - 力扣（LeetCode）
给你一个字符串 s，找到 s 中最长的 回文子串 。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
解法(中心扩散)
算法思路:
枚举每一个可能的子串非常费时，有没有比较简单一点的方法呢?
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。如此这样去除，一直除到长度小于等于2时呢?长度为1的，自身与自身就构成回文;而长度为2的，就要判断这两个字符是否相等了。
从这个性质可以反推出来，从回文串的中心开始，往左读和往右读也是一样的。那么，是否可以枚举回文串的中心呢?
从中心向两边扩展，如果两边的字母相同，我们就可以继续扩展;如果不同，我们就停止扩展。这样只需要一层 for 循环，我们就可以完成先前两层 for 循环的工作量。
class Solution {
public:
string longestPalindrome(string s)
{
int begin=0,len=0,n=s.size();
for(int i=0;i<n;i++)//固定所有的中心点
{
//先扩展奇数长度的子串
int left=i,right=i;
while(left>=0&&right<n&&s[left]==s[right])
{
left--;
right++;
}
if(right-left-1>len)
{
begin=left+1;
len=right-left-1;
}
//扩展偶数长度
left=i,right=i+1;
while(left>=0&&right<n&&s[left]==s[right])
{
left--;
right++;
}
if(right-left-1>len)
{
begin=left+1;
len=right-left-1;
}
}
return s.substr(begin,len);
}
};3.二进制求和. - 力扣（LeetCode）
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
解法(模拟十进制的大数相加的过程)
算法思路:
模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和，我们不是逢十进一，而是逢二进一。
class Solution {
public:
string addBinary(string a, string b)
{
string str;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int i=0;
int tmp=0;
int num=0;
while(i<a.size()&&i<b.size())
{
num=(a[i]-'0')+(b[i]-'0')+tmp;
tmp=num/2;
str+=to_string(num%2);
num=0;
i++;
}
while(i<a.size())
{
num=(a[i]-'0')+tmp;
tmp=num/2;
str+=to_string(num%2);
num=0;
i++;
}
while(i<b.size())
{
num=(b[i]-'0')+tmp;
tmp=num/2;
str+=to_string(num%2);
num=0;
i++;
}
if(tmp!=0)
str+=to_string(tmp);
reverse(str.begin(),str.end());
return str;
}
};4.字符串相乘. - 力扣（LeetCode）
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
解法(无进位相乘然后相加，最后处理进位)
算法思路:
整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性，我们选择一种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。如下图:
class Solution {
public:
string multiply(string num1, string num2)
{
//解法：无进位相乘后相加，然后处理进位
int n=num1.size();
int m=num2.size();
if(num1=="0")
return "0";
if(num2=="0")
return "0";
vector<int> tmp(m+n-1);
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
//1.无进位相乘后相加
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');
}
}
//2.处理进位
string str;
int t=0;
for(int i=0;i<m+n-1;i++)
{
str += to_string((tmp[i]+t) % 10);
t = (tmp[i] + t) / 10;
}
if(t!=0)
str+=to_string(t);
//处理前导零
while(str.size()>1&&str.back()=='0')
str.pop_back();
reverse(str.begin(),str.end());
return str;
}
};原文地址：https://blog.csdn.net/m0_74826386/article/details/143632100
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！