344.反转字符串
卡哥建议： 本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下 平时刷题什么时候用 库函数，什么时候 不用库函数
题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
做题思路：
可以用双指针法，前后用两个指针，再把两个指针的内容相互交换，两个指针不能移到中间。交换的库函数是swap（a,b)，参数a和b可以是任何数据类型，该函数不返回任何内容，它交换两个变量的值。
代码，字符串用vector容器存放：
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 void reverseString(vector<char>& s) {
5 int l = 0;
6 int r = s.size() - 1;
7 while(l < r)
8 {
9 swap(s[l],s[r]); //交换库函数
10 l++;
11 r--;
12 }
13 }
14 int main()
15 {
16 vector<char> s;
17
18 int n;
19 cin >> n;
20 for(int i = 0; i < n; i++)
21 {
22 char num = 0;
23 cin >> num;
24 s.push_back(num);
25 }
26 reverseString(s);
27 for(vector<char>::iterator it = s.begin(); it != s.end(); it++) //vector容器的遍历
28 {
29 cout << (*it);
30 }
31 cout << endl;
32 return 0;
33 }
运行结果：
541. 反转字符串II
卡哥建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
做题思路：
题目说每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符,那要先找到2k个字符。用for循环有 i++，是每次一个的遍历；还有 i += 2k，是每次2k 的遍历。其中反转题目有要求，在2k个把前k个反转了；还有剩余字符理解的话就是没凑够要反转的k个的字符；前 k 个字符不能反转后，那就是剩余字符反转的问题，所以一开始不用处理剩余字符的问题。
本题代码：
1 string reverseStr(string s, int k) {
2 for (int i = 0; i < s.size(); i += (2 * k)) {
3 // 1. 每隔 2k 个字符的前 k 个字符进行反转
4
5 if (i + k <= s.size()) { //不能在空子串里操作
6 reverse(s, i, i + k - 1); // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
7 continue; //反转前k个后，结束这一轮循环，不用走到下面的代码了
8 }
9 // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
10 reverse(s, i, s.size() - 1); //将s中当前字符到末尾字符全部反转
11 }
12 return s;
13 }
151.翻转字符串里的单词
卡哥建议：这道题目基本把 刚刚做过的字符串操作 都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
做题思路：
整体思路见卡哥的文章。双指针移除空格的思路和之前移除元素的思路是一样的。快指针去找字符串中不为空的字母，慢指针除了把这个不为空的字母对应的位置记录下来，同时向后移动，还要做好分割成单个单词的操作，就是单词间加一个空格。
在处理空格时，先可以选择忽略空格，就是在一个没有空格的字符串里操作；再利用快指针把不为空的单词收集起来，如果快指针遇到空了，那慢指针此时要在这个位置加空格，如果是整个字符串的第一个单词，我们不需要加空格，因为除了第一个单词前面外，第二个单词.....他们前面要加空格，这个要在找空格的while循环一开始判断，紧接着慢指针加1，再去找下一个单词，再找空格。
本题代码：
1 void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
2 for (int i = start, j = end; i < j; i++, j--) {
3 swap(s[i], s[j]);
4 }
5 }
6
7 void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
8 int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html
9 for (int i = 0; i < s.size(); ++i) { //这个i和while循环的i意义不同，这个i是为了控制初快指针的始条件，和移动关系不大
10 if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格，忽略掉s的空格
11 if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
12 while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
13 s[slow++] = s[i++]; //快慢指针向后移动
14 }
15 }
16 }
17 s.resize(slow); //slow的大小即为去除多余空格后的大小，更新slow
18 }
19
20 string reverseWords(string s) { //反转单词
21 removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
22 reverse(s, 0, s.size() - 1);
23 int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
24 for (int i = 0; i <= s.size(); ++i) {
25 if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
26 reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
27 start = i + 1; //更新下一个单词的开始下标start，下一次反转要知道从哪个位置反转
28 }
29 }
30 return s;
31 }