反转字符串
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
|
func strStr(haystack string, needle string) int {
i, j := 0, 0
for ; i <= len(haystack)-len(needle); i++ {
for j = 0; j < len(needle); j++ {
if haystack[i+j] != needle[j] {
break
}
}
if j == len(needle) {
return i
}
}
return -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
该讲解更易理解：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86
KMP：在一个串中查找是否出现过另一个串
KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。next数组就是一个前缀表（prefix table），前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
为了清楚地了解前缀表的作用，举一个例子：要在主串：aabaabaafa 中查找是否出现过一个模式串：aabaaf
主串中第六个字符 b 和模式串的第六个字符 f 不匹配了。如果是暴力匹配，此时模式串就要从头开始和主串起始的下一个字符匹配了，但如果使用前缀表，模式串就可以不从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始与主串第六个字符匹配，因为b之前的aa已经在上次匹配成功，主串也不会回退，直接从当前匹配不成功的地方继续比较
模式串与前缀表对应位置的数字表示的就是：下标之前（包括下标）的字符串中，相同前后缀的长度，当不匹配时， 模式串直接跳到前一个字符的前缀表的所存下标开始与当前主串字符重新匹配
双指针构建next数组：俩指针分别指向前后缀末尾位置，初始一个指针指向模式串头，另一指针从模式串第二个元素开始遍历；若俩指针指向值不同且前缀指针不是指向字符串首，则进入循环，前缀指针跳到前一个字符的next所存下标，直到俩指针指向值相等或前缀指向首；若是俩指针指向值相等，则前缀后移一个单位，再将后缀指向的next数组值置为前缀指针；若是前缀指向首，则直接将后缀指向的next数组值置为前缀指针(0)；最后将后缀指针向后移一个
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
}
|