时间戳

首页 > 技术文章 > 翻转单词顺序VS左旋转字符串

翻转单词顺序VS左旋转字符串

sankexin 2016-07-02 22:22 原文

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。

思路:首先将整个句子按字符翻转，然后再将其中每个单词的字符旋转。

 1 #include <string>
 2 #include "stdafx.h"
 3 
 4 void Reverse(char *pBegin, char *pEnd)
 5 {
 6     if(pBegin == NULL || pEnd == NULL)
 7         return;
 8     
 9     while(pBegin < pEnd)
10     {
11         char temp = *pBegin;
12         *pBegin = *pEnd;
13         *pEnd = temp;
14         
15         pBegin ++, pEnd --;
16     }
17 }
18 
19 char* ReverseSentence(char *pData)
20 {
21     if(pData == NULL)
22         return NULL;
23 
24     char *pBegin = pData;
25 
26     char *pEnd = pData;
27     while(*pEnd != '\0')
28         pEnd ++;
29     pEnd--;
30 
31     // 翻转整个句子
32     Reverse(pBegin, pEnd);
33 
34     // 翻转句子中的每个单词
35     pBegin = pEnd = pData;
36     while(*pBegin != '\0')
37     {
38         if(*pBegin == ' ')
39         {
40             pBegin ++;
41             pEnd ++;
42         }
43         else if(*pEnd == ' ' || *pEnd == '\0')
44         {
45             Reverse(pBegin, --pEnd);
46             pBegin = ++pEnd;
47         }
48         else
49         {
50             pEnd ++;
51         }
52     }
53 
54     return pData;
55 }
56 
57 
58 int main()
59 {
60     char input[] = "I am a student.";
61     printf("%s\n\n",input);
62     printf("After reverse.\n\n");
63     ReverseSentence(input);
64     printf("%s\n", input);
65     
66     return 0;
67 }

题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。 

思路:把字符串分为两个部分，先分别翻转这两部分，接下来再翻转整个字符串。

 1 #include <string>
 2 #include "stdafx.h"
 3 
 4 void Reverse(char* pBegin, char* pEnd)
 5 {
 6     if(pBegin == NULL || pEnd == NULL)
 7         return;
 8 
 9     while(pBegin < pEnd)
10     {
11         char temp = *pBegin;
12         *pBegin = *pEnd;
13         *pEnd = temp;
14 
15         pBegin++;
16         pEnd--;
17     }
18 }
19 
20 char* LeftRotateString(char* pStr, int n)
21 {
22     if(pStr != NULL)
23     {
24         int nLength = static_cast<int>(strlen(pStr));
25         if(nLength > 0 && n > 0 && n < nLength)
26         {
27             char *pFirstStart = pStr;
28             char *pFirstEnd = pStr + n - 1;
29             char *pSecondStart = pStr + n;
30             char *pSecondEnd = pStr + nLength - 1;
31             
32             Reverse(pFirstStart, pFirstEnd);
33             Reverse(pSecondStart, pSecondEnd);
34             Reverse(pFirstStart, pSecondEnd);
35         }
36     }
37     
38     return pStr;
39 }
40 
41 int main(int argc, char const *argv[])
42 {
43     char input[] = "abcdefg";
44     printf("the initial is :%s\n", input);
45     int num = 2;
46     char* result = LeftRotateString(input, num);
47     printf("after left rotate : %s\n", result);
48     
49     return 0;
50 }

推荐阅读