单词间隔


单次——双指针

func findClosest(words []string, word1, word2 string) int {    ans := len(words)    index1, index2 := -1, -1    for i, word := range words {        if word == word1 {            index1 = i        } else if word == word2 {            index2 = i        }        if index1 >= 0 && index2 >= 0 {            ans = min(ans, abs(index1-index2))        }    }    return ans}func abs(x int) int {    if x < 0 {        return -x    }    return x}func min(a, b int) int {    if a > b {        return b    }    return a}

工夫复杂度：O(n)，其中 n 是数组words 的长度。须要遍历数组一次计算 word 1和word 2的最短距离，每次更新下标和更新最短距离的工夫都是 O(1)。这里将字符串的长度视为常数。

空间复杂度：O(1)。

屡次——哈希表

func findClosest(words []string, word1, word2 string) int {    ans:=len(words)    //存入哈希    m:=make(map[string][]int)    for i,word:=range words{        m[word]=append(m[word],i)    }    array1,array2:=m[word1],m[word2]    for _,i:=range array1{        for _,j:=range array2{            ans = min(ans, abs(i - j))        }    }    return ans}func abs(x int) int {    if x < 0 {        return -x    }    return x}func min(a, b int) int {    if a > b {        return b    }    return a}

因为测试用例只有43例，因而优化成果不显著

Z字形变换

func convert(s string, numRows int) string {    if numRows==1{return s}    res:=make([][]int32,numRows)    i,flag:=0,-1    for _,c:=range s{        res[i]=append(res[i],c)        if i==0||i==numRows-1{flag=-flag}        i+=flag    }    var ress string    for _,r:=range res{        ress=ress+string(r)    }    return ress}

模仿

func convert(s string, numRows int) string {    n, r := len(s), numRows    if r == 1 || r >= n {        return s    }    t := r*2 - 2    c := (n + t - 1) / t * (r - 1)    mat := make([][]byte, r)    for i := range mat {        mat[i] = make([]byte, c)    }    x, y := 0, 0    for i, ch := range s {        mat[x][y] = byte(ch)        if i%t < r-1 {            x++ // 向下挪动        } else {            x--            y++ // 向右上挪动        }    }    ans := make([]byte, 0, n)    for _, row := range mat {        for _, ch := range row {            if ch > 0 {                ans = append(ans, ch)            }        }    }    return string(ans)}作者：LeetCode-Solution链接：https://leetcode.cn/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode-solution-4n3u/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

优化

func convert(s string, numRows int) string {    r := numRows    if r == 1 || r >= len(s) {        return s    }    mat := make([][]byte, r)    t, x := r*2-2, 0    for i, ch := range s {        mat[x] = append(mat[x], byte(ch))        if i%t < r-1 {            x++        } else {            x--        }    }    return string(bytes.Join(mat, nil))}作者：LeetCode-Solution链接：https://leetcode.cn/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode-solution-4n3u/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。
func convert(s string, numRows int) string {    n, r := len(s), numRows    if r == 1 || r >= n {        return s    }    t := r*2 - 2    ans := make([]byte, 0, n)    for i := 0; i < r; i++ { // 枚举矩阵的行        for j := 0; j+i < n; j += t { // 枚举每个周期的起始下标            ans = append(ans, s[j+i]) // 以后周期的第一个字符            if 0 < i && i < r-1 && j+t-i < n {                ans = append(ans, s[j+t-i]) // 以后周期的第二个字符            }        }    }    return string(ans)}作者：LeetCode-Solution链接：https://leetcode.cn/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode-solution-4n3u/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。