剑指offer2之翻转字符串

题目一(翻转单词顺序列)

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串 “I am a student.”,则输出 “student. a am I”。

算法思路

下面介绍两种思路,分为翻转法后追加法
翻转法:显然,我们可以先对整个句子翻转,然后再对每个单词进行翻转就可得到所求。单词的边界就通过空格来判断即可。
后追加法:从输出结果,可以看出这么一个规律。前一个单词需要追加到后一个单词的后面。因此,我们可以遍历字符串,通过空格,找出每个单词(除了最后一个),然后将空格和单词进行拼接后的结果再和之前的结果顺序拼接得到新的结果。最后,还剩下最后尾巴的部分尚未拼接,将其这部分拼接到当前结果的前面即可。这样子,遍历依次就完成了整个单词顺序翻转的过程,整个过程没有采用翻转,而关键在于单词拼接顺序的改变。

算法实现

翻转法

后追加法

题目二(左旋转字符串)

在题目一的基础上,如果定义字符串的左旋转操作是把字符串的若干个字符转移到字符串的尾部。那么请实现一个函数实现此功能。比如,输入字符串 “abcdefg” 和 2,该函数将返回左旋转两位得到的结果 “cdefgab”。

算法思路

本题最简单的思路就是直接将前若干个数字拼接到后面的子串的后方即可。但本题实际考察的是字符串翻转的使用。
那么通过例子,我们发现对整个字符串翻转之后,得到 “gfedcba”,如果再对前5个字符和后两个字符分别进行字符串翻转之后,那么结果显而易见。总之,借助三次字符串翻转便可达到目的。

算法实现

复杂度

算法的时间复杂度均为 O(n),空间复杂度为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网1
[3] 牛客网2

-------------本文结束感谢您的阅读-------------