这是算法记录的第七天，主要包含字符串简单操作
对应leetcode题目为151.344.541.剑指05.剑指58
344.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须 原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路
要求原地修改，可以使用左右指针往中间走（这里的r实际没动，r-l在动，r-l才相当于右指针），再对左右交换即可。
代码
// 左右指针
func reverseString(s []byte) {
r := len(s) - 1
for l := 0; l < len(s)/2; l++ {
//左右交换
s[l], s[r-l] = s[r-l], s[l]
}
}
541.反转字符串II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
思路
以步长为2k对字符串遍历，子串长度和k进行比较，若k小就反转前k个，若子串长度小就直接反转这个子串
代码
// 先把str转为切片可修改，然后以步长为2k对字符串遍历，反转前k个，若子串长度小于k了就直接反转这个子串
func reverseStr(s string, k int) string {
nums := []byte(s)
for i := 0; i < len(s); i += 2 * k {
var sub []byte
//找到更小的
if i+k < len(s) {
sub = nums[i : i+k]
} else {
sub = nums[i:len(s)]
}
//完成的是344.反转字符串的功能
for j, n := 0, len(sub); j < n/2; j++ {
sub[j], sub[n-j-1] = sub[n-j-1], sub[j]
}
}
return string(nums)
}
剑指05.替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
思路
直接遍历添加到新空间，遇到’ ‘换成’%20’就行
代码
// 对go来说，string不可变，没法原地修改，所以直接创建[]byte切片用于遍历接收，最后转为string返回
func replaceSpace(s string) string {
var str []byte
for i := 0; i < len(s); i++ {
if s[i] == ' ' {
str = append(str, '%', '2', '0')
} else {
str = append(str, s[i])
}
}
return string(str)
}
151.反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意： 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
思路一
对整个字符串先反转，再对每个单词反转。
思路二
按照顺序对每个单词进行截图，再倒着拼接。
代码
下面是思路二的代码
// 非数组遍历解法
func reverseWords(s string) string {
res := ""
for i := 0; i < len(s); {
word := ""
j := i
// 单词部分，遇到空格就结束
for j < len(s) && s[j] != ' ' {
j++
}
// 截取单词内容
word = s[i:j]
// 空格部分
for j < len(s) && s[j] == ' ' {
j++
}
// 排开串首串尾的空格部分并反转单词位置
if word != "" {
res = " " + word + res
}
// i移动到j的位置
i = j
}
// 第一个是空格排除去
return res[1:]
}
剑指II58.左旋转字符
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
思路
也是字符串的截取和拼接，下面是两种方式，一个是节省空间，一个是节省时间
代码
func reverseLeftWords(s string, n int) string {
//空间少
return s[n:] + s[:n]
}
//+操作的拼接效率低
func reverseLeftWords(s string, n int) string {
//速度快
nums := []byte(s)
left := nums[0:n]
nums = append(nums, left...)
return string(nums[n:])
}
总结
这一部分都相对简单，算是后面KMP算法的缓冲。对于细节来说，需要注意语言特性，以及需要避免越界情况。