解题要点:设i,j作为指针分别指向头与尾,交换位置,实现原地算法
func reverseString(s []byte) {
j := len(s) - 1
i := 0
for i < j {
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
}
}
解题要点:找出空格位置,然后根据这个位置找到这个单词进行反转
func reverseWords(s string) string {
length := len(s)
ret := []byte{}
for i := 0; i < length; {
start := i
for i < length && s[i] != ' ' {
i++
}
for p := start; p < i; p++ {
ret = append(ret, s[start+i-1-p])
}
for i < length && s[i] == ' ' {
i++
ret = append(ret, ' ')
}
}
return string(ret)
}
func reverseWords(s string) string {
top := 0
bottom := 0
n := len(s)
ret := []byte{}
start := 0
for top < n {
if s[top] == ' ' {
fmt.Println(top, bottom)
for bottom < top {
fmt.Println(top, bottom, start+top-bottom-1, string(s[start+top-bottom-1]))
ret = append(ret, s[start+top-bottom-1])
bottom += 1
}
ret = append(ret, ' ')
bottom = top + 1
start = bottom
fmt.Println(string(ret), "----=", string(s[start+top-bottom-1]), top, bottom)
}
top += 1
}
top = n
start = bottom
for start < n {
fmt.Println(bottom + top - start - 1)
ret = append(ret, s[bottom+top-start-1])
start += 1
}
return string(ret)
}
总结
1、字符串反转,用双指针是非常好的实现
2、原地算法,减少额外数组的使用
3、反转算法,使用原地算法进行字符串的反转操作,不需要额外的空间申请,通过双指针进行位置记录使得每次循环能够替换位置