Leetcode Answers 186

继续刷题,今晚第8道。这次是要做一个in-place的reverse words。前一个是用的C#的string的方法基本上一行就搞定了,但是因为string的split和join都有大量的复制操作所以会占用很多extra space,这次换成in-place来处理。

题目:
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

思路:
之前的Reverse string是用string.split和string.join来做的,每一个都有大量的copy操作,需要大量的space。那么换成in-place的话首先想到的一个方法就是逐字swap,这个很容易。当我们把整个string都swap过了以后就是逆序了,虽然单词本身也是逆序了,于是再去找每个单词重新再swap回来就好了。按照空格去找,空格之前的swap,最后剩下一个再swap一下,结束。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
public void ReverseWords(char[] s) {
if(s == null || s.Length <= 0) return;
int l = s.Length - 1, start = 0;
swap(s, 0, l);
int i = 1;
for(; i<= l; i++){
if(s[i] == ' '){
swap(s, start, i-1);
start = i+1;
}
}
swap(s, start, i-1);
}
private void swap(char[] s, int start, int end){
char temp = ' ';
while(start<end){
temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
}

考察:Discuss里面有人提到如果给的char[]特别大以至于memory 装不下那怎么办。我的想法就是进行partitioning,然后注意的是,先处理的part是逆序之后最末尾的part,这样就可以了。或者partitioning之后按照逆序从最后面的part开始处理,这样就正序append就好了。

以上。

17-04-23
@Sturbridge