一 仅仅反转字母
链接如下：https://leetcode-cn.com/problems/reverse-only-letters/submissions/
思路：
这道题目的核心就是交换，我们发现这个逻辑和当时在数据结构里学的快速排序非常类似：两个指针，一个指向开头，一个指向结尾，如果前一个指针的值小于后面指针的值，就交换。相应的在这道题目：如果前一个指针和后一个指针都是字母，那就交换。
所以我们需要先写一个判断是否是字母的函数。（c语言库中有这个函数，如果记得这个函数的名称和使用方法可以直接使用，如果不记得也可以像博主一样现写一个）。还需要写一个交换函数。注意：c++的模板中已经定义了这个函数，所以不需要我们自己实现。
代码实现如下：
1class Solution { 2public: 3bool isLetter(char ch) 4 { 5 if(ch >= 'a' && ch <= 'z') 6 return true; 7 if(ch >= 'A' && ch <= 'Z') 8 return true; 9 return false; 10 } 11 12 string reverseOnlyLetters(string s) 13 { 14 size_t start=0,end=s.size()-1; 15 while(start<end) 16 { 17 while(start<end && !isLetter(s[start])) 18 ++start; 19 while(start<end && !isLetter(s[end])) 20 --end; 21 22 swap(s[start],s[end]); 23 start++; 24 end--; 25 } 26 return s; 27 } 28};
二 找字符串中第一个只出现一次的字符
链接如下：https://leetcode-cn.com/problems/first-unique-character-in-a-string
思路：
我们可以用一个数组去映射26个字母出现的次数
代码实现如下：
1class Solution { 2public: 3 int firstUniqChar(string s) { 4 int count[26]={0}; 5 for(auto ch: s) 6 { 7 count[ch-'a']++; 8 } 9 for(size_t i=0;i<s.size();i++) 10 { 11 if(count[s[i]-'a']==1) 12 return i; 13 } 14 return -1; 15 } 16};
这道题目非常的经典，很多年前就有了，许多公司现在的笔试题都还在考这道题，对于思维有一点的要求。
三 字符串里面最后一个单词的长度
题目意思为：给你一个字符串，去找最后一个单词的长度，相当于需要你去寻找空格。这道题目是一个标准的IO型题目，不是接口型题目。
思路：
（1）寻找空格。但是如果有多个空格怎么办？例如：have a nice day。那我们就可以倒着去找空格，怎么倒着去找空格呢，string中有一个接口已经帮我们实现了：
（2）那我们在string类中怎么去实现输入和输出呢？也有接口已经帮我们实现了：
就相当于运算符重载
（3）当我们找到最后一个空格的时候，怎么计算最后一个单词的长度呢？
这里有一个小妙招：
当区间是左闭右开的时候：如[0,10)，这个时候区间的长度就是所求的长度。
当区间是左闭右闭的时候：如[0,9]，这个时候的区间的长度就比所求的长度少一
字符串最后一个字符的位置是size（）-1 因为size指向的是最后一个字符的下一个位置假设寻找到的空格所在位置是pos
这个时候pos所指向的位置也不是我们所求区间的第一个位置，而是我们所求位置的前一个位置，所以只需要pos+1就可以了。这个时候区间为左闭右开[pos,size)
我们来尝试写一下代码：
1#include<iostream> 2#include<string> 3using namespace std; 4 5int main() { 6 string str; 7 cin >> str; 8 9 size_t pos = str.rfind(' '); 10 cout << str.size() - (pos + 1) << endl; 11}
但是当我们提交之后，发现测试用例不通过，为什么呢？
注意，在C++中输入的时候，如果有多组输入，用空格或换行当作他们的间隔。（scanf也有这个问题）
那么怎么解决呢？C++帮我们想好了：
getline的作用是读取一整行，默认遇到换行才结束。
getline还有一个很厉害的功能：可以自己设定遇到哪个字符结束输入，这个符号放置在第三个参数的位置，第一个参数是istream类型，就是流插入运算符。
所以调整后的代码如下：
1#include<iostream> 2#include<string> 3using namespace std; 4 5int main() { 6 string str; 7 getline(cin,str); 8 size_t pos=str.rfind(' '); 9 if(pos!=str.size()) 10 { 11 cout<< str.size()-(pos+1)<<endl; 12 } 13 else { 14 cout<<str.size()<<endl; 15 } 16}
四 字符串相加
链接如下：https://leetcode-cn.com/problems/add-strings
有些同学看到这道题的思路是：将两个字符串设置成auto类型，相加之和转化为字符串再输出，但是这样的想法是不对的。如果这个个字符串对应的数字比较小可以这样计算，但是如果这两个字符串对应的是几十亿的大数字呢，还能这样计算吗？显然不能，因为这样就越界了。
正确思路：
我们分别从最后一个数字计算相加，大于10的进位，再算前一位数字，这样循环。直到两个字符串都遍历完。
注意：这里有一个易错点：是需要两个字符串都遍历完了才行，而不是只有一个遍历完了就行。所以循环条件要用或 || 而不是且&&（因为如果使用且的话，只要有一个遍历完了就会退出循环，这样会出错）
我们先来给出代码，再来一步一步解答：
1class Solution { 2public: 3 string addStrings(string num1, string num2) { 4 int end1=num1.size()-1,end2=num2.size()-1; 5 string retStr; 6 int carry=0; 7 while(end1>=0 || end2>=0) 8 { 9 int val1=end1>=0?num1[end1--]-'0':0; 10 int val2=end2>=0?num2[end2--]-'0':0; 11 int ret=val1+val2+carry; 12 carry=ret/10; 13 ret=ret%10; 14 15 retStr.insert(0,1,ret+'0'); 16 } 17 if(carry) 18 { 19 retStr.insert(0,1,'1' ); 20 } 21 return retStr; 22 23 } 24};
我们一句一句解释：
1int end1=num1.size()-1,end2=num2.size()-1;
这里设置了两个变量，分别指向两个字符串的最后一个字符。
1int carry=0;
carry代表的英语意思是进位，将进位初始设置为0
1string retStr;
设置了一个新的字符串，用来保存每次相加之和的值
1while(end1>=0 ||end2 >=0)
循环条件：当两个字符串有任意一个没有遍历完都会进入循环
1 2int val1 = end1 >= 0? num1[end1--] : 0; 3int val2 = end2 >= 0? num2[end2--] : 0; 4 5
设置了两个整型变量来存储当前num1[end1] 对应的数字，end1-- 是先取值再将 end1 减 1，指向下一位）；否则 val1 为 0（比如 num1 已经处理完，高位补 0）。
这里的高位补0的逻辑可能有点绕，博主再来讲解一下：
举个生活中的例子：计算
123 + 45时，我们会自然地把它们对齐成：
这里其实就是给
45的高位（百位）补了一个0，变成045再与123相加。在代码中，"高位补 0" 的逻辑体现在这里：
- 当
end1 < 0时（num1已处理完所有字符），val1取0，相当于给num1的高位补 0- 当
end2 < 0时（num2已处理完所有字符），val2取0，相当于给num2的高位补 0
1int ret=val1+val2+carry; 2carry = ret/10; 3ret = ret%10; 4 5
int ret = val1 + val2 + carry;：当前位的两个数字加上进位，得到总和ret。carry = ret / 10;：计算进位（比如ret = 15，则carry = 1）。ret = ret % 10;：得到当前位的结果（比如ret = 15，则当前位结果为5）。
1retStr.insert(0,1,ret+'0');
头插操作：把当前位的结果插入到 retStr 的开头。
头插操作（在字符串开头插入字符）是为了保证最终结果的数字顺序正确。我们可以通过一个具体例子来理解：
而代码的计算顺序是从低位到高位（先算个位，再算十位，最后算百位）：
- 先算个位：3 + 5 = 8 → 得到数字 "8"
- 再算十位：2 + 4 = 6 → 此时需要把 6 放在 8 的前面，变成 "68"
- 最后算百位：1 + 0 = 1 → 再把 1 放在 68 的前面，变成 "168"
这里的 "把新数字放在前面" 就是头插操作
我们在这里复习一下insert这个接口的使用
在指定位置插入多个相同字符
string& insert(size_t pos, size_t n, char c);第一个参数是要插入的位置，第二个参数是插入字符的个数，第三个参数是需要插入的字符
其他的使用方法我们在这里暂不复习
1if（carry) 2{ 3 retStr.inset(0,1,'1'); 4}
当两个字符串都遍历结束时，可能还有进位会遗漏，这个时候就需要判断一下。如果这个时候carry不为0，那么头插一个1。
注意：这篇代码有一个易遗漏的，易错的点：为什么运算输出和输入的时候都要加上‘0’ ？
在代码中，
'0'代表字符'0'（ASCII 码值为 48），它的作用是将数字（整数）转换为对应的字符形式。当我们计算出某一位的结果
ret（比如ret = 5）时，需要将这个数字存储到字符串中。但字符串只能直接存储字符，不能直接存储整数。此时通过
'0' + ret的运算：
- 字符
'0'的 ASCII 码是 48- 当
ret = 5时，'0' + 5 = 48 + 5 = 53，而 53 恰好是字符'5'的 ASCII 码- 因此
'0' + ret的结果就是数字ret对应的字符形式
到此，这道题我们就完成了。
但是这个代码还可不可以优化呢？
优化思路：
我们来算一下这篇代码的时间复杂度是多少？
答案是 O（N^2）
这里常犯的一个错误是很多的同学都会把这里的时间复杂度算成O（n)
原代码中使用
insert(0, ...)头插操作，每次头插都需要将retStr中已有的所有字符后移一位，时间复杂度是 O(N^2)（假设结果字符串长度为 N，每次头插的时间复杂度是 O(N)，共执行 N 次左右）
那么我们可不可以把时间复杂度优化成o(n)呢？
可以的。
思路：
我们将头插操作替换成尾插操作（尾插操作的时间复杂度时O(1) )，当遍历和进位都完成之后，再反转字符串就可以了。
还可以提前分配内存，避免后面频繁扩容，影响频率。原因：两个长度分别为 m 和 n 的字符串相加，结果的最大长度是 max(m, n) + 1
尾插的实现用+=：
在 C++ 的
std::string中，+=是用于在字符串末尾追加字符或字符串的运算符，它本质上就是一种尾插操作
+=用于单个字符时，和push_back()效率相同，都是 O(1) 级别的操作（均摊时间复杂度），不会像头插那样需要移动已有字符
我们来实现代码：
1class Solution { 2public: 3 string addStrings(string num1, string num2) { 4 int end1=num1.size()-1,end2=num2.size()-1; 5 string retStr; 6 int carry=0; 7 retStr.reserve(max(num1.size(),num2.size())+1); 8 while(end1>=0 || end2>=0) 9 { 10 int val1=end1>=0?num1[end1--]-'0':0; 11 int val2=end2>=0?num2[end2--]-'0':0; 12 int ret=val1+val2+carry; 13 carry=ret/10; 14 ret=ret%10; 15 16 retStr+=ret+'0'; 17 } 18 if(carry) 19 { 20 retStr+='1'; 21 } 22 reverse(retStr.begin(),retStr.end()); 23 return retStr; 24 25 } 26};
注意！！！！！一定要区分reserve和reverse，一个时扩容，一个是逆置，二者不可混为一谈
倒数第二行代码逆置的时候，使用了迭代器，所以迭代器的使用其实是重要的。
《【c++】深入理解string类（3）：典型OJ题》 是转载文章，点击查看原文。
