首页 计算机科学 算法训练 2023

# 字符串

Go 标准库源码解析 - 文本操作：https://blog.twelveeee.top/2023/Go/Lib/strings/

# 算法题

# 1. 转换成小写字母

https://leetcode.cn/problems/to-lower-case/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_1/topic_1.go

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。

func toLowerCase(s string) string {
	return strings.ToLower(s)
}
func toLowerCaseV2(s string) string {
	ans := strings.Builder{}
	ans.Grow(len(s))
	for _, ch := range s {
		if ch >= 'A' && ch <= 'Z' {
			ch += 32
		}
		ans.WriteRune(ch)
	}
	return ans.String()
}
# 2. 字符串转换整数
https://leetcode.cn/problems/string-to-integer-atoi/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_1/topic_2.go
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。
注意：
  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
func myAtoi(s string) int {
	i, ans, n := 0, 0, len(s)
	flag := 1
	for i < n && s[i] == ' ' {
		i++
	}
	if i < n && s[i] == '-' {
		flag = -1
		i++
	} else if i < n && s[i] == '+' {
		i++
	}
	for i < n {
		if s[i] < '0' || s[i] > '9' {
			return ans * flag
		}
		ans *= 10
		ans += int(s[i] - '0')
		if ans*flag < math.MinInt32 {
			return math.MinInt32
		} else if ans*flag > math.MaxInt32 {
			return math.MaxInt32
		}
		i++
	}
	return ans * flag
}
# 3. 反转字符串
https://leetcode.cn/problems/reverse-string/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_1.go
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地改输入数组、使用 O (1) 的额外空间解决这一问题。
func reverseString(s []byte) {
	for i := 0; i < len(s)/2; i++ {
		s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i]
	}
}
# 4. 反转字符串 II
https://leetcode.cn/problems/reverse-string-ii/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_2.go
给定一个字符串 s 和一个整数 k ，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
func reverseStr(s string, k int) string {
	ans := []byte(s)
	times := len(s) / (2 * k)
	if len(s)%(2*k) != 0 {
		times++
	}
	for i := 0; i <= times; i++ {
		left, rihgt := i*2*k, (i*2*k)+k
		if rihgt > len(s) {
			rihgt = len(s)
		}
		for j := 0; j < (rihgt-left)/2; j++ {
			ans[left+j], ans[rihgt-j-1] = ans[rihgt-j-1], ans[left+j]
		}
	}
	return string(ans)
}
# 5. 仅仅反转字母
https://leetcode.cn/problems/reverse-only-letters/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_3.go
给你一个字符串 s ，根据下述规则反转字符串：
  • 所有非英文字母保留在原有位置。
  • 所有英文字母（小写或大写）位置反转。
返回反转后的 s 。
func reverseOnlyLetters(s string) string {
	ans := []byte(s)
	w := 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] > 'z' || s[i] < 'A' || (s[i] > 'Z' && s[i] < 'a') {
			continue
		}
		for w < len(ans) && (ans[w] > 'z' || ans[w] < 'A' || (ans[w] > 'Z' && ans[w] < 'a')) {
			w++
		}
		ans[w] = s[i]
		w++
	}
	return string(ans)
}
# 5. 仅仅反转字母
https://leetcode.cn/problems/reverse-only-letters/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_3.go
给你一个字符串 s ，根据下述规则反转字符串：
  • 所有非英文字母保留在原有位置。
  • 所有英文字母（小写或大写）位置反转。
返回反转后的 s 。
func reverseOnlyLetters(s string) string {
	ans := []byte(s)
	w := 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] > 'z' || s[i] < 'A' || (s[i] > 'Z' && s[i] < 'a') {
			continue
		}
		for w < len(ans) && (ans[w] > 'z' || ans[w] < 'A' || (ans[w] > 'Z' && ans[w] < 'a')) {
			w++
		}
		ans[w] = s[i]
		w++
	}
	return string(ans)
}
# 6. 验证回文串
https://leetcode.cn/problems/valid-palindrome/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_4.go
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s ，如果它是 回文串 ，返回 true ；否则，返回 false 。
func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		for left < right && !isLetter(s[left]) {
			left++
		}
		for left < right && !isLetter(s[right]) {
			right--
		}
		if !sameByte(s[left], s[right]) {
			return false
		}
		right--
		left++
	}
	return true
}
func isLetter(a byte) bool {
	// 48 57 65 90 97 122
	// '0', '9', 'A', 'Z', 'a', 'z'
	if a >= 'a' && a <= 'z' {
		return true
	}
	if a >= 'A' && a <= 'Z' {
		return true
	}
	if a >= '0' && a <= '9' {
		return true
	}
	return false
}
func sameByte(a, b byte) bool {
	if a == b {
		return true
	}
	if '0' >= a && a <= '9' {
		return false
	}
	if diff := int(a) - int(b); diff == -32 || diff == 32 {
		return true
	}
	return false
}
# 7. 字符串中的第一个唯一字符
https://leetcode.cn/problems/valid-palindrome/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_2/topic_5.go
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s ，如果它是 回文串 ，返回 true ；否则，返回 false 。
func firstUniqChar(s string) int {
	list := make([]int, 26)
	for _, v := range s {
		list[v-'a']++
	}
	for i, v := range s {
		if list[v-'a'] == 1 {
			return i
		}
	}
	return -1
}
# 8. 最长公共前缀
https://leetcode.cn/problems/longest-common-prefix/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_3/topic_1.go
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
func longestCommonPrefix(strs []string) string {
	if len(strs) == 1 {
		return strs[0]
	}
	minLen := math.MaxInt32
	var ans []byte
	for _, str := range strs {
		if minLen > len(str) {
			minLen = len(str)
		}
	}
	for i := 0; i < minLen; i++ {
		firstChar := strs[0][i]
		for _, str := range strs {
			if firstChar != str[i] {
				return string(ans)
			}
		}
		ans = append(ans, firstChar)
	}
	return string(ans)
}
# 9. 压缩字符串
https://leetcode.cn/problems/string-compression/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/12_String/level_3/topic_2.go
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
  • 如果这一组长度为 1 ，则将字符追加到 s 中。
  • 否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
func compress(chars []byte) int {
	if len(chars) <= 1 {
		return 1
	}
	pre, write := 0, 0
	for i := 0; i < len(chars); i++ {
		if i == len(chars)-1 || chars[pre] != chars[i+1] {
			chars[write] = chars[pre]
			write++
			count := i - pre + 1
			if count > 1 {
				tempWrite := write
				for count > 0 {
					chars[write] = '0' + byte(count%10)
					count /= 10
					write++
				}
				for j := 0; j < (write-tempWrite)/2; j++ {
					chars[tempWrite+j], chars[write-j-1] = chars[write-j-1], chars[tempWrite+j]
				}
			}
			pre = i + 1
		}
	}
	return write
}
 
-->