初级算法实践之字符串篇

作者: | 更新日期:

字符串的一些练习题,你可以看看。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

一、背景

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

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

二、整数反转

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

思路:先把这个数字储存在64位的变量上,记录其符号。
然后将这个变量转化为正数,并反转,再加上对应的符号。
最后判断是否越界。

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

三、验证回文字符串

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

思路:具体来说,有三种方法。

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

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

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

当然,上面的方法都需要申请额外的O(n)的内存。
如果我们按照题意就在原字符串上判断的话,就只需要O(1)的内存解决这个问题。
所以第四个方法就是直接处理。

四、字符串转换整数

题意:给一个字符串,求转化为整数。

规则如下:

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

思路: 按照题意处理即可。
第一步跳过空白。
第二部判断符号。
第三部读取数字,这里可以便读取边判断是否越界。
最后返回答案。

五、最后

好了,作为初级的字符串,这里介绍三个算法题吧。
类似的初级字符串题还要字符串反转、字符串的字符组成是否相同、多个字符串的公共前缀等等。
感兴趣的你都可以练习一下。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越