【算法刷题系列】第8天 344. 反转字符串, 541. 反转字符串 II, 54. 替换数字（第八期模拟笔试）
Overview
学习内容
收获总结
-
字符串和字节数组的转换：在 Go 语言中，字符串是不可变的。对于需要修改字符串的操作，如反转、替换等，我们通常会先将字符串转换为
[]byte类型。这是因为[]byte是可变的，可以通过索引操作直接修改其内容。在许多字符串操作中，将字符串转换为字节数组是一个有效的优化策略，尤其是在需要大量的字符替换和处理时，这种转换能够提高性能和代码的可读性。 -
unicode.IsDigit和rune的用法：在处理字符串中数字字符时，使用unicode.IsDigit函数来判断字符是否为数字非常便捷。unicode.IsDigit适用于所有 Unicode 字符，能够处理多字节字符，如中文或特殊字符。而rune是 Go 语言中用于表示 Unicode 码点的类型，它可以存储多字节字符。因此，在处理包含不同字符集的字符串时，理解rune和unicode.IsDigit的作用，可以让我们编写的代码更具通用性和健壮性。 -
从后向前替换字符的技巧：当处理需要对字符进行替换且替换后长度不同的情况时（例如将单个数字字符替换为多个字符），先扩展数组的长度，然后从后向前进行替换操作。这种方式能够有效避免字符替换过程中覆盖未处理的部分，保证替换操作的正确性。在替换操作时，提前计算所需的最终数组长度，并从末尾倒序进行填充，能够让操作更为高效，也避免了不必要的内存分配。
题目解析
题目1：344. 反转字符串
-
题目描述：
给定一个字符数组s，请你将该字符数组原地反转。要求算法的空间复杂度为 O(1)，也就是说必须在原数组上进行修改，而不借助额外的空间。 -
示例：
- 输入：
["h", "e", "l", "l", "o"] - 输出：
["o", "l", "l", "e", "h"]
- 输入：
-
解法说明：
本题的最佳解决方法是使用双指针法。我们从数组的头尾两端分别设立两个指针，一个指向数组的第一个元素（left），另一个指向最后一个元素（right）。然后通过不断交换left和right所指向的元素，left逐渐向右移动，right逐渐向左移动，直到两个指针相遇或交错。这样便完成了原地反转操作，且没有额外的空间开销。这种方法非常简洁，且利用了数组的特性，使得反转操作只需遍历一遍数组即可完成，非常高效。
-
代码实现:
1func reverseString(s []byte) { 2 // 对撞双指针反转法 3 left := 0 4 right := len(s) - 1 5 6 for left < right { 7 s[left], s[right] = s[right], s[left] 8 left++ 9 right-- 10 } 11} -
复杂度说明：
时间复杂度为 O(n)，其中 n 是数组的长度。每个元素被访问和交换一次，因此遍历的时间复杂度是线性的。
空间复杂度为 O(1)，因为我们是在原数组上进行操作，未使用任何额外的空间。
题目2：541. 反转字符串 II
-
题目描述：
给定一个字符串s和一个整数k，请将字符串按照以下规则进行反转：- 每隔 2k 个字符，反转前 k 个字符。
- 如果剩余字符少于 k 个，则将所有剩余字符反转。
- 如果剩余字符多于 k 个但少于 2k 个，则只反转前 k 个字符，其余字符保持不变。
-
示例：
- 输入：
s = "abcdefg",k = 2 - 输出：
"bacdfeg"
- 输入：
-
解法说明：
该题的核心是按照每 2k 个字符为一组，反转其中的前 k 个字符。为了实现这一点，首先我们需要将字符串转换为可修改的[]byte，然后按照步长为 2k 进行遍历。在每个 2k 的区间内，判断当前剩余的字符数：- 如果该区间的字符数大于或等于 k，则对前 k 个字符进行反转。
- 如果剩余字符少于 k 个，则将所有剩余字符反转。 最终处理完所有区间后，将字节数组重新转换为字符串并返回。
这种解法灵活地处理了各种剩余字符的情况，同时通过局部反转，达到了题目的要求。反转操作依旧使用双指针法，因此时间复杂度不会过高。
-
代码实现:
1func reverseStr(s string, k int) string { 2 ss := []byte(s) 3 4 // 同样使用对撞双指针，只不过逻辑上往前移动2k个，前k个反转；还要考虑怎么收尾处理问题 5 for i := 0; i < len(s); i += 2 * k { 6 // 1. 如果还可以往前走k个，则反转前k个 7 if i+k <= len(s)-1 { 8 reverseFunc(ss[i : i+k]) 9 } else { 10 // 2. 其他情况反转全部 11 reverseFunc(ss[i:]) 12 } 13 } 14 return string(ss) 15} 16 17func reverseFunc(s []byte) { 18 start := 0 19 end := len(s) - 1 20 21 for start < end { 22 s[start], s[end] = s[end], s[start] 23 start++ 24 end-- 25 } 26} -
复杂度说明：
时间复杂度为 O(n)，其中 n 是字符串的长度。由于我们每次以 2k 为单位进行遍历并在部分区间内进行反转，整体上所有字符的操作次数是线性的。
空间复杂度为 O(n)，因为我们将字符串转换为了字节数组，这个转换过程需要额外的空间来存储新的字节数组。
题目3：54. 替换数字（第八期模拟笔试）
-
题目描述：
给定一个包含数字和字母的字符串，将其中的每个数字字符替换为字符串 "rebmun"。例如，字符串"a1b2c3"中的数字 1、2、3 分别替换为 "rebmun"，结果是"arebmubrebmuncrebmun"。 -
示例：
- 输入：
"a1b2c3" - 输出：
"arebmubrebmuncrebmun"
- 输入：
-
解法说明：
这道题目要求我们对字符串中的每一个数字字符进行替换。我们可以先遍历整个字符串，统计其中数字字符的个数。然后，根据数字字符的个数，扩展数组的长度，为每个数字字符替换为 "rebmun" 预留足够的空间。
接着，我们使用倒序遍历字符串的方式进行替换操作：从字符串的末尾开始，遇到数字字符时，将其替换为 "rebmun"。如果遇到非数字字符，则将其原样放回。这种从后往前替换的方式能够避免覆盖未处理的字符，保证替换过程的正确性。该解法的关键在于对数组的扩展和倒序替换。扩展数组是为了避免频繁的内存分配，而倒序替换则能够确保每个字符都能得到正确的处理，特别是在原地替换的场景中。
-
代码实现:
1package main 2 3import ( 4 "fmt" 5 "unicode" 6) 7 8func replaceNumber(ss []byte) []byte { 9 // 1. 统计数字字符的个数 10 count := 0 11 for _, i := range ss { 12 if unicode.IsDigit(rune(i)) { 13 count++ 14 } 15 } 16 17 // 2. 扩充原切片大小 18 expandedSize := len(ss) + count * 5 // 每个数字替换成 "rebmun"，长度为 5 19 ss = append(ss, make([]byte, count*5)...) // 扩展原始切片大小 20 21 // 3. 从后往前替换 22 newindex := expandedSize - 1 23 oldindex := len(ss) - count*5 - 1 24 25 for oldindex < newindex { 26 if unicode.IsDigit(rune(ss[oldindex])) { 27 // 替换数字为 "rebuman" 28 ss[newindex-5] = 'n' 29 ss[newindex-4] = 'u' 30 ss[newindex-3] = 'm' 31 ss[newindex-2] = 'b' 32 ss[newindex-1] = 'e' 33 ss[newindex] = 'r' 34 newindex -= 6 35 } else { 36 ss[newindex] = ss[oldindex] 37 newindex-- 38 } 39 oldindex-- 40 } 41 42 return ss 43} 44 45func main() { 46 var str string 47 fmt.Scanln(&str) 48 49 strByte := []byte(str) 50 newString := replaceNumber(strByte) 51 52 fmt.Println(string(newString)) 53} -
复杂度说明：
时间复杂度为 O(n)，其中 n 是字符串的长度。我们需要遍历整个字符串两次：第一次用于统计数字字符的个数，第二次用于从后向前进行替换操作。因此时间复杂度是线性的。
空间复杂度为 O(n)，因为我们需要扩展数组的大小来存储替换后的字符串，并且扩展后的数组长度与原字符串成正比。