字符串
字符串
  Go字符串
    Go 语言中的字符有2种
      uint8 类型（byte类型）
        代表 ASCII 码的一个字符
      rune类型（int32类型）
        代表一个 UTF-8 字符
        处理中文、日文或其他符合字符时需要用到 rune 类型
    字符串的遍历和修改
      遍历字符串时，看字符类型
        如果只有 ASCII 字符，如纯英文
          可以直接用 for i := 0; i < len(s); i++ { //byte } 遍历
以字节为单位
        如果字符串中有中文，遍历 UTF-8 字符
          使用 for range 遍历
for range 是以 Unicode 码点（rune）遍历字符串的
      修改字符串
        Go 语言中默认字符串只读，所以需要转成数组修改，再转回 string
        只有 ASCII 字符
          []byte(s) 再修改
        UTF-8 字符
          []rune(s) 再修改
  344.反转字符串
    题意
      原地修改数组，将字符串反转过来
    思路
      双指针法，for left < right {}，左右指针交换
        不要总是想到遍历一半数组，要经常想到 left < right 这个条件
      func reverseString(s []byte) {
left := 0
right := len(s) - 1
for left < right {
s[left], s[right] = s[right], s[left]
left++
right--
}
}
  541. 反转字符串II
    题意
      给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
      如果剩余字符少于 k 个，则将剩余字符全部反转。
      如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
    思路
      for 循环， 步长 2 * k，因为要找的是每 2*k 区间的起点
      总结下来需要反转的是，区间内的前k个字符，不足k个就全部反转
        reverse(s[i:i+k])
        reverse(s[i:len])
      func reverseStr(s string, k int) string {
ss := []byte(s)
len := len(ss)
for i := 0; i < len; i += 2*k {
if i + k <= len { // 1,2,3 k==2
// 反转 i ~ i+k （前k个），凑足k个反转
reverse(ss[i:i+k]) // 左闭右开
} else {
// 剩余的不足k个，剩下的都反转
reverse(ss[i:len])
}
}
return string(ss)
}
// reverse 函数即上一题的代码
  151.翻转字符串里的单词
    题意
      给定一个字符串，逐个翻转字符串中的每个单词。
      原地修改，空间复杂度要求 O(1)
    思路
      1. 去除多余空格，给单词间加空格（参考数组移除元素）
        单词间加空格
          // 单词间加上空格
if slow != 0 {
ss[slow] = ' '
slow++
}
        复制逻辑
          // 复制逻辑
for i < len(ss) && ss[i] != ' ' {
ss[slow] = ss[i]
slow++
i++
}
      2. 反转整个字符串
      3. 单独反转每个单词
        遍历到空格或字符串末尾时，操作底层数组来反转单词
        // 3. 反转每个单词
start := 0
for i := 0; i <= len(ss); i++ {
if i == len(ss) || ss[i] == ' ' {
reverse(ss[start:i])
// start 是单词的开头，而此时i指向空格或字符串末尾，i+1 才是下一个单词的开头
start = i + 1
}
}
  28. 实现 strStr()
    题意
      实现 strStr() 函数。
      给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
    KMP 算法
      主要思想
        当出现字符串不匹配时，可以知道一部分已经匹配的文本内容，从而避免从头重新做匹配
      前缀表（ next 数组）
        前缀
          必须包含第一个字母但不包含最后一个字母的连续子串
            aabaaf 的所有前缀：a; aa; aab; aaba; aabaa
        后缀
          必须包含最后一个字母但不包含第一个字母的连续子串
            aabaaf 的所有后缀：f; af; aaf; baaf; abaaf
            后缀也是从左往右读的，并非对称
        最长相等前后缀
          一个字符串的前缀集和后缀集中的最长相等字符串
        什么是前缀表？
          记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀的数组
          结果
        匹配过程/为什么要用前缀表
          不匹配时，前面的子串aabaa，后缀 aa 和前缀 aa 相等，aa 既是前缀又是后缀，下次匹配时前缀aa一定相等，就不用匹配了，直接从aa的下一位字符b开始匹配就OK了。
          这里就用到了前五位子串aabaa的最长相等前后缀的长度为2。
        前缀表计算方式
          长度为前1个字符的子串a，最长相等前后缀的长度为0。
          长度为前2个字符的子串aa，最长相等前后缀的长度为1。
          长度为前3个字符的子串aab，最长相同前后缀的长度为0
          结果
        构造 next 数组
          直接使用前缀表或整体右移
          视频资源
            1. 看完 https://www.bilibili.com/video/BV18k4y1m7Ar/
            2. 06:11 开始 https://www.bilibili.com/video/BV1AY4y157yL/?share_source=t=369
          本质上也使用了模式匹配，在不匹配时j需要移动到前一个字符对应的值
          // 前缀表无减一或者右移
// getNext 构造前缀表next
// params:
// next 前缀表数组
// s 模式串
func getNext(next []int, s string) {
j := 0
next[0] = j
for i := 1; i < len(s); i++ {
for j > 0 && s[i] != s[j] {
j = next[j-1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
}
        使用next数组来做匹配
          func strStr(haystack string, needle string) int {
n := len(needle)
if n == 0 {
return 0
}
j := 0
next := make([]int, n)
getNext(next, needle)
for i := 0; i < len(haystack); i++ {
for j > 0 && haystack[i] != needle[j] {
j = next[j-1] // 回退到j的前一位
}
if haystack[i] == needle[j] {
j++
}
if j == n {
return i - n + 1
}
}
return -1
}
  459.重复的子字符串
    题意
      给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
    暴力解法
      如果子串超过 len/2 则一定不是周期串
      如果子串不包含首位字符，一定不是周期串
        只用一个 for 循环判断子串结束位置即可
      l 末尾位置从索引1开始，substr := s[:l]
        检查 substr 之后的每一段是否和 substr 匹配
        s[i:i+l] != substr
      func repeatedSubstringPattern(s string) bool {
// 寻找子串，包含开头，结尾不超过中间，否则不可能由子串重复构成
n := len(s)
for l := 1; l <= n/2; l++ {
if n % l != 0 { // 必须整除，否则不可能由该子串重复构成
continue
}
substr := s[:l]
is_match := true
// 检查每一段是不是和 substr 相等
for i := l; i < n; i = i + l {
if s[i:i+l] != substr {
is_match = false
break
}
}
if is_match {
return true
}
}
return false
}
    双倍字符串法
      把字符串翻倍，掐头去尾，如果原字符串在其中，那么原字符串就是周期串 。
      func repeatedSubstringPattern(s string) bool {
// 如果2个s拼起来掐头去尾，可以在其中找到s，就说明s是周期串
t := s + s
return strings.Contains(t[1:len(t)-1], s)
}
    KMP算法
      如果一个字符串 s 是由重复子串组成，那么最长相等前后缀不包含的子串一定是字符串 s 的最小重复子串。
      func repeatedSubstringPattern(s string) bool {
// 求 next 数组
n := len(s)
next := make([]int, n)
j := 0
next[0] = j
for i := 1; i < n; i++ {
for j > 0 && s[j] != s[i] {
j = next[j-1]
}
if s[j] == s[i] {
j++
}
next[i] = j
}
// next[n-1] 是s最长相等前后缀的长度
if next[n-1] != 0 && n % (n - next[n-1]) == 0 {
return true
}
return false
}