344.反转字符串
# 示例 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"]
使用双指针法定义两个指针,分别指向字符串开头和结尾,两个指针同时向中间移动,并交换元素。
func ReverseString(s []byte) {
//双指针
left := 0
right := len(s) - 1
// 循环的条件还可以写成 for left < right {}
for i := 0; i < len(s)/2; i++ {
s[left], s[right] = s[right], s[left]
left++
right--
}
}
512.反转字符串Ⅱ
给定一个字符串 s
和一个整数 k
,从字符串开头算起,每计数至 2k
个字符,就反转这 2k
字符中的前 k
个字符。
如果剩余字符少于
k
个,则将剩余字符全部反转。如果剩余字符小于
2k
但大于或等于k
个,则反转前k
个字符,其余字符保持原样
# 示例 1:
输入:s = "abcdefg", k = 2
输出:"bacdfeg"
# 示例 2:
输入:s = "abcd", k = 2
输出:"bacd"
func ReverseStr(s string, k int) string {
// 将s转换为byte类型的切片
ss := []byte(s)
length := len(s)
// 字符串每次2k个移动
for i := 0; i < length; i += 2 * k {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
// sasakura
if i+k <= length {
reverse(ss[i : i+k])
} else {
reverse(ss[i:length])
}
}
return string(ss)
}
// 反转操作
func reverse(str []byte) {
left := 0
right := len(str) - 1
for left < right {
str[left], str[right] = str[right], str[left]
left++
right--
}
}
05.替换空格
剑指 Offer 05. 替换空格 - 力扣(LeetCode)
# 示例 1:
输入:s = "We are happy."
输出:"We%20are%20happy.
这个写法会新开辟两个内存空间
ss : 将 string 转换为 byte 类型的切片的空间
result : 最后返回的切片
func replaceSpace(s string) string {
// 将string转换为byte类型的切片
ss := []byte(s)
result := make([]byte, 0)
for key, value := range ss {
if value == ' ' {
result = append(result, []byte("%20")...)
} else {
result = append(result, ss[key])
}
}
return string(result)
}
双指针写法 : 只开一个内存空间
思路:
开始先计算空格的数量 , 根据空格的数量来扩充新切片
151.翻转字符串里的单词
给你一个字符串 s
,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s
中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意:输入字符串
s
中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
# 示例 1:
输入:s = "the sky is blue"
输出:"blue is sky the"
# 示例 2:
输入:s = " hello world "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格
思路 :
首先使用双指针法去除多余空格
然后翻转整个字符串
再把每个单词反转回来
func ReverseWords(s string) string {
// 将s转换为字符串
ByteSlice := []byte(s)
// 一:首先使用双指针去除多余空格
slow := 0
for i := 0; i < len(ByteSlice); i++ {
if ByteSlice[i] != ' ' {
// 如果slow不指向起始位置,添加空格
if slow != 0 {
ByteSlice[slow] = ' '
slow++
}
// 虽然是两层for循环,但是时间复杂度是O(n)
for i < len(ByteSlice) && ByteSlice[i] != ' ' { // 复制逻辑
ByteSlice[slow] = ByteSlice[i]
slow++
i++
}
}
}
//去除空格之后,切片截取到slow指针指向的位置
ByteSlice = ByteSlice[0:slow]
// 翻转整个字符串
reverse(ByteSlice)
// 翻转每个单词
last := 0
for i := 0; i <= len(ByteSlice); i++ {
// 必须先判断 i == len(ByteSlice)
if i == len(ByteSlice) || ByteSlice[i] == ' ' {
reverse(ByteSlice[last:i])
last = i + 1
}
}
return string(ByteSlice)
}
// 反转字符串
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}
58.左旋转字符串
剑指 Offer 58 - II. 左旋转字符串 - 力扣(LeetCode)
不使用额外空间
思路:
首先反转前 n 个字符串
反转 n 到末尾的字符串
反转所有字符串
func ReverseLeftWords(s string, n int) string {
ss := []byte(s)
// 反转前n个字符串
reverse(ss[:n])
// 反转n到末尾的字符串
reverse(ss[n:len(ss)])
// 反转所有字符串
reverse(ss)
return string(ss)
}
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}
func reverseLeftWords(s string, n int) string {
b := []byte(s)
// 1. 反转前n个字符
// 2. 反转第n到end字符
// 3. 反转整个字符
reverse(b, 0, n-1)
reverse(b, n, len(b)-1)
reverse(b, 0, len(b)-1)
return string(b)
}
// 切片是引用传递
func reverse(b []byte, left, right int){
for left < right{
b[left], b[right] = b[right],b[left]
left++
right--
}
}
使用额外空间
func ReverseLeftWords(s string, n int) string {
ss := []byte(s)
// 创建一个额外的内容空间
result := make([]byte, len(ss))
// 将n到结尾的字母追加到新创建的空间
for i := n; i < len(ss); i++ {
result = append(result, ss[i])
}
// 将开头到n的字母追加到切片结尾
for i := 0; i < n; i++ {
result = append(result, ss[i])
}
return string(result)
}
评论区