题目:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例1:
输入:[“h”,“e”,“l”,“l”,“o”]
输出:[“o”,“l”,“l”,“e”,“h”]
示例2:
输入:[“H”,“a”,“n”,“n”,“a”,“h”]
输出:[“h”,“a”,“n”,“n”,“a”,“H”]

分析:本题难在不能使用额外的空间,只能原地修改数组。解题思路是用 双指针 的方法。定义一个首指针和一个尾指针,分别指向数组头和数组尾,然后交换两指针所指向的内容,接着就两指针向中间移动,直至相遇。具体实现代码如下:

func reverseString(s []byte)  {
    var tmp byte
    var i,j int
    i=0
    j=len(s)-1
    for{
        if i>j{
            break
        }
        tmp=s[i]
        s[i]=s[j]
        s[j]=tmp
        i++
        j--
    }
    fmt.Println(s)
}

时间复杂度:O(n),n为数组长度
空间复杂度:O(1),没有分配额外的空间