反转字符串里的单词
题目
给你一个字符串 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"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。思路
如果会使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了
如果不要使用辅助空间，空间复杂度要求为O(1)，那么只能在原字符串上下功夫了。
解题思路如下：
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
解法
解法1：先删除空白，然后整个反转，最后单词反转。
func reverseWords(s string) string {
b := []byte(s)
// 移除前面、中间、后面存在的多余空格
slow := 0
for i := 0; i < len(b); i++ {
if b[i] != ' ' {
if slow != 0 {
b[slow] = ' '
slow++
}
for i < len(b) && b[i] != ' ' { // 复制逻辑
b[slow] = b[i]
slow++
i++
}
}
}
b = b[0:slow]
// 翻转整个字符串
reverse(b)
// 翻转每个单词
last := 0
for i := 0; i <= len(b); i++ {
if i == len(b) || b[i] == ' ' {
reverse(b[last:i])
last = i + 1
}
}
return string(b)
}
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}解法2：使用双指针
func reverseWords(s string) string {
//1.使用双指针删除冗余的空格
slowIndex, fastIndex := 0, 0
b := []byte(s)
//删除头部冗余空格
for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' {
fastIndex++
}
//删除单词间冗余空格
for ; fastIndex < len(b); fastIndex++ {
if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' {
continue
}
b[slowIndex] = b[fastIndex]
slowIndex++
}
//删除尾部冗余空格
if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {
b = b[:slowIndex-1]
} else {
b = b[:slowIndex]
}
//2.反转整个字符串
reverse(b)
//3.反转单个单词 i单词开始位置，j单词结束位置
i := 0
for i < len(b) {
j := i
for ; j < len(b) && b[j] != ' '; j++ {
}
reverse(b[i:j])
i = j
i++
}
return string(b)
}
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}