反转字符串
344. 反转字符串 - 力扣（LeetCode）
将输入的字符串反转，要求不给另外的数组分配额外的空间，必须原地修改输入数组、使用O(1)的额外空间解决这一问题
双指针：指向首尾，每次交换，同时移动，直至相遇
1
2
3
4
5
6
7
8
|
func reverseString(s []byte) {
idx1, idx2 := 0, len(s)-1 // 俩指针分别指向首尾
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1] // 交换值
idx1++ // 后移
idx2-- // 前移
}
}
|
反转字符串 II
541. 反转字符串 II - 力扣（LeetCode）
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k 个，则将剩余字符全部反转。
- 如果剩余字符小于
2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
双指针：快指针遍历字符串，当快指针计数至2k或结束，慢指针指向这2k个字符的开头或剩余字符的开头，反转后，更新慢指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func reverseStr(s string, k int) string {
slowIdx := 0 // 慢指针指向首
sArr := []byte(s) // 字符串转为字符数组
for fastIdx := 0; fastIdx < len(sArr); fastIdx++ { // 快指针遍历数组
if (fastIdx+1)%(2*k) == 0 { // 计数至2k个字符
reverse(sArr[slowIdx : slowIdx+k]) // 反转这2k字符中的前k个字符
slowIdx = fastIdx + 1 // 更新慢指针
}
}
if len(sArr)-slowIdx < k { // 剩余字符少于k个
reverse(sArr[slowIdx:]) // 反转剩余全部字符
} else if len(sArr)-slowIdx >= k && len(sArr)-slowIdx < 2*k { // 剩余字符少于2k但大于或等于k个
reverse(sArr[slowIdx : slowIdx+k]) // 反转前k个字符
}
return string(sArr)
}
// 反转给定的字符串
func reverse(s []byte) {
idx1, idx2 := 0, len(s)-1 // 俩指针分别指向首尾
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1] // 交换值
idx1++ // 后移
idx2-- // 前移
}
}
|
优化：遍历字符串时每次前进2*k个字符，也就是到了下一个2k的第一个字符；进入循环后判断当前2k的第一个字符加上k个字符后是否超过数组长度，若没超过，则反转i开始的前k个字符，若超过了，反转i开始的全部字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func reverseStr(s string, k int) string {
sArr := []byte(s) // 将字符串转为字符数组
for i := 0; i < len(sArr); i += 2 * k { // 步进2*k
if i+k <= len(sArr) { // i加上k个字符后没超过数组长度
reverse(sArr[i : i+k]) // 反转i开始前k个字符
} else { // i加上k个字符后超过数组长度
reverse(sArr[i:]) // 反转i开始全部字符
}
}
return string(sArr)
}
func reverse(s []byte) {
idx1, idx2 := 0, len(s)-1
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1]
idx1++
idx2--
}
}
|
替换数字
54. 替换数字（第八期模拟笔试） (kamacoder.com)
给定一个字符串，包含小写字母和数字字符，要求将每个数字字符替换为number
开辟一个新的空间，遍历给定字符串，遇到字母就存入结果集，遇到数字就将number存入结果集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package main
import "fmt"
func main() {
var strByte []byte
fmt.Scanln(&strByte)
res := ""
for _, v := range strByte { // 遍历字符串
if v >= 'a' && v <= 'z' { // 遍历到小写字母
res += string(v) // 追加到结果集
} else { // 遍历到数字字符
res += "number"
}
}
fmt.Println(res)
}
|
反转字符串中的单词
151. 反转字符串中的单词 - 力扣（LeetCode）
给定一个字符串，用空格分隔字符串中的单词，给定的字符串中可能有前导空格、尾随空格或者单词间的多个空格。返回反转单词后的字符串，且单词间应当仅用单个空格分隔也不包含任何额外的空格
双指针：从后向前遍历给定字符串，一对指针确定一个单词，每遇到字母字符且慢指针指向非空格，则快慢指针就同时指向该字符，然后快指针继续向后遍历，直到遇到空格，将该单词存入结果集，慢指针指向空格，继续找下一单词；最后判断字符串首是否还有最后一个单词
注意：
s 包含英文大小写字母、数字和空格 ' '，数字也算单词- 在ASCII中0值最小，z值最大，0~z中包括所有大小写字符且不含空格，有特殊字符，但题目中说明不含特殊字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func reverseWords(s string) string {
slowIdx := len(s) - 1 // 慢指针初始指向数组尾
res := ""
for fastIdx := len(s) - 1; fastIdx >= 0; fastIdx-- { // 遍历字符串
if s[slowIdx] == ' ' && s[fastIdx] >= '0' && s[fastIdx] <= 'z' { // 慢指针指向空格且快指针指向字母
slowIdx = fastIdx // 更新慢指针指向单词头
} else if s[fastIdx] == ' ' && s[slowIdx] >= '0' && s[slowIdx] <= 'z' { // 快指针指向空格且慢指针指向字符
res += s[fastIdx+1 : slowIdx+1] // 单词存入结果集
res += " " // 加入单词间空格
slowIdx = fastIdx // 更新慢指针指向空格
}
}
if s[0] >= '0' && s[0] <= 'z' { // 字符串首还有字母
res += s[0 : slowIdx+1] // 单词存入结果集
} else { // 已存入全部单词
res = res[:len(res)-1] // 删除最后的空格
}
return res
}
|
右旋字符串
55. 右旋字符串（第八期模拟笔试） (kamacoder.com)
给定一个字符串和一个整数k，将字符串尾部k个字符移动到字符串首
先选定要移动的子串，然后字符串后移k个单位，再将选定子串放入字符串首
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package main
import "fmt"
func main() {
var k int
fmt.Scanln(&k)
var s []byte
fmt.Scanln(&s)
temp := make([]byte, k)
copy(temp, s[len(s)-k:len(s)]) // 保存要移动的子串
for i := len(s) - 1; i >= k; i-- { // 字符后移
s[i] = s[i-k]
}
for i := 0; i < k; i++ {
s[i] = temp[i]
}
fmt.Println(string(s))
}
|
找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
给定两个字符串，找出第二个字符串在第一个字符串中的下标，若没有则返回-1
暴力：外层遍历第一个字符串，若遇到字符与第二个字符串首字符相同，则继续比较后续字符，若遇到不一样的，则进入下一外层循环，若外层遍历结束仍未找到，返回-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func strStr(haystack string, needle string) int {
for i := 0; i <= len(haystack)-len(needle); i++ {
if haystack[i] == needle[0] { // 首字符相同
idx := i // 初始化指针指向字符串1的i
isOk := true // 默认匹配
for j := 0; j < len(needle); j, idx = j+1, idx+1 {
if haystack[idx] != needle[j] {
isOk = false // 不匹配
break
}
}
if isOk {
return i // 返回下标
}
}
}
return -1
}
|
- 时间复杂度：O(n × m)
- 空间复杂度：O(1)
KMP：在一个串中查找是否出现过另一个串
KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。next数组就是一个前缀表（prefix table），前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
为了清楚地了解前缀表的作用，举一个例子：要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf
文本串中第六个字符 b 和 模式串的第六个字符f不匹配了。如果是暴力匹配，此时模式串就要从头开始和文本串下一个字符匹配了，但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始与文本串第六个字符匹配，因为b之前的aa已经在上次匹配成功
模式串与前缀表对应位置的数字表示的就是：下标之前（包括下标）的字符串中，相同前后缀的长度，当不匹配时， 直接跳到前一个字符的前缀表的所存下标开始重新匹配
双指针构建next数组：俩指针分别指向前后缀末尾位置，初始一个指针指向模式串头，另一指针从模式串第二个元素开始遍历；若俩指针指向值相等，说明找到了相同的前后缀，则将前缀末尾指针后移一个，若俩指针指向值不同且前缀末尾指针不是指向字符串首，则前缀跳到前一个字符的前缀表的所存下标直到俩指针指向值相等或到字符串首；最后将当前前缀末尾下标赋值给后缀下标的next数组，进入下次循环，后缀末尾指针后移；
前后缀不匹配时，前缀要向前连续回退，回退到哪要看前一位的next数组的值（动态规划），只与前一个状态有关：
- 若不匹配，一直往前退到0或匹配为止
- 若匹配，则将之前的结果传递：因为之前的结果不为0时，前后缀有相等的部分，所以i所指的实际是与当前值相等的前缀，可视为将前缀从前面拖了过来，就不必将指针从前缀开始匹配了，所以之前的结果是可以传递的
求next数组的时候就是在用kmp，把 [0，1] 的前缀看成是模式串，把 [1，j] 的后缀看成是文本串，①文本串一直是每次循环+1，不会回退 ②模式串有时候可以通过next数组跳过前面几个字符直接比较，这两点就是kmp高效的地方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
func strStr(haystack string, needle string) int {
// 填充next数组
next := make([]int, len(needle))
i := 0 // 初始前缀末尾指针指向字符串首
for j := 1; j < len(needle); j++ { // 后缀末尾指针从第二个元素开始遍历
for i != 0 && needle[i] != needle[j] { // 俩指针指向值不同且前缀指针不在首
i = next[i-1] // 前缀指针回退
}
if needle[i] == needle[j] { // 俩指针指向值相等
i++ // 前缀指针前进
} // 若是前缀指针到首则不前进
next[j] = i // 前缀指针指向下标赋值给next数组
}
// 在z串中匹配模式串
i = 0 // i指向模式串首
for j := 0; j < len(haystack); j++ { // j指向主串
for i != 0 && haystack[j] != needle[i] { // 主串与模式串字符不相等
i = next[i-1] // 模式串指针回退
}
if haystack[j] == needle[i] { // 主串与模式串字符相等
i++ //模式串前进
}
if i == len(needle) { // 遍历完模式串
return j - len(needle) + 1 // 返回主串中匹配到的模式串首
}
}
return -1
}
|
- 时间复杂度：O(n+m)，n为文本串长度，m为模式串长度，匹配过程中文本串的遍历是没有回退过的，所以是O(n)，生成next数组需要遍历一遍模式串，所以时间复杂度是O(m)，综上整个KMP算法的时间复杂度是O(n+m)的
- 空间复杂度: O(m)
重复的子字符串
459. 重复的子字符串 - 力扣（LeetCode）
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成
暴力：若能被子串构成，则子串是从第一个字符开始的，且子串结束位置不大于中间位置，所以两层for循环，外层遍历获取子串的终止位置，内层遍历判断能否构成主串
注意：要记得判断最后剩余字符数不足以匹配子串的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func repeatedSubstringPattern(s string) bool {
for i := 0; i < len(s)/2; i++ { // i指向子串末尾,遍历到中间位置
isTrue := true // 默认该子串能构成主串
for j := i + 1; j < len(s); j += i + 1 { // j从第二个子串首开始遍历字符串,j每次前进子串长度
if len(s)-j < i || s[j:j+i+1] != s[:i+1] { // 子串与主串不匹配(包括最后剩余字符数不足以匹配)
isTrue = false // 该子串无法构成主串
break // 跳出循环,更新子串
}
}
if isTrue {
return true
}
}
return false
}
|