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

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：412 字 | 阅读时长：2 分钟

题目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

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