乐趣区

关于golang:刷题笔记剑指-Offer-58-I-翻转单词顺序

这题思路很简略,因为这个是简略题。次要就是要宰割每个单词,而后逆序组成新的字符串。有两种方法,一个是背 API,利用自带的函数帮忙咱们实现去除首尾空格和按空格宰割。另一个如官网题解所示,本人实现双指针,宰割字符串。

难点

为什么我要写这篇题解,因为我面试这题挂了。基于缸中之脑实践和局部性原理,我在接下来几天内,都会频繁地再遇到这题。这题思路上没有任何难点,难点次要在于,如果是用自带函数,在线面试过程中,咱们没方法查看函数定义,甚至没方法应用规范输入 (stdout),须要 背 API。如果是本人实现双指针,须要极度注意 边界 问题。

背 API

Go 中负责去除首尾空格的函数为 strings.Trim,函数签名为func Trim(s, cutset string) strings 参数为要解决的字符串,sep为须要前后去除的字符串,返回值是解决好的字符串。在这里,咱们只须要输出 s = strings.Trim(s, " ") 就能去除首尾的所有空格。

其次,咱们须要将字符串按空格宰割成一个个单词,单词间的可能空格不只一个,比方 "abc defg"。这里咱们要留神, 相对不能应用 strings.Split Split 只能去除单个空格,如果有多个空格,将会宰割成多个长度为 0 的空字符串。比方下面的例子会宰割成["abc", "","", "","", "defg"]。因而咱们须要应用strings.Fields,函数签名如下func Fields(s string) []string。该函数能去除单词之间一个或多个的空格,返回字符串切片。应用下面的例子,会返回["abc","defg"],合乎咱们的要求。

如果有更多个性化的宰割需要,能够应用 strings.FieldsFunc,函数签名如下func FieldsFunc(s string, f func(rune) bool) []string,须要你写一个函数f。对于合乎f 函数的要求的一个或多个字符,都会被视为分隔符,而被宰割。上面正文的例子写得比较清楚,如果咱们还是要按空格宰割,就写一个匿名函数 func(c rune)bool{return c==' '},留神该函数的参数必须是rune 类型。

最初拼接字符串时,记得单词间要有空格,然而开端不要有空格。

func reverseWords(s string) string {s = strings.Trim(s, " ")
    words := strings.Fields(s)
    //words := strings.FieldsFunc(s, func(c rune) bool {
    //    return c==' '
    //})
    result := ""
    for i := len(words) - 1; i >= 0; i-- {result += words[i]
        if i != 0 {result += " "}
    }
    return result

}

手动实现双指针

手动实现双指针,须要注意边界问题,须要留神的点我都在正文下方写上了。首先咱们应用一个左右指针 l,r。去除首尾空格。留神不要让l 大于 r,否则会有异样,因而咱们对于l 指针的遍历,须要用 l<r 条件断定。而后的宰割操作。咱们应用两个指针 i,j,同时指向单词开端。先让i 跳过所有非空格,去到第一个空格,此时 s[i+1:j+1] 就是一个单词了,因而将此退出到列表中。随后让 i 继续前进,跳过所有空格,去到下一个单词的开端,同时让 j 跟上 i,也就j=i。这时就能够进入下一个循环了。当去到正序一个单词时,i 指针此时应该为 -1,在将正序第一个单词退出列表后,外层循环i>=0 会断定跳出。

最初拼接字符串时,记得单词间要有空格,然而开端不要有空格。

func reverseWords(s string) string {l,r:=0,len(s)-1
    for ;r>=0 && s[r]==' ';r--{}
    // 留神判断条件是 l <r,而非 l <len(s),后者在面对全空格字符串时会导致 l 大于 r
    for ;l<r && s[l]==' ';l++{}
    // 大部分语言的切片操作都是左闭右开,因而须要 r +1
    s=s[l:r+1]
    
    words:=make([]string,0)
    for i,j:=len(s)-1,len(s)-1;i>=0;{
        // 跳过非空格
        // 留神条件是 i >=0, 而非 i >0
        for ;i>=0 && s[i]!=' ';i--{}
        words=append(words,s[i+1:j+1])

        // 再跳过单词间的空格
        // 留神条件是 i >=0, 而非 i >0
        for ;i>=0 && s[i]==' ';i--{}
        j=i
    }
    result:=""
    for i,w:=range words{
        result+=w
        if i!=len(words)-1{result+=" "}
    }
    return result
}
退出移动版