1. C++字符串处理算法精解
作为一名长期奋战在C++开发一线的程序员,我深知字符串处理是算法面试和实际开发中的高频考点。今天我将分享8个经典的字符串算法问题及其解决方案,这些题目全部来自LeetCode和牛客网的实战题库,覆盖了字符串处理的各类典型场景。
2. 基础字符处理技巧
2.1 字母判断与大小写转换
在处理字符串问题时,经常需要判断字符是否为字母或数字。以下是两个实用的辅助函数:
cpp复制bool isLetter(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
bool isLetterOrNumber(char ch) {
return isLetter(ch) || (ch >= '0' && ch <= '9');
}
注意:在ASCII表中,大小写字母的编码不连续,中间有其他字符,因此不能简单地用
ch >= 'A' && ch <= 'z'来判断字母。
大小写转换的技巧:
cpp复制// 大写转小写
ch = ch - 'A' + 'a';
// 小写转大写
ch = ch - 'a' + 'A';
2.2 双指针法的应用
双指针是字符串处理的利器,典型应用场景包括:
- 反转字符串
- 去除特定字符
- 回文判断
- 字符串分割
基本模板:
cpp复制int left = 0, right = s.size() - 1;
while (left < right) {
// 移动左指针直到找到目标字符
while (left < right && !condition(s[left])) left++;
// 移动右指针直到找到目标字符
while (left < right && !condition(s[right])) right--;
// 处理找到的字符
process(s[left], s[right]);
left++;
right--;
}
3. 经典算法问题解析
3.1 仅反转字母(LeetCode 917)
问题描述:给定一个字符串,反转其中的所有字母,其他字符保持原位。
解决方案:
cpp复制string reverseOnlyLetters(string S) {
if(S.empty()) return S;
size_t begin = 0, end = S.size()-1;
while(begin < end) {
while(begin < end && !isLetter(S[begin])) ++begin;
while(begin < end && !isLetter(S[end])) --end;
swap(S[begin], S[end]);
++begin;
--end;
}
return S;
}
时间复杂度:O(n),每个字符最多被访问两次。
3.2 第一个唯一字符(LeetCode 387)
问题描述:找到字符串中第一个不重复的字符。
两种解法对比:
- 使用256大小的数组(处理所有ASCII字符):
cpp复制int firstUniqChar(string s) {
int count[256] = {0};
for(char c : s) count[c]++;
for(int i = 0; i < s.size(); ++i)
if(count[s[i]] == 1) return i;
return -1;
}
- 使用26大小的数组(仅处理小写字母):
cpp复制int firstUniqChar(string s) {
int count[26] = {0};
for(auto ch : s) count[ch - 'a']++;
for(size_t i = 0; i < s.size(); i++)
if(count[s[i] - 'a'] == 1) return i;
return -1;
}
性能考虑:当确定字符范围时,第二种方法更节省空间。实际开发中应根据需求选择。
3.3 最后一个单词的长度(牛客网)
问题描述:计算字符串中最后一个单词的长度。
关键点:
- 使用
rfind从后向前查找空格 - 处理没有空格的情况
- 注意字符串末尾可能有空格
解决方案:
cpp复制int lengthOfLastWord(string s) {
size_t end = s.find_last_not_of(' ');
if(end == string::npos) return 0;
size_t start = s.rfind(' ', end);
if(start == string::npos) return end + 1;
return end - start;
}
实际开发中,建议先trim字符串两端空格,再处理。
4. 字符串操作进阶
4.1 验证回文字符串(LeetCode 125)
问题描述:判断字符串在忽略大小写和非字母数字字符后是否为回文。
解决方案:
cpp复制bool isPalindrome(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
while (left < right && !isalnum(s[left])) left++;
while (left < right && !isalnum(s[right])) right--;
if (tolower(s[left]) != tolower(s[right])) return false;
left++;
right--;
}
return true;
}
优化点:
- 使用标准库函数
isalnum和tolower - 原地处理,无需额外空间
4.2 字符串相加(LeetCode 415)
问题描述:实现两个表示数字的字符串相加。
关键点:
- 从后向前逐位相加
- 处理进位
- 最后反转结果
解决方案:
cpp复制string addStrings(string num1, string num2) {
string res;
int carry = 0;
int i = num1.size() - 1, j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int n1 = i >= 0 ? num1[i--] - '0' : 0;
int n2 = j >= 0 ? num2[j--] - '0' : 0;
int sum = n1 + n2 + carry;
carry = sum / 10;
res.push_back(sum % 10 + '0');
}
reverse(res.begin(), res.end());
return res;
}
边界情况:
- 两个空字符串
- 有前导零的字符串
- 结果比两个输入都长(进位导致)
5. 字符串翻转技巧
5.1 翻转字符串II(LeetCode 541)
问题描述:每2k个字符翻转前k个,不足k个则全部翻转。
解决方案:
cpp复制string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += 2 * k) {
reverse(s.begin() + i, s.begin() + min(i + k, (int)s.size()));
}
return s;
}
关键点:
i += 2*k实现跳跃式遍历min(i + k, (int)s.size())处理边界
5.2 翻转字符串III(LeetCode 557)
问题描述:翻转字符串中每个单词的字符顺序,保持单词顺序不变。
解决方案:
cpp复制string reverseWords(string s) {
size_t start = 0;
for (size_t i = 0; i <= s.size(); ++i) {
if (i == s.size() || s[i] == ' ') {
reverse(s.begin() + start, s.begin() + i);
start = i + 1;
}
}
return s;
}
优化方向:
- 处理多个连续空格
- 原地修改减少内存分配
6. 字符串乘法实现(LeetCode 43)
问题描述:实现两个表示数字的字符串相乘。
算法思路:
- 处理乘数为0的特殊情况
- 逐位相乘并累加
- 处理进位
解决方案:
cpp复制string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
vector<int> res(num1.size() + num2.size(), 0);
for (int i = num1.size() - 1; i >= 0; i--) {
for (int j = num2.size() - 1; j >= 0; j--) {
int product = (num1[i] - '0') * (num2[j] - '0');
int sum = product + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}
string result;
for (int num : res) {
if (!(result.empty() && num == 0)) {
result.push_back(num + '0');
}
}
return result.empty() ? "0" : result;
}
复杂度分析:
- 时间复杂度:O(m*n)
- 空间复杂度:O(m+n)
7. 实战经验分享
7.1 调试技巧
-
边界测试:
- 空字符串
- 全空格字符串
- 只有一个字符的字符串
- 超大字符串(测试性能)
-
打印中间结果:
cpp复制// 在关键循环中添加调试输出
cout << "Processing at index " << i << ": " << s.substr(0, i+1) << endl;
- 单元测试框架:
cpp复制void testReverseOnlyLetters() {
assert(reverseOnlyLetters("ab-cd") == "dc-ba");
assert(reverseOnlyLetters("a-bC-dEf-ghIj") == "j-Ih-gfE-dCba");
assert(reverseOnlyLetters("") == "");
cout << "All tests passed!" << endl;
}
7.2 性能优化
-
减少内存分配:
- 预分配字符串空间:
s.reserve(n) - 尽量使用
+=而非+拼接字符串
- 预分配字符串空间:
-
算法选择:
- 能用O(n)算法就不用O(n^2)
- 哈希表统计比暴力搜索更高效
-
标准库函数:
std::reversestd::tolowerstd::isalnum
7.3 常见错误
-
索引越界:
- 忘记检查字符串是否为空
- 循环条件错误导致访问
s[-1]或s[s.size()]
-
字符处理错误:
- 混淆字符和数字(忘记
-'0'转换) - 大小写转换错误
- 混淆字符和数字(忘记
-
边界条件:
- 最后一个单词后面没有空格
- 乘法结果有前导零
- 反转时奇数长度处理
8. 扩展思考
8.1 Unicode字符串处理
现代C++支持Unicode字符串,处理时需要注意:
- 使用
wstring代替string - 字符可能占用多个字节
- 排序和比较需要考虑本地化设置
cpp复制wstring ws = L"你好世界";
wcout << ws << endl;
8.2 正则表达式应用
C++11引入了<regex>库,适合复杂字符串匹配:
cpp复制regex word_regex("(\\w+)");
string s = "Quick brown fox";
smatch matches;
if (regex_search(s, matches, word_regex)) {
cout << matches[1] << endl; // 输出"Quick"
}
8.3 字符串视图(string_view)
C++17引入的string_view可以避免不必要的字符串拷贝:
cpp复制string s = "Hello World";
string_view sv(s.c_str(), 5); // "Hello"
cout << sv << endl;
在实际项目中,字符串处理往往占用了大量CPU时间。通过掌握这些经典算法和优化技巧,可以显著提升程序性能。建议读者在理解这些基础算法后,尝试解决更复杂的字符串处理问题,如正则表达式引擎、字符串压缩、模式匹配等高级话题。