1、反转字符串
首先我们来看第一道，先从简单一点的开始做起✍
① 题目描述：
class Solution { public: void reverseString(vector<char>& s) { } };
② 思路分析：
- 本题很简单，就是将题目中给出的字符串做一个前后逆置的操作。这边首先想到的就是双指针的一个思路，让一个指针
i在前，一个指针j在后，相对而行，不断交互二者位置上的字符，直到二者相遇为止
③ 代码展示：
- 代码很简洁，一个for循环就能搞定了
void reverseString(vector<char>& s) { for(int i = 0, j = s.size() - 1; i < j; ++i, --j) { swap(s[i], s[j]); } }
④ 运行结果：
- 来看看执行结果，发现效率中一般，不过能AC就行😁
2、反转字符串||
接下去再来看第二道，稍稍复杂一些
① 题目描述：
class Solution { public: string reverseStr(string s, int k) { } };
② 思路分析：
- 本题相对上一题来说就发生了一些变化，虽然都是在反转字符串，但本题呢不是一个一个地在遍历，而是2k个2k个地在遍历，在题目给到的参数中还有一个k，我们在遍历这个字符串时是 ==一次遍历2k个，然后反转前k个==
- 在不断执行的过程中总会碰到结束，此时题目又给出了两种结果。
- 也就是当剩余的字符少于2k个，但是大于等于k个的话，则反转前k个，这个其实我们可以和题干中的意思做一个结合，多加一个是否到达结尾即可
- 当剩余的字符连k个都不足的话，此时将剩余的全部反转即可
- 很多同学在写本题的时候都会纠结于这个2k，所以在循环遍历的时候会选择拿一个计数器去计数，然后当这个计数器到达的 2k 的时候就对前k个去做反转，其实没必要这样，我们在这里直接去修改循环遍历的次数即可，即
i += 2 * k，让i每次移动的距离就是 2k 个，那当我们在遍历的时候也无需去考虑那么多了
接下去呢我们就要在循环内部去反转对应的字符串了，这里大家可以自己实现一个（就是我们上一题所讲的代码），或者是直接使用库函数【reverse】
- 不过记住了在库函数这里我们要传递的是 ==迭代器==，注意这里【reverse】是左闭右开的，所以不包含
i + k这个位置
reverse(s.begin() + i, s.begin() + i + k);
- 不过呢也不是任何区间我们都可以去做反转的，至少不能发生越界的情况，此时我们给出判断的条件
i + k <= s.size()，因为i + k这个位置是不包含的，所以我们在判断条件中要加上 - 那在反转之后为什么还要再加一个
continue呢，原因就在于我们只是反转前k个，而后k个是不动的，所以在反转完后直接继续向后比较遍历 2k 个即可
if(i + k <= s.size()) { reverse(s.begin() + i, s.begin() + i + k); continue; // 只翻转前k个, 翻转完后继续遍历 }
- 那在之后呢我们还要去考虑到这个剩余的字符问题，小于2k但是大于等于k已经包含在了上面的代码中，而我们此时要考虑的就是不足k个的问题，所以直接反转从当前的位置到结尾即可
// 考虑到最后的字符少于k个的情况 reverse(s.begin() + i, s.end());
③ 代码展示：
- 最后来看一下整体的代码，可以看出也不是非常复杂
string reverseStr(string s, int k) { for(int i = 0;i < s.size(); i += 2 * k) { if(i + k <= s.size()) { reverse(s.begin() + i, s.begin() + i + k); continue; // 只翻转前k个, 翻转完后继续遍历 } // 考虑到最后的字符少于k个的情况 reverse(s.begin() + i, s.end()); } return s; }
④ 运行结果：
- 最后再来看下执行结果吧
3、字符串最后一个单词的长度
然后是第三题，我们来看看和 string类 API相关的一些题目
① 题目描述：
② 思路分析：
- 好，我们来分析一下本题该如何去进行求解。题目的意思很明确，就是给你一个字符串，然后计算出这个字符串最后一个单词的长度
- 我们知道单词都是以【空格】作为分割，此时我们只需要去找到最后一个空间即可，然后计算出从这个空格开始到结尾有多少字符
此时我们可以使用到的是string类中 rfind() 接口，从一个字符串开始从后往前进行寻找，找第一个空格
size_t pos = s.rfind(' ');
- 那如果找到了这个空格的话就可以去输出最后一个单词的长度的，因为这是【左闭右开】的，而我们不能计算上
pos这个位置空格的长度，所以要从pos + 1的位置开始计数
cout << s.size() - (pos + 1) << endl;
- 不过呢我们还要考虑到给到的字符串没有空格的情况，这个时候返回这个字符串的【size】即可
// 如果不存在空格, 直接返回当前字符串的长度 cout << s.size() << endl;
- 这里我们先执行一下试试看，发现取到的长度是5，这是为什么呢？
- 面对这个问题而言我们可以到VS上去调试一下，发现当使用
cin >>流插入在进行读取的时候只读到了前面的【hello】，但是呢后面的【newcoder】却没有读取到，这个我们在讲解 STL中的string类 时就有说到过，对于像cin >>、scanf()这些都是会去缓冲区里面读内容，但是呢在读取到空格的时候就会自动截止了，而无法完成整行的读取
- 而我们若是要进行一整行读取的话可以使用
get()，不过在这里呢我更推荐 getline() 函数，传递进流对象cin和所要读取的string对象，就可以去读取到整行的信息
- 然后再去读取的时候就发现确实读到了这一整行
③ 代码展示：
- 代码如下，具体见运行结果
#include <iostream> #include <string> using namespace std; int main() { string s; getline(cin, s); //cin >> s; size_t pos = s.rfind(' '); if (pos) { cout << s.size() - (pos + 1) << endl; } else { // 如果不存在空格, 直接返回当前字符串的长度 cout << s.size() << endl; } }
④ 运行结果：
4、找字符串中第一个只出现一次的字符
第四题的话我们再来看看与其他数据结构相结合的题目
① 题目描述：
② 思路分析：
- 本题的题意很清晰，我们要去找的就是在一个字符串中第一次出现的，也是唯一一次出现的字符
- 那么也就意味着我们需要去每一个字符所出现的次数，这立马让我想到了【哈希表】，不知读者一看到此题是什么反应呢？
首先我们考虑先去定义一个哈希表出来，使用到的是
unordered_map，【key】的类型是char、【value】的类型是int
unordered_map<char, int> count;
- 接下去我们就遍历这个字符串s然后统计出每一个字符所出现的次数即可
for(char c: s) { count[c]++; // 统计每个字符出现的次数，放入哈希表中存起来 }
- 最后一步，我们再去遍历这个字符串，然后根据对应的字符到哈希表中去寻找即可，一旦找到一个字符所对应的【value】值是1的话，那就返回这个字符在字符串中所在下标。若是找了一圈还没有发现为1的话，则表示在字符串中并没有只出现一次的数字
// 遍历该统计数组，若是找到第一个只出现一次的，返回其坐标 for(int i = 0;i < s.size(); ++i) { if(count[s[i]] == 1) return i; }
③ 代码展示：
int firstUniqChar(string s) { unordered_map<char, int> count; for(char c: s) { count[c]++; //统计每个字符出现的次数，放入哈希表中存起来 } //遍历该统计数组，若是找到第一个只出现一次的，返回其坐标 for(int i = 0;i < s.size(); ++i) { if(count[s[i]] == 1) return i; } return -1; }
④ 运行结果：
5、仅仅反转字母
接下去我们进阶地要来做一做反转相关的题目
① 题目描述：
② 思路分析：
- 首先来解读一下本题的意思，和第一小题反转字符串很类似，但是呢它在反转的时候不是全部的字符都会反转，而是只反转那些 大小写的字母，除此之外都会别忽略
- 那首先我们双指针的做法还是可行的，只是在从两头往中间遍历的时候需要去判断一下当前字符是不是大小写字母。库里虽然是有API给我们调用，但是呢最好自己写一下，这样比较好控制
bool IsUpperOrLowerLetter(char ch) { if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) return true; return false; }
- 下面我画了一个算法分解图，以题目中的示例3为例
- 上面这个交换的过程中最重要的逻辑就是下面的和这个对当前所在字符的判断，如果当前这个字符不是大小写中英文的话，就继续 前移或者后移
while(begin < end && !IsUpperOrLowerLetter(s[begin])) begin++; while(begin < end && !IsUpperOrLowerLetter(s[end])) end--;
③ 代码展示：
- 好，我们展示一下整体代码
bool IsUpperOrLowerLetter(char ch) { if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) return true; return false; } string reverseOnlyLetters(string s) { int begin = 0, end = s.size() - 1; while(begin < end) { while(begin < end && !IsUpperOrLowerLetter(s[begin])) begin++; while(begin < end && !IsUpperOrLowerLetter(s[end])) end--; swap(s[begin++], s[end--]); } return s; }
④ 运行结果：
- 来看看执行结果，发现还不错哦！
6、验证一个字符串是否是回文
然后我们再来试试验证回文串，本题和上面一题部分类似，可做借鉴
① 题目描述：
② 思路分析：
- 首先来解释一下为什么本题可以借鉴上一题，原因就在于在进行某些判断的时候都需要去忽略一些除指定字符以外的其他字符，而且在遍历的时候也是采取双指针的做法，
- 下面就是对于当前字符是否为字母或者数字的一个判断
bool IsLetterOrDigit(char ch) { if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')) return true; return false; }
然后我们来从头分析一下
- 首先的话题目给出了要求，我们在对这些字符进行判断的时候首先要将它们都转换为小写，可以看到我这里使用到了C++11的一个新语法【范围for】，而且对字符串中的每一个字符都做了引用，这样就可以使得内部的修改带动外部
// 1.将字符串中的所有字符转换为小写 for(auto& c: s) { if(c >= 'A' && c <= 'Z') c += 32; }
- 接下去呢我们就可以去做遍历判断了，这里也给出关键的代码，如果你认真看过上题的话就可以知道，它们的思路基本都是一致的：一个指针从前往后，一个指针从后往前，若是相等的话则继续遍历，直到遇到二者不同为止则
return false。如果在遍历结束了之后没发现不同的话这就是个回文串
// 通过循环略过非字母或 数字的字符 while(begin < end && !IsLetterOrDigit(s[begin])){ begin++; } while(begin < end && !IsLetterOrDigit(s[end])){ end--; }
- 还有一点可以在开头就去做一个判断，当着字符串中没有任何字符而是一个空串的时候，此时它一定是一个回文串，直接
return true即可
if(s.size() == 0) return true;
③ 代码展示：
- 本题的代码较上面的题目还是慢慢多了一些，读者可以先好好看看
bool IsLetterOrDigit(char ch) { if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')) return true; return false; } bool isPalindrome(string s) { if(s.size() == 0) return true; // 1.将字符串中的所有字符转换为小写 for(auto& c: s) { if(c >= 'A' && c <= 'Z') c += 32; } // 2.前后指针遍历判断 int begin = 0, end = s.size() - 1; while(begin < end) { // 通过循环略过非字母或 数字的字符 while(begin < end && !IsLetterOrDigit(s[begin])){ begin++; } while(begin < end && !IsLetterOrDigit(s[end])){ end--; } if(s[begin] != s[end]) { return false; }else{ begin++; end--; } } return true; }
④ 运行结果：
