算法题5.27 leetcode

单词距离
文章图片

单次——双指针

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字形变换 【算法题5.27】

文章图片

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）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。