1.反转字符串
方法1: 直接调用库函数 reverse函数,时间复杂度O(n)，通过一个for循环来实现。
实现原理：通过双指针实现，一个头指针指向字符串第一个字符，另一个尾指针指向字符串的尾部
void reverseString(vector<char>& s) { for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) { swap(s[i],s[j]); } }
题型:
(1) 直接反转一个单个字符串
注意这里不可以将string塞到vector中,不然是反转不了Hello的，因为你会发现a[0]就是Hello，这是我刚刚踩的大坑
#include<bits/stdc++.h> using namespace std; void reverseStr(vector<char>& s) { for(int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) { swap(s[i], s[j]); } } int main() { vector<char>a; a.push_back('H'); a.push_back('e'); a.push_back('l'); a.push_back('l'); a.push_back('o'); reverseStr(a); for(auto str : a) { cout<<str; } }
(2)在一个长的主字符串中反转n个长度为k的子字符串
class Solution { public: string reverseStr(string s, int k) { for (int i = 0; i < s.size(); i += (2 * k)) { // 1. 每隔 2k 个字符的前 k 个字符进行反转 // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符 if (i + k <= s.size()) { reverse(s.begin() + i, s.begin() + i + k ); } else { // 3. 剩余字符少于 k 个，则将剩余字符全部反转。 reverse(s.begin() + i, s.end()); } } return s; } };
reverse 函数的具体实现参考前面的代码
(3)反转字符串里面的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
大体思路：
首先将字符串两侧的空格去除，单词中间的空格要留下，可以用一个函数来实现
我们可以用库函数erase来实现，库函数erase的时间复杂度--在删除单个元素的时候时间复杂度为O(1)，若删除一个区间的元素的时间复杂度为O(n).
void removeExtraSpaces(string& s) { for (int i = s.size() - 1; i > 0; i--) { if (s[i] == s[i - 1] && s[i] == ' ') { s.erase(s.begin() + i); } } // 删除字符串最后面的空格 if (s.size() > 0 && s[s.size() - 1] == ' ') { s.erase(s.begin() + s.size() - 1); } // 删除字符串最前面的空格 if (s.size() > 0 && s[0] == ' ') { s.erase(s.begin()); } }
我们也可以用双指针法来实现
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。 int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html for (int i = 0; i < s.size(); ++i) { // if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。 if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。 while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。 s[slow++] = s[i++]; } } } s.resize(slow); //slow的大小即为去除多余空格后的大小。 }
这样我们既删除了字符串首尾的空格，也将单词之间的大于一的冗余的空格的数量统一都缩小到1
对空格处理完之后，我们就可以对字符串进行处理了
string reverseWords(string s) { removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。 reverse(s, 0, s.size() - 1); int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。 for (int i = 0; i <= s.size(); ++i) { if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。 reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。 start = i + 1; //更新下一个单词的开始下标start } } return s; } };
先将整个句子都倒过来，再将每个单词都正回来
2.替换数字--双指针实现
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
大体思路：
先用一个for循环来检查一下有多少个数字，然后根据数字的数量进行扩容，再用双指针进行操作，一个指针指向原字符串的末尾，一个指针指向扩容后的字符数组的末尾，利用双指针操作进行替换数字。
#include<iostream> using namespace std; int main() { string s; while (cin >> s) { int count = 0; // 统计数字的个数 int sOldSize = s.size(); for (int i = 0; i < s.size(); i++) { if (s[i] >= '0' && s[i] <= '9') { count++; } } // 扩充字符串s的大小，也就是每个空格替换成"number"之后的大小 s.resize(s.size() + count * 5); int sNewSize = s.size(); // 从后先前将空格替换为"number" for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) { if (s[j] > '9' || s[j] < '0') { s[i] = s[j]; } else { s[i] = 'r'; s[i - 1] = 'e'; s[i - 2] = 'b'; s[i - 3] = 'm'; s[i - 4] = 'u'; s[i - 5] = 'n'; i -= 5; } } cout << s << endl; } }
请务必注意 i-=5 的操作
