初级算法实践之字符串篇

一、背景

在这《 初级算法实践之数组篇 》篇文章提起过，未来会按初级、中级、高级三个等级介绍算法。

这篇介绍几个经典的字符串题。

二、整数反转

题意：给一个 32 位的整数，求按 10 进制数字反转之后的值，如果溢出，返回 0 。

思路：先把这个数字储存在 64 位的变量上，记录其符号。

然后将这个变量转化为正数，并反转，再加上对应的符号。

最后判断是否越界。

注意事项：一定要转化为 64 位变量，不然会越界的。

三、验证回文字符串

题意：给一个字符串，只考虑字母和数字，判断是否是回文串。

思路：具体来说，有三种方法。

第一种方法是：先预处理这个字符串，删除无关的符号，然后双指针比较。

第二种方法是：预处理字符串后，反转字符串，判断反转后的字符串是否和原字符串相等。

第三种是先反转字符串，然后依次找到有效字符，进行判断。

当然，上面的方法都需要申请额外的 O(n) 的内存。

如果我们按照题意就在原字符串上判断的话，就只需要 O(1) 的内存解决这个问题。

所以第四个方法就是直接处理。

四、字符串转换整数

题意：给一个字符串，求转化为整数。

规则如下：

1. 丢弃字符串开头的空白  
2. 这个字符串可能有一个 + 或者 -，代表这个数字的符号，当然数字默认是正号。  
3. 之后，应该尽量多的读取连续的数字。  
4. 如果组成的数字大于正数最大值或者负数最小值，则返回对应的最值。

思路： 按照题意处理即可。

第一步跳过空白。

第二部判断符号。

第三部读取数字，这里可以便读取边判断是否越界。

最后返回答案。

五、最后

好了，作为初级的字符串，这里介绍三个算法题吧。

类似的初级字符串题还要字符串反转、字符串的字符组成是否相同、多个字符串的公共前缀等等。

感兴趣的你都可以练习一下。

-EOF-