目 录CONTENT

文章目录

算法学习-字符串

Sakura
2023-09-17 / 0 评论 / 1 点赞 / 28 阅读 / 0 字 / 正在检测是否收录...
温馨提示:
本文最后更新于228天前,若内容或图片失效,请留言反馈。 部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

344.反转字符串

344. 反转字符串 - 力扣(LeetCode)

# 示例 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.反转字符串Ⅱ

541. 反转字符串 II - 力扣(LeetCode)

给定一个字符串 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.翻转字符串里的单词

151. 反转字符串中的单词 - 力扣(LeetCode)

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

# 示例 1:
输入:s = "the sky is blue"
输出:"blue is sky the"

# 示例 2:
输入:s = "  hello world  "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格

思路 :

  1. 首先使用双指针法去除多余空格

  1. 然后翻转整个字符串

  1. 再把每个单词反转回来

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)

  • 不使用额外空间

思路:

  1. 首先反转前 n 个字符串

  2. 反转 n 到末尾的字符串

  3. 反转所有字符串

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)
}

28.实现strStr() ( 之后有时间看 )

459.重复的子字符串 ( 之后有时间看 )

1

评论区