[Algorithm]算法(字符串移动,单词翻转)

题目1:

定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部,如把字符串abcdef左旋转2位得到字符串cdefab。

请实现字符串左旋转的函数,要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1)

题目2:

输入一个英文句子,番句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。句子中标点符号和普通字母一样处理。

例如输入“I am a student.”,则输出“student. a am I”。

解决方法:

先将整个句子翻转,再将其中的每个单词翻转

Code (cpp)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>  
#include <string>
#include <iostream>
#include <string.h>

using namespace std;

void reverse(char *s, int from, int to)
{
while(from < to)
{
char t = s[from];
s[from++] = s[to];
s[to--] = t;
}
}

void WordRotateString(char *s)
{
reverse(s, 0, strlen(s)-1);
int start = 0;
int end = 0;
while(s[start] !='\0')
{
if(s[end] == '\0') break;

if(s[end] == ' ') {
reverse(s, start, end-1);
end++;
start = end;
} else
end++;
}
}

void LeftRotateString(char *s, int n,int m)
{
m %= n;
reverse(s, 0, m-1);
reverse(s, m, n-1);
reverse(s, 0, n-1);
}



int main(int argc, char **argv)
{
//反转字符 string s = "abcdefg";
cout << s << endl;
LeftRotateString((char *)s.c_str(), s.length(), 2);
cout << s << endl;
cout << endl;
//单词反转
s = "I am a student.";
cout << s << endl;
WordRotateString((char *)s.c_str());
cout << s << endl;
return 0;
}

Reference

程序员编程艺术:第一章、左旋转字符串