[Go版]算法通关村第十二关黄金——字符串冲刺题

题目：最长公共前缀

题目链接：LeetCode-14. 最长公共前缀

解法1：纵向对比-循环内套循环写法

以第一个子字符串为标准，遍历其每个字符时，内嵌遍历其余子字符串的对应字符是否一致。不一致时，则返回当前字符之前的子字符串。

复杂度：时间复杂度$O(n\ast m)$、空间复杂度$O(1)$

• 时间复杂度：其中 n 是字符串平均长度，m 是字符串数组的长度。

Go代码

func longestCommonPrefix(strs []string) string {length := len(strs)if length==1 {return strs[0]}chlen := len(strs[0])for i:=0; i<chlen; i++ {// 用第一个子字符串的字符作为比较ch := strs[0][i]for j, v := range strs {if j == 0 {continue}// 子字符串的长度比第一个短 或者 出现比较字符不同if i == len(v) || v[i] != ch {return string(strs[0][:i])}}}return strs[0]
}

解法2：横向对比-两两对比（类似合并K个数组、合并K个链表）

1. 先让前两个子字符串对比得到公共前缀
2. 再将此公共前缀作和下一个子字符串对比得到公共前缀
3. 如此循环到末尾，返回最后的公共前缀即可
4. 优化：遍历过程中如果公共前缀已经是空字符串了，则可直接返回空字符串。

相比于解法1的优点：将逻辑分解到两个函数中，使代码更加模块化和可维护。

复杂度：时间复杂度$O(n\ast m)$、空间复杂度$O(1)$

• 时间复杂度：其中 n 是字符串平均长度，m 是字符串数组的长度。

Go代码

func longestCommonPrefix(strs []string) string {length := len(strs)if length == 1 {return strs[0]}str := strs[0]for i:=1; i<length; i++ {str = getCommonPrefix(str, strs[i])if str == "" {return ""}}return str
}func getCommonPrefix(str1, str2 string) string {length2 := len(str2)for i, v := range str1 {val := byte(v)if i == length2 || val != str2[i] {return string(str1[:i])}}return str1
}

题目：压缩字符串

题目链接：LeetCode-443. 压缩字符串

解法1：读写指针 + 次数统计 + 顺向思维处理次数输出

1. 安排读写指针，分别指向要写的位置，和读的位置，两指针首先指向第一个字符

2. 如果是相同时最后一个元素的标记，或者 读指针的字符和写指针不同时：

   1. 统计总次数，区分是否 >1
      • 大于1：区分是否 >= 10
        • 小于10：仅追加一个数字
        • 大于10：不断除10，得到可除次数，和除10的最后余数
          1. 追加最后余数
          2. 遍历可除次数，追加数值0
          3. 根据可除次数，用总次数除了10的可除次数次方，得到余数，追加余数
   2. 如果是相同时最后一个元素的标记，到这里直接返回写指针+1即可
   3. 更新对比字符为当前字符，追加对比字符
   4. 总次数还原为1，读指针++
   5. 如果是最后一个元素，到这里直接返回写指针+1即可

3. 相同时，总次数++

   • 如果是最后一个元素，添加标记（这里只为加上其相同次数）

复杂度：时间复杂度$O(n)$、空间复杂度$O(1)$

Go代码

func compress(chars []byte) int {length := len(chars)if length == 0 || length == 1 {return length}left, right := 0, 1 // left写 right读num := 1    //次数统计ch := chars[0]lastone := falsefor lastone || right < length {if lastone || chars[right] != chars[left] {// 追加长度if num > 1 {// 要追加多个长度if num >= 10 {tmpnum := numcount10 := 1// 明确有几个10for tmpnum >= 10 {tmpnum = tmpnum/10if tmpnum >= 10 {count10++}}// 追加大于10的首个数字left++chars[left] = byte(tmpnum + '0')   for i:=1; i<count10; i++ {// 补零left++chars[left] = '0'}// 追加大于等于10时的余数f10 := math.Pow(10, float64(count10))yu := num % int(f10)if yu >= 0 {left++chars[left] = byte(yu + '0')}} else {    //只追加一个长度left++chars[left] = byte(num + '0')}}if lastone {return left+1}ch = chars[right]// 追加新字符left++chars[left] = chnum = 1right++// 如果是最后一个元素if right == length {return left+1}} else {num++right++if right == length {lastone = true}}}return left+1
}

解法2：读写起始三指针 + 逆向思维处理次数输出（优化解法1）

优化点：

1. 无需用变量循环时累加统计总次数：让一个起始指针指向当前统计字符的首位置，当遍历到该字符末尾时，尾索引-首索引+1=总次数。
2. 将正向计算追加>10时的最后余数、可除10次数、余数改为：追加依次除10得到的余数，最后反转该段数字区间即可。
3. 读指针和下一个不同时处理当前，此时包含了最后一个字符的场景。解法1中读指针和写指针不同时处理的逻辑就没法包含最后一个字符，需要考虑最后一个字符时是和之前一致还是不同的情况。

复杂度：时间复杂度$O(n)$、空间复杂度$O(1)$

Go代码

func compress(chars []byte) int {length := len(chars)if length == 0 || length == 1 {return length}left, right, start := 0, 0, 0for ; right < length; right++ {if right == length-1 || chars[right] != chars[right+1] {chars[left] = chars[right]left++count := right-start+1site := leftif count > 1 {for count > 0 {n := count%10chars[left] = byte(n + '0')left++count = count/10}reverse(chars, site, left-1)}start = right+1}}return left
}
func reverse(chars []byte, left int, right int) {if left >= right {return}for left <= right {chars[left], chars[right] = chars[right], chars[left]left++right--}
}