【算法刷题系列】第9天 151. 反转字符串中的单词, 55. 右旋字符串, 459. 重复的子字符串
Overview
学习内容
学习文档
-
字符串总结：这篇文档总结了字符串相关的常用操作和处理方法。特别是如何高效地使用
substr、split、reverse等库函数处理字符串问题。它还包含了各种算法的讨论，例如 KMP 算法如何处理字符串匹配问题，具体可以参考 KMP 模式匹配的高效实现。 -
双指针总结：双指针是一种常见且高效的算法思路，尤其在处理字符串和链表问题时特别有效。文档详细介绍了双指针在解决问题中的应用场景，如链表反转、寻找和计算字符串中的特定内容、左右边界的处理等。这个方法也经常用于简化两个嵌套的循环，使时间复杂度从 O(n^2) 降到 O(n)。
收获总结
-
字符串是一种特殊的数组，有限字符序列： 字符串本质上就是一系列字符的集合，因此在很多算法问题中，可以将字符串当作数组来处理。字符串相关的操作，如查找、分割、拼接等，本质上与数组操作有相似之处。学会理解这一点，可以让我们在处理字符串问题时更加灵活和高效。
-
substr、split、reverse 等库函数在 Golang 里的简单使用：
substr用于提取字符串的子串。split用于将字符串按照指定的分隔符进行切分。reverse用于将字符串或字符数组进行反转。掌握这些函数能够帮助我们处理很多字符串问题，尤其是在需要对字符串进行拆分、拼接或翻转操作时，简化代码的编写。
-
双指针在处理字符串问题时的应用： 双指针技术经常用于字符串处理问题，如字符串的反转、查找重复字符、判断回文串等。通过设置两个指针从字符串的不同端开始遍历，可以有效减少遍历次数并提升效率。双指针的典型应用包括：
- 字符串反转 为例：我们可以定义两个指针，分别指向字符串的第一个和最后一个字符。在循环中，交换这两个位置的字符，然后同时移动两个指针，一个向右，一个向左，直到它们相遇或交错为止。这个方法能在 O(n) 的时间内完成反转。
- 字符串填充 问题。如果需要在字符串中插入填充内容，比如插入空格或其他字符，我们可以先根据填充后的最终长度对数组进行扩容，然后使用双指针从末尾向前操作。一个指针从原字符串的最后一个字符开始，另一个指针从扩容后的新位置开始，逐步进行字符的移动和填充，这样避免了额外的多次遍历。
- 反转链表，我们使用两个指针，
prev和curr，分别指向当前节点和前一个节点。通过将当前节点的next指针指向前一个节点，实现局部反转。然后依次更新指针，直到遍历完整个链表，从而在一次遍历中完成链表的反转。 - n 数之和（如 Two Sum 问题）同样可以通过双指针技术来解决。首先将数组排序，然后定义两个指针，分别指向数组的首尾。通过计算这两个指针所指元素的和，根据结果移动指针：如果和小于目标值，则移动左指针以增大和；如果和大于目标值，则移动右指针以减小和。这样可以在 O(n) 的时间内找到所有满足条件的组合。
-
反转系列问题：先局部后整体或先整体后局部的应用： 字符串或数组的反转问题通常可以分为两类：
- 先局部反转再整体反转：这种方法适用于需要反转某个特定区间的内容，然后对整体内容进行反转的情况。
- 先整体反转再局部反转：用于整体反转之后需要再对局部的特定段进行细化处理。比如字符串旋转的操作可以通过这种方式来实现。
-
KMP 算法的学习与理解： KMP 算法是一种用于解决字符串匹配问题的高效算法。KMP 的核心思想在于避免重复匹配，通过构建
next数组，预处理模式串来记录前缀与后缀的匹配情况，使得在遇到不匹配时可以通过next数组快速跳过不必要的字符，减少回溯次数。掌握 KMP 算法不仅能够提升匹配效率，而且对于理解复杂字符串问题具有重要意义。
1// 计算next数组
2func computeNext(pattern string) []int {
3 m := len(pattern)
4 next := make([]int, m)
5 j := 0
6
7 next[0] = 0 // 修改为0
8
9 for i := 1; i < m; i++ {
10 // 如果不匹配，回退到上一个可能的匹配点
11 for j > 0 && pattern[i] != pattern[j] {
12 j = next[j-1]
13 }
14 // 如果匹配，j递增
15 if pattern[i] == pattern[j] {
16 j++
17 }
18 next[i] = j // 记录前缀长度，而不是j - 1
19 }
20
21 return next
22}
执行模式匹配:
- 遍历主串中的每个字符。
- 如果主串字符与模式串当前指针指向的字符不匹配，使用next数组来跳过已经匹配过的部分，避免重复比较。
- 如果字符匹配，移动模式串的指针。
- 如果模式串的指针达到模式串的末尾，说明找到了一个匹配，将匹配的位置记录下来。
- 使用next数组中的值来更新模式串的指针，继续搜索。（optional）
1// kmpSearch
2func kmpSearch(text, pattern string) int {
3 n, m := len(text), len(pattern)
4 if m == 0 || n == 0 || m > n {
5 return -1 // 如果模式串为空或主串为空，或模式串比主串长，则没有匹配
6 }
7
8 next := computeNext(pattern) // 计算模式串的next数组
9 j := 0 // 模式串的指针
10
11 for i := 0; i < n; i++ { // 遍历主串
12 // 当出现不匹配时，使用next数组跳过已经匹配过的部分
13 for j > 0 && text[i] != pattern[j] {
14 j = next[j] + 1
15 }
16 // 如果字符匹配，移动模式串的指针
17 if text[i] == pattern[j] {
18 j++
19 }
20 // 如果模式串完全匹配
21 if j == m {
22 return i - m + 1 // 返回第一个匹配的位置
23 }
24 }
25
26 return -1 // 如果没有找到匹配，返回-1
27}
- 传递左右边界的重要性: 显示传递左右边界vs切片方式左闭右开, 是有区别的。在处理字符串问题时，显示传递左右边界可以更好地控制边界条件，避免出现越界问题。这种方式在处理字符串反转、局部替换等问题时尤为重要。
题目解析
题目1：151. 反转字符串中的单词
题目描述： 给定一个字符串，要求将字符串中的单词顺序颠倒，并去除多余的空格。单词之间用单个空格分隔，返回处理后的字符串。
示例：
输入: "the sky is blue"
输出: "blue is sky the"
解法总结：
- 使用双指针技术去除多余的空格，包括开头和结尾，以及中间相邻的多个空格。
- 对整个字符串进行一次反转。
- 对反转后的字符串中的每个单词进行单独的局部反转，最终得到正确的顺序。
-
代码实现:
1func reverseWords(s string) string { 2 ss := []byte(s) 3 4 // 1. 去除多余空格 5 slow := 0 6 fast := 0 7 n := len(ss) 8 9 // 去掉开头的空格 10 for fast < n && ss[fast] == ' ' { 11 fast++ 12 } 13 14 for ; fast < n; fast++ { 15 if fast > 0 && ss[fast] == ' ' && ss[fast-1] == ' ' { 16 continue 17 } 18 ss[slow] = ss[fast] 19 slow++ 20 } 21 22 // 去掉结尾的空格 23 if slow > 0 && ss[slow-1] == ' ' { 24 slow-- 25 } 26 27 // 截取有效部分 28 ss = ss[:slow] 29 30 // 2. 整体反转 31 reverse(ss) 32 33 // 3. 单词局部反转 34 start := 0 35 for i := 0; i <= len(ss); i++ { 36 // 遇到空格或者到达字符串末尾时反转单词 37 if i == len(ss) || ss[i] == ' ' { 38 reverse(ss[start:i]) 39 start = i + 1 40 } 41 } 42 43 return string(ss) 44} 45 46// 反转 []byte 数组 47func reverse(s []byte) { 48 left := 0 49 right := len(s) - 1 50 for left < right { 51 s[left], s[right] = s[right], s[left] 52 left++ 53 right-- 54 } 55}
时间复杂度：O(n)，因为每个字符最多被访问两次，整体和局部反转都是线性的。
空间复杂度：O(1)，只需要使用常数级别的额外空间存储指针位置。
题目2：55. 右旋字符串
题目描述： 给定一个字符串，要求将其右旋指定次数。旋转的操作是将字符串的后面部分移动到前面。
示例：
输入: n = 2, str = "abcdefg"
输出: "fgabcde"
解法总结：
- 先对整个字符串进行一次整体反转。
- 对旋转点前后分别进行局部反转，这样可以达到右旋的效果。
- 旋转次数
n可能大于字符串的长度，因此需要对n进行取模运算来保证旋转次数合法。
-
代码实现:
1package main 2 3import ( 4 "fmt" 5) 6 7func reverse(s []byte, l, r int) { 8 for l < r { 9 s[l], s[r] = s[r], s[l] 10 l++ 11 r-- 12 } 13} 14 15func main() { 16 var n int 17 fmt.Scanln(&n) 18 19 // 读取输入字符串 20 var str string 21 fmt.Scanln(&str) 22 23 // 将字符串转换为字节数组 24 strByte := []byte(str) 25 26 // 1. 整体反转 27 reverse(strByte, 0, len(strByte)-1) 28 29 // 边界条件，防止 n 大于或等于字符串长度 30 if n > len(strByte) { 31 n = len(strByte) 32 } 33 34 // 2. 局部反转 35 reverse(strByte, 0, n-1) 36 reverse(strByte, n, len(strByte)-1) 37 38 // 输出结果 39 fmt.Println(string(strByte)) 40}
时间复杂度：O(n)，因为每次反转操作都需要遍历整个字符串。
空间复杂度：O(1)，只使用了额外的几个变量来记录边界信息。
题目3：459. [重复的子字符串](459. 重复的子字符串)
题目描述： 给定一个非空字符串，判断该字符串是否可以通过它的一个子串重复若干次构成。
示例：
输入: "abab"
输出: true
解释: "abab" 是由 "ab" 重复两次构成的。
解法总结：
通过 KMP 算法计算字符串的 next 数组。next[len(s)-1] 的值表示最长相同前后缀的长度。如果字符串的长度减去最长前后缀长度能够整除整个字符串长度，则该字符串是由一个子串重复多次构成的。
-
代码实现:
1func repeatedSubstringPattern(s string) bool { 2 if len(s) == 0 { 3 return false 4 } 5 6 // 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。 7 next := computeNext(s) 8 if next[len(s)-1] != 0 && (len(s)%(len(s)-next[len(s)-1]) == 0) { 9 return true 10 } 11 12 return false 13} 14 15func computeNext(pattern string) []int { 16 m := len(pattern) 17 next := make([]int, m) 18 j := 0 19 20 next[0] = 0 // 修改为0 21 22 for i := 1; i < m; i++ { 23 // 如果不匹配，回退到上一个可能的匹配点 24 for j > 0 && pattern[i] != pattern[j] { 25 j = next[j-1] 26 } 27 // 如果匹配，j递增 28 if pattern[i] == pattern[j] { 29 j++ 30 } 31 next[i] = j // 记录前缀长度，而不是j - 1 32 } 33 34 return next 35}
时间复杂度：O(n)，KMP 算法的时间复杂度为线性时间。
空间复杂度：O(n)，需要额外的 next 数组来记录前缀信息。