【正确答案】字符串的反转主要通过字符的交换来实现,需要首先把字符串转换为字符数组,然后定义两个索引分别指向数组的首尾,再交换两个索引位置的值,同时把两个索引的值向中间移动,直到两个索引相遇为止,则完成了字符串的反转。根据字符交换方法的不同,可以采用如下两种实现方法。
方法一:临时变量法
最常用的交换两个变量的方法为:定义一个中间变量来交换两个值,主要思路为:假如要交换a与b,通过定义一个中间变量temp来实现变量的交换:temp=a; a=b; b=a。实现代码如下:
def reverseStr(str):
ch=list(str)
lens=len(ch)
i=0
j=lens-1
while i<j:
tmp=ch[i]
ch[i]=ch[j]
ch[j]=tmp
i+=1
j-=1
return ".join(ch)
if __name__=="__main__":
str="abcdefg"
print "字符串"+str+"翻转后为:",
print reverseStr(str)
程序的运行结果为:
字符串abcdefg 翻转后为:gfedcba
算法性能分析:
这种方法只需要对字符数组变量遍历一次,因此时间复杂度为O(N)(N为字符串的长度)。
方法二:直接交换法
在交换两个变量的时候,另外一种常用的方法为异或的方法,这种方法主要基于如下的特性:a^a=0、a^0=a以及异或操作满足交换律与结合律。假设要交换两个变量a与b,则可以采用如下方法实现:
a=a^b:
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
实现代码如下:
def reverseStr(strs):
ch=list(strs)
lens=len(ch)
i=0
j=lens-1
while i<j:
#Python中不能直接对字符串进行异或操作, 所以借助ord和chr函数。
ch[i]=chr(ord(ch[i])^ord(ch[j]))
ch[j]=chr(ord(ch[i])^ord(ch[j]))
ch[i]=chr(ord(ch[i])^ord(ch[j]))
i+=1
j-=1
return ".join(ch)
算法性能分析:
这种方法只需要对字符数组遍历一次,因此时间复杂度为O(N)(N为字符串的长度)。与方法一相比,这种方法在实现字符交换的时候不需要额外的变量。
【答案解析】[考点] 如何对字符串进行反转