一、仅反转字母

917. 仅仅反转字母 - 力扣（LeetCode）

简单来说输入字符串，要求你返回所有仅字母位置反转后的字符串。

简单看一个样例加深理解：

前后互换，我想思路基本很明显了，双指针，或者说前后指针法。

基本上循环停止的条件就是指针交汇，具体还是拿这个样例画图看看：

下次就该交汇了，等于当两指针相遇或者错过了，那么循环就该停止，换言之，head < tail循环才能进行。

简单写写代码尝试尝试：

没啥问题，思路也没多难，就是个指针，一个从前往后，一个从后往前，三种情况，如果俩指针指向的都是字母那就互换；哪个不是哪个就继续遍历，直到俩都是字母。

最后返回即可。

重点是有了STL以后明显看出来，s.size是库里的，swap也不用自己写了，isalpha用的是C学的字符函数，自己出出思路，麻烦事都有库和编译器解决，好不快活。

二、字符串中第一个唯一字符

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

1.第一次尝试

看见这一道题第一反应是写个双指针，一个指针站岗，另一个指针遍历。这个方法大概率就是O( $n^{2}$ )。

而且可恨的是我自己写的时候其实很搞笑：

class Solution {
public:int firstUniqChar(string s) {int ptree = 0;int ps = 1;if (s.size() == 1)return 0;while (ptree < s.size()){while (ps < s.size()&&s[ptree] != s[ps]){ps++;}if (ps < s.size() && s[ptree] == s[ps]){ptree++;}if(ps == s.size())return ptree;}return -1;}
};

错误原因倒是也简单：

按照我写的代码逻辑，很明显只会站到ptree的下一个位置开始遍历，这样第二个a就会被误认为是第一个唯一字符。

2.归巢原理

class Solution {
public:int firstUniqChar(string s) {int arr[26] = { 0 };int ps = 0;while (ps < s.size()){int value = s[ps] - 'a';arr[value]++;ps++;}int i = 0;while (arr[i] != 1){i++;}if (i < 26){char rep = i + 'a';ps = 0;while (ps < s.size()){if (s[ps] == rep)return ps;ps++;}}elsereturn -1;}
};

因为第一次尝试末尾的错误，我大脑里并不是说继续走下去那个O( $n^{2}$ )的算法，因为那样真的是实打实的高复杂度。我想到归巢原理就是因为我冒出来了一个念头，如果前后都能知道都能照顾的到就好了，就想到了计数，也就是类似于我们之前写过的计数排序一样。

当然，这段代码还是有问题，不是全部路径都有返回值就不说了。

最开始的归巢写的倒是没啥问题，但是后面判断的顺序我错了：

在后面的调试中可以看到，我的逻辑是哪个是第一个1那就是第一个唯一字符，其实这段代码写出来就有问题，你arr中是以英文字母表的顺序排列的，又不是原字符串s，所以就会出现错误。

最后我把归巢化简，并遍历s来确定谁是第一个唯一字符：

class Solution {
public: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;}
};

入乡随俗了，C++里有这么个方便的遍历方式就用起来，然后根据下标从头开始对比这个字符在数组中映射的值是不是1。

三、字符串最后一个单词的长度

字符串最后一个单词的长度_牛客题霸_牛客网

其实这么看来还简单了一点，简单到哪了呢？

每个单词之间用' '分割，这样的话你倒着读取，找到最后一个空格，最后一个空格后不就是最后一个单词嘛，有了最后一个空格的位置何愁最后一个单词的长度呢。

#include <iostream>
using namespace std;int main() {string s("hellonowcoder");cin >> s;int space = s.size() - 1;while (space >= 0 && s[space] != ' '){space--;}if (space < 0)cout<< s.size() <<endl;elsecout<< s.size() - space - 1 << endl;return 0;
}

但是天有不测风云：

原因也简单，cin和scanf读数据的时候默认跳过空格，所以这样的话只能读到第一个单词，永远输出的值都是第一个单词的值，在VS上调试可知：

所以这里就用到我们说的getline函数了：

讲string的时候就说了，这玩意平常不显山不露水的，一遇到事它是真上啊，你把默认分界符（空格）改了不就行了。

#include <iostream>
using namespace std;int main() {string s("hellonowcoder");getline(cin,s);int space = s.size() - 1;while (space >= 0 && s[space] != ' '){space--;}if (space < 0)cout<< s.size() <<endl;elsecout<< s.size() - space - 1 << endl;return 0;
}

直接大功告成。

四、验证回文串

125. 验证回文串 - 力扣（LeetCode）

别管思路不思路，上来你就得干个大小写转换，因为只要是相同的字母，不管大小写都算相同，所以索性直接全变大或者全变小。

然后其实也简单，直接双指针前后对照就行，这个题其实超级像反转字母，只不过对遍历到的对象的操作不一样。

class Solution {
public:bool isalphaornum(char ch){if(isalpha(ch)||(ch >= '0'&&ch <= '9'))return true;elsereturn false;}bool isPalindrome(string s) {//转换for(auto& ch: s){if(isupper(ch))ch = tolower(ch);}int phead = 0;int ptail = s.size() - 1;while(phead <= ptail){while(phead < ptail&&!isalphaornum(s[phead]))phead++;while(phead < ptail&&!isalphaornum(s[ptail]))ptail--;if(s[phead] != s[ptail])return false;phead++;ptail--;}return true;}
};

需要强调的有两点，虽然最后题目通过了，tolower函数的返回值：

返回对应小写字母的ASCII码，也就是说传参不能改变实参的值，我自己写的时候直接是tolower(ch)，结果拿着一调试我发现自己压根没变大小写。

然后就是注意题上要求的是字符串只剩字母和数字。

五、字符串相加

415. 字符串相加 - 力扣（LeetCode）

为什么说有这种需求呢，没事搞啥字符串相加。

看题上给的样例不也就正常数字相加嘛：

实际上样例的意思是让你写出来函数让字符串实现整型的相加减，因为正常情况下一个int最多存42亿多的值，而longlong啥的肯定更大，只不过总归是有限度的，有极个别，航天领域之类的可能会遇到整型无法计算的值，而字符串的长度可是无限的啊，这玩意就说存个42亿，也就十位数大概11个字节存下，重点这玩意还能继续存啊。你把char[10000]填满，longlong啥的或者更大的能达到吗？

所以实现字符串相加其实还挺合理的。

思路：

我的思路很简单，末尾对齐当竖式算，从后往前依次取出来字符，并将其转换为整型计算，把进位记录下来进入下次的计算，直至最长的都被加完。

这个直至有点麻烦，也就是说你一直得检查是否越界，越界以后那就不用再加了基本上。

具体代码里分析怎么解决：

一写代码就有思路了，那就是先把短的能加的位加完，出了这个循环再写俩循环去把俩字符串检查检查是不是全部算完了。

转换成整型算数，算出来比如6+7就是13，1得进位，3得留下，所以就处理一下。然后存到最后返回的字符串里，但是问题就来了，那就是用insert那就O(n^2)了，所以我写的代码其实是push_back，这么搞不就反了，不过也简单：

库里面有reverse算法。

所以算完最后reverse就行。

随便写一个数看看剩下没有计算的位数怎么插入，很明显，继续从后往前尾插就算了：

只可能存在一个越界另一个没越界和两个同时越界的情况，同时越界那后面两段代码也能兼顾得到，只不过不走而已。另外就是特别注意短的走完了也可能进位，别忘加一下。

而且保证所有循环结束后进位加完了，避免有9 + 1的情况：

class Solution {
public:string addStrings(string num1, string num2) {string ret;int p1 = num1.size() - 1;int p2 = num2.size() - 1;int sum = 0;//记录和int carry = 0;//记录进位int value = 0;//记录留下的值while(p1 >= 0 && p2 >= 0){sum = num1[p1] - '0' + num2[p2] - '0' + carry;carry = sum / 10;//进位value = sum % 10;//除去进位的值ret.push_back(value + '0');p1--;p2--;}if(p1 < 0){while(p2 >= 0){sum = num2[p2] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p2--;}}if(p2 < 0){while(p1 >= 0){sum = num1[p1] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p1--;}}if(carry > 0)ret.push_back(carry + '0');reverse(ret.begin(),ret.end());return ret;}
};

六、反转字符串

541. 反转字符串 II - 力扣（LeetCode）

其实读了读这段话每k个字符反转一次，每2k重置一次。

我个人看了这么多倾向于写个循环处理整个字符串是k的倍数的情况，至于不是k的倍数的，大致上分的两种其实基本差不多：

到时候遍历肯定是用指针遍历，画图的时候就当成指针了，但是等到需要reverse的时候一定得转换成迭代器（因为有迭代器就可以用STL库里的reversel了，超级省事）刚开始不妨都放到字符串的头，后面的指针往后一直走，走到k个就传迭代器调reverse算法，然后走到2k个就把前面的迭代器拉过来。

简单来说循环里就是一个站岗一个遍历。

一旦出了循环，刚好是2k的倍数，这种情况不多说。

这个时候计算。后面指针，就说叫soldier吧，毕竟老累了，冲锋陷阵，前面站岗的我也不知道哨兵是啥，就起个tree。如果soldier-tree<k那就不用费劲了，传tree和end()不就完成任务了；如果k<soldier-tree<2k，其实根本不用管了，因为前面每2k个不用说了，剩下的前k个肯定会被处理，只不过重置前直接跳出循环了，剩下那不足k个又不用管他。

当然还是举例子看一眼合适，这玩意总会出现+1-1的问题：

结果就发现，如果直接用下标-，还需要+1才准。

class Solution {
public:string reverseStr(string s, int k) {int tree = 0;int soldier = 0;while(soldier < s.size()){if(soldier - tree + 1 == k){string::iterator it1 = s.begin() + tree;//迭代器用的时候左闭右开string::iterator it2 = s.begin() + soldier + 1;reverse(it1,it2);}if(soldier - tree + 1 == 2 * k){tree = ++soldier;}soldier++;}if(soldier - tree + 1 <= k){string::iterator it = s.begin() + tree;reverse(it,s.end());}return s;}
};

强调一个点，最后if的时候其实我写的是soldier - tree + 1 < k，不足k个的话直接全部反转呗，但是难免出现特例：

7个元素，不够8个，上面的循环仅仅是soldier一直后移，啥也没干，但是最后soldier的位置拿下标来说的话，其实是下标7的位置，7 + 1刚好是8，刚好不符合小于，也就没办法给它reverse，一修就行了。

七、反转字符串中的单词

557. 反转字符串中的单词 III - 力扣（LeetCode）

再看一眼例子：

思路直接出来了，还是两个指针，一个指针只要碰见字母就停下，一个指针碰到空格或'\0'就停下，这样这俩指针站的也刚好就是reverse的两个迭代器的位置，所以这次直接尝试用迭代器遍历吧，虽然没有那么浅显易懂，但是总归reverse的时候爽。

class Solution {
public:string reverseWords(string s) {string::iterator alpha = s.begin();string::iterator space = s.begin();while(space != s.end()){   if(!isalpha(*alpha))alpha++;if(*space != ' ')space++;if(isalpha(*alpha)&&*space == ' '){reverse(alpha,space);alpha = space++;}}//到最后直接跳出来了，并没有reverse最后一个单词reverse(alpha,space);return s;}
};

代码看着没啥毛病，但是架不住题阴啊：

合着把(也给我当成单词里的字符了，我真服了，所以alpha的遍历我也不整那么多虚的了，初始化为begin，以后全部改为' '位置+1包对的，我不再用isalpha做判断条件了，太阴了。

class Solution {
public:string reverseWords(string s) {string::iterator alpha = s.begin();string::iterator space = s.begin();while(space != s.end()){   if(*space != ' ')space++;if(*space == ' '){reverse(alpha,space);alpha = ++space;}}//到最后直接跳出来了，并没有reverse最后一个单词reverse(alpha,space);return s;}
};

阴死我了，我看见上面那个样例其实我人是蒙的，后来单独拉出来string和它的左括号直接无语了，现在alpha不用找了，刚开始在begin后面就在' '+1，利用的是：

太阴了，不过还是做出来了。

八、字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

其实写字符串相加和写这个字符串相乘都不是同一天，写完字符串相加的时候我还在想，进位的问题嘛，加法最大9+9等于18，最多进位1；然后我就想到如果乘法那就进位大了，结果今天就看见这道字符串相乘了，果然我能想到的，出题的也能想到啊。

就拿这个例子来说，我最开始想的是把短的拆成不同位数去乘

空想完了我发现，其实还是要用到int或者更大的longlong才能用，我就回想我做字符串相加最核心的思想就是拆分，当时是对齐以后，两数相加以后记录下来进位记录下来留下的值，所以核心应该还是拆分。

于是我就列了个竖式，其实我们竖式的思想就是每位乘后再加，而且我观察到：

竖式算出来几行也就是几个数取决于下面的字符串有多长，完全可以创建两个空字符串，第一个字符串记录上次算出来的和，第二个字符串记录这次算出来的数，并且末尾补0（to_string再push_back字符'0'即可）。最后再让这俩字符串相加存到第一个字符串上，字符串相加已经实现过了。

上面这种操作不断循环，直至把较短字符串从后往前遍历完，但是如果较长字符串长度是n1，较短字符串是n2的话，那么内层再嵌套个字符串相加，基本上最少都得是n1的长度，也就是说可能是n1*n2的复杂度。

一路修修补补过来的，不再一段一段代码复制粘贴了，直接看最后成果：

class Solution {
public:string addStrings(string num1, string num2) {string ret;int p1 = num1.size() - 1;int p2 = num2.size() - 1;int sum = 0;//记录和int carry = 0;//记录进位int value = 0;//记录留下的值while(p1 >= 0 && p2 >= 0){sum = num1[p1] - '0' + num2[p2] - '0' + carry;carry = sum / 10;//进位value = sum % 10;//除去进位的值ret.push_back(value + '0');p1--;p2--;}if(p1 < 0){while(p2 >= 0){sum = num2[p2] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p2--;}}if(p2 < 0){while(p1 >= 0){sum = num1[p1] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p1--;}}if(carry > 0)ret.push_back(carry + '0');reverse(ret.begin(),ret.end());return ret;}string multiply(string num1, string num2) {//如果有一个是0就不用算了，直接return算了if(num1[0] == '0'||num2[0] == '0'){return "0";}string multi;string ret("0");string now;int carry = 0;//记录进位int value = 0;//记录尾插值int mul = 0;//记录每两位的积//还是创建俩指针来遍历字符串int p1 = num1.size() - 1;int p2 = num2.size() - 1;//以竖式下面的值的长度定while(p2 >= 0){//计算每一位与num1这个字符串相乘的值while(p1 >= 0){int mul = (num1[p1] - '0') * (num2[p2] - '0') + carry;carry = mul / 10; value = mul % 10;multi.push_back(value + '0');p1--;}//防止9 * 9 = 81只插1，把carry清空再说if(carry != 0){multi.push_back(carry + '0');carry = 0;}//定nowreverse(multi.begin(),multi.end());now = multi;multi = "";for(int i = 0;i < num2.size() - p2 - 1;i++){now.push_back('0');}//相加ret = addStrings(ret,now);p1 = num1.size() - 1;p2--;}return ret;}
};

上面那段是字符串相加，不多解释。

创建的multi是用来接收本次计算得到的值的，所以当本次值已经给出去以后