反转字符串

1
2
3
4
5
6
7
8
9
10
func reverseString(s []byte)  {
    len := len(s)
    left , right := 0 , len-1 
    for left < right {
        s[left],s[right] = s[right],s[left]
        left ++ 
        right -- 
    }
}
// 双指针

反转字符串2

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func reverseStr(s string, k int) string {
    t := []byte(s)
    for i := 0; i < len(s); i += 2 * k {
        sub := t[i:min(i+k, len(s))]
        for j, n := 0, len(sub); j < n/2; j++ {
            sub[j], sub[n-1-j] = sub[n-1-j], sub[j]
        }
    }
    return string(t)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

替换数字

​ 给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

1
2
3
4
5
6
7
8
9
10
11
func replaceNumbers(s string) string {
	var result string
	for _, char := range s {
		if char >= '0' && char <= '9' {
			result += "number"
		} else {
			result += string(char)
		}
	}
	return result
}

反转字符串中的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

思路

  1. 去除重复的空格（重点）
  2. 将整个字符串倒序
  3. 从头到尾将每个单词倒序
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func reverseWords(s string) string {
    b := []byte(s)

    // 移除前面、中间、后面存在的多余空格
    slow := 0
    for i := 0; i < len(b); i++ {
        if b[i] != ' ' {
            if slow != 0 {
                b[slow] = ' '
                slow++
            }
            for i < len(b) && b[i] != ' ' { // 复制逻辑
                b[slow] = b[i]
                slow++
                i++
            }
        }
    }
    b = b[0:slow]
    
    // 翻转整个字符串
    reverse(b)
    // 翻转每个单词
    last := 0
    for i := 0; i <= len(b); i++ {
        if i == len(b) || b[i] == ' ' {
            reverse(b[last:i])
            last = i + 1
        }
    }
    return string(b)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

这里的 快慢指针 来 解决重复空格的思路很奇特，我想了好久

具体可以看 数组中 移除元素 的那题

当然这道题的难点还是 处理空间复杂度为 O(1)

右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

必须 空间复杂度为O（1）

思路

这里的思路可以用到上面那一题的思路

  1. 先将所有字符串倒序一遍
  2. 再把局部的字符串倒序一遍
1
2
3
4
5
strByte := []byte(str)

reverse(strByte, 0, len(strByte) - 1)
reverse(strByte, 0, target - 1)
reverse(strByte, target, len(strByte) - 1)

实现strStr()

​ 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

O(n*n)的算法我就不展示了

KMP实现

为了理解KMP我花了一个晚上，这个东西好绕啊

  • 匹配过程 —->保存之前已经匹配过的
  • 制作next数组 —–> 前后缀相同

前缀和后缀

abcdefgz 中

前缀：

a ，ab ，abc ，…..以第一个数字

后缀：

若以d 为后缀最后一个数字

d , cd , bcd , a

当然从左往右遍历的时候，后缀可以取很多字符

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 方法二: 前缀表无减一或者右移

// getNext 构造前缀表next
// params:
//		  next 前缀表数组
//		  s 模式串
// 制作 next 数组
// i 是后缀表示
// j 是前缀表示
func getNext(next []int, s string) {
	j := 0  // 可以是0，-1都可以，表示方法不同而已
	next[0] = j  // 第一个元素为0 ， 有些表示层-1
	for i := 1; i < len(s); i++ { //直接从数组第二个元素开始计算
		for j > 0 && s[i] != s[j] {
			j = next[j-1] 		// 前后缀不相同时
		} //其实看这个代码的过程不难发现，这个制作next 数组的过程也有点像下面匹配字符串的过程，不过这里匹配的时候需要使用循环，旨在知道（虽然我第i个字符是不匹配的，但是我第i个前的字符串有多少是匹配的，而j是前缀表示，同时也表示着前缀的长度，也就是匹配到的数组长度） 
		if s[i] == s[j] {	      // 前后缀相同时
			j++
		}
		next[i] = j  // 赋值
	}
}

// 若第n个字符不同，则判断第n个字符前 相邻的字符串有多长是与主串相同的
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  // 返回index
		}
	}
	return -1  // 失败
}

其实我现在也有点蒙蔽，记住就行。。。下次碰到可能就会了

参考：

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

记得看代码随想录中的两个视频

图示非常清楚

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

1
2
3
>输入: s = "abab"
>输出: true
>解释: 可由子串 "ab" 重复两次构成。

直接用KMP 的next 数组函数求解

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
// 前缀表（不减一）的代码实现
func repeatedSubstringPattern(s string) bool {
	n := len(s)
	if n == 0 {
		return false
	}
	j := 0
	next := make([]int, n)
	next[0] = j
	for i := 1; i < n; i++ {
		for j > 0 && s[i] != s[j] {
			j = next[j-1]
		}
		if s[i] == s[j] {
			j++
		}
		next[i] = j
	}
	// next[n-1]  最长相同前后缀的长度
    //n%(n-next[n-1]) == 0 -- 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环
	if next[n-1] != 0 && n%(n-next[n-1]) == 0 {
		return true
	}
	return false
}

这里唯一有点巧妙的是，如何判断周期循环

n%(n-next[n-1]) == 0

总结

到此，字符串的章节就刷完了，明天休息一天

去写一下短链系统

后天开始双指针的写法