LeetCode-算法-双指针-第4天

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
具体题目链接

Python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left,right=0,len(s)-1
        while left<right:
            s[left],s[right]=s[right],s[left]
            left+=1
            right-=1

思路：这是最简单的双指针思路，通过左右指针来进行互换。

GO

func reverseString(s []byte)  {
    for left,right:=0,len(s)-1;left<right;left++{
        s[left],s[right]=s[right],s[left]
        right--
    }
}

思路：同python

557. 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
提示：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格
具体题目链接

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.split(" ")[::-1])[::-1]

思路：python的str变量是不可变的，因此不可避免地需要新的空间储存str。得益于python的切片功能，写出来只有一行的方法。s.split(" ")是以" "进行分割成列表，s.split(" ")[::-1]其中[::-1]进行反向列表，" ".join(s.split(" ")[::-1])是以" "为分隔符进行合并数组为字符串，" ".join(s.split(" ")[::-1])[::-1]的[::-1]是反转字符串，及最后达到结果。

GO

func reverseWords(s string) string {
    ret := []byte(s)
    //如果需要包括中文需要ret:=[]byte()
    for length,left,right:=len(ret),0,0;right<length;right++{
        if ret[right]==' '{//若字符为空格，则进行调用reverse进行翻转
            reverse(ret,left,right-1)
            left=right+1
        }else if right==length-1{//若是最后一个字符，则需要一次反转。
            reverse(ret,left,right)
        }
    }
    return string(ret)
}
func reverse(ret[] byte,index,end int){
    for ;index<end;index++{
        ret[index],ret[end]=ret[end],ret[index]
        end--
    }
}

思路：可见注释，reverse函数是双指针进行反转。整个过程需要一次遍历，在遍历中记录单词开始位置和结束位置，之后进行反转。