二、字符串 🔡
2.1 字符串自身变化
【344.反转字符串】
原地返回字符串。力扣评论笑死了：“做完这道题我又有自信了。”总之就是非常简单的一道题，但也能实在说到双指针的解法，一个前一个后，然后用一个 tmp 字符来进行交换操作。
2.2 字符串与数字
【7.整数翻转】
数学处理，给出 32 位有符号整数，将每位的数字进行翻转。自己写的比较繁琐，题解会比较简洁：先弹出数字，然后依次判断正负溢出的情况，最后推入数字。
一些知识：
- %求模和求余的不同：-7 求模 10 =-7；-7 求余 10 =3 （C++是求模）
- 弹出和推入数字的写法：弹出：
num=x%10;x/=10;推入：result=result*10+num; - 考虑溢出：INT_MAX/INT_MIN（推入）
【8.字符串转换整数 (atoi)】
这个题很费劲，各种意义上，而且借由这个题能 get 很多知识点，而且最后力扣给的官方题解竟然使用 DFA，枉学自动机好多年。就记录一下用普通的算法需要考虑的点：
- 起始是字母，直接返回 0。
- 起始是空格，删除空格：我使用了 while 循环，实际上只需要用
str = str.trim();函数就可以删除所有空格。 - 当前起始是数字或加号/当前起始是符号：记录负号，如果是符号就考虑符号后的（我是连续用了 idx 记录，到最后再用一个
string tmp = s.substr(idx, s.length() - idx);来保存 idx 到结尾的字符串。 - 删除数字后续的字符串：找到往下的第一个非数字的 idx，然后再用
substr(pos,length)来截取。 - 调用
strToNum函数获取字符对应的数字。
long strToNum(string s, long num)的逻辑：
- num 参数是 1 或-1，表示正数或负数。
- 如果 s 的长度大于 10，正数返回 INT_MAX，负数返回 INT_MIN。这是为了避免超级长的字符串不进行后续的运算，导致数字太大，但是，注意并不是 10 位数以下都是不越界的。
- s 长度小于等于 10 时，正常计算对应的数，这里要用 long 来存储，并乘 num 来表示正负数。
- 判断当前计算的结果是否小于 INT_MIN 或大于 INT_MAX，如果是就修改为边界值，如果不是就用 int()强制类型转换，并最后返回。
其他的一些知识：
- 判断字符是否是数字：
bool isNum=Character.isDigit(ch)，是数字返回 true，不是返回 false。 Integer.MIN_VALUE=INT_MIN=-2^32，Integer.MAX_VALUE=INT_AX=2^32-1。
弹出和推入数字的写法：弹出：num=x%10;x/=10; 推入：result=result*10+num;
2.3 字符串匹配
【38.外观数列】
下一个字符串是根据上一个字符串作为描述生成的，给定 n 求第 n 个生成的数列。写的时候稍微思路有点乱，实现了给定描述生成字符串和给定字符串生成描述的两个函数，结果发现后一个根本不需要。还有一个要注意的点是：最开始写的时候把描述搞错了，用了一个 10 个数字的数组作为哈希表，但是实际上统计次数还要符合数字的出现顺序，所以用一个外部的变量循环地记录当前数字出现的次数，如果当前数字和下一个数字不符时，更新输出的字符串和外部变量即可。
【14.最长公共前缀】
茴有几种写法，最长公共前缀有几种写法？看官方题解的话，明明是个简单题，会发现有 4 种解法。
- 横向扫描: 依次遍历，每个遍历的字符串更新公共前缀。时间：O(mn)，空间 O(1)。m 是字符串平均长度，n 是字符串数量，后续相同。
- 纵向扫描：遍历每一列，这个思路和我的解法比较类似。时间：O(mn)，空间 O(1)。
- 分治法：LCP 满足结合律，分治法求最长前缀，分解成两个子问题分别求解，然后再计算最长前缀。时间：O(mn)，空间 O(mlogn)。
- 二分查找法：最长公共前缀的长度不会超过字符串数组中的最短字符串的长度，用二分查找来确定即可。时间：O(mnlogm)，空间 O(1)。
KMP 算法
【28.实现 strStr()】
在 haystack 字符串中找出 needle 字符串出现的第一个位置，如果不存在就输出-1，如果 needle 是空字符串就返回 0。主要有两种算法，暴力和 KMP 算法（之后再专门梳理 KMP 算法的理解）。
2.4 验证字符串是否满足某种性质
【125.验证回文串】
有混着非数字和字母的字符串，判断除开其余字符是否是回文串。这里我考虑的是双指针的想法，一个从右到左，一个从左到右，如果是非字母数字的字符就再向中间走，如果都是数字字母就比较，不相等就返回 false，直到i>=j，最后返回 true。题解的想法也不错，先把所有的字母数字挑出来，同时用tolower()函数转化为小写字母，然后 reverse 字符串，再比较两个字符串是否相等。但是确实没有双指针法快。
【242.有效的字母异位词】
异位词就是字符出现次数都相等的词。我刚开始考虑用unordered_map<char, int>来存储出现的字符和对应的次数，这样的话，就需要判断键是否存在在 map 中，所以会更耗时间。题解是用一个vector<int> ch(26,0)就能够达到同样的功能，这个确实是多写就能自然而然想到的点。
【387.字符串中的第一个唯一字符】
用 unordered_map 做一个哈希，用<char,int>的存储空间会比<int,int>的存储空间更高，因为 char 只占 1 个字节而 int 占 4 个字节。 官方还提供了其他的解法， 比如用哈希表存储单独出现的位置，如果重复的话就置为-1，然后再次遍历找最小的不为-1 的值。还有一个解法是用队列。不过三种解法时间空间复杂度都一样。