剑指offer58-1（反转字符串）

发表于 | 分类于 ，

题目：

　　输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变。如输入字符串“I am a student.”输出“student. a am I”

思路：

　　先整体反转字符串，然后按各个字符再次反转。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String ReverseSentence1(String str) {
	char[] arr = str.toCharArray();
	reverse(arr, 0, arr.length-1);
	int startIndex = -1;
	for(int i = 0;i < arr.length;i++) {
		if (arr[i] == ' ') {
			int endIndex = i;
			reverse(arr, startIndex+1, endIndex-1);
			startIndex = endIndex;
		}
	}
	reverse(arr, startIndex+1, arr.length-1);
	return new String(arr);
}
public static void reverse(char[] arr,int low,int high) {
	while(low < high) {
		char temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
		low++;
		high--;
	}
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。