【出自WR面试题】
难度系数：★★★☆☆ 被考察系数：★★★☆☆
题目描述：
实现字符串的反转，要求不使用任何系统方法，且时间复杂度最小。
分析与解答：
字符串的反转主要通过字符的交换来实现，需要首先把字符串转换为字符数组，然后定义两个索引分别指向数组的首尾，再交换两个索引位置的值，同时把两个索引的值向中间移动，直到两个索引相遇为止，则完成了字符串的反转。根据字符交换方法的不同，可以采用如下两种实现方法。
方法一：临时变量法
最常用的交换两个变量的方法为定义一个中间变量来交换两个值，主要思路是：假如要交换a与b，通过定义一个中间变量temp来实现变量的交换：temp=a；a=b；b=a。实现代码如下：
程序的运行结果如下：
字符串abcdefg翻转后为：gfedcba
算法性能分析：
这种方法只需要对字符数组变量遍历一次，因此时间复杂度为O（N）（N为字符串的长度）。
方法二：直接交换法
在交换两个变量的时候，另外一种常用的方法为异或的方法，这种方法主要基于如下的特性：a^a=0、a^0=a以及异或操作满足交换律与结合律。假设要交换两个变量a与b，则可以采用如下方法实现：
a=a^b；(www.xing528.com)
b=a^b； //b=a^b=（a^b）^b=a^（b^b）=a^0=a
a=a^b； //a=a^b=（a^b）^a=（b^a）^a=b^（a^a）=b^0=b
实现代码如下：
算法性能分析：
这种方法只需要对字符数组遍历一次，因此时间复杂度为O（N）（N为字符串的长度），与方法一相比，这种方法在实现字符交换的时候不需要额外的变量。
引申：如何实现单词反转
题目描述：把一个句子中的单词进行反转，例如：“howareyou”，进行反转后为“youarehow”。
分析与解答：
主要思路：对字符串进行两次反转操作，第一次对整个字符串中的字符进行反转，反转结果为：“uoyerawoh”，通过这一次的反转已经实现了单词顺序的反转，只不过每个单词中字符的顺序反了，接下来只需要对每个单词进行字符反转即可得到想要的结果：“youare how”。实现代码如下：
程序的运行结果如下：
字符串how are you翻转后为：you are how
算法性能分析：
这种方法对字符串进行了两次遍历，因此时间复杂度为O（N）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
