FilesExpand file tree

 master

/

Coding_029.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

82 lines (70 loc) · 1.23 KB

 master

/

Coding_029.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

82 lines (70 loc) · 1.23 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

//翻转单词顺序列

//题目描述

//

/*

例如，“student. a am I”。

把句子单词的顺序翻转了，

正确的句子应该是“I am a student.”。

*/

//思路

/*

利用T(X)代表转置符号

XY ->YX

YX = T(T(YX))=T(T(X)T(Y))

把整个字符串翻转

再对所有单词再进行一次反转

时间复杂度O（n）,

空间复杂度O（1）

*/

#include <iostream>

#include <vector>

#include <string>

#include <stack>

#include <queue>

using namespace std;

class Solution {

public:

string ReverseSentence(string str) {

if (str.empty())

return str;

int len = str.length();

Reverse(str, 0, len - 1);

int start = 0;

for (int i = 0; i < len; ++i)

{

if (str[i] == ' ')

{

Reverse(str, start, i-1);

while (str[++i] == ' ')

;//过来掉单词中的多个空格

start = i;

}

else if (i == len - 1)

{

Reverse(str, start, i);

}

}

return str;

}

private:

void Reverse(string& str, int start, int end)

{

while (start<end)

{

char temp = str[start];

str[start] = str[end];

str[end] = temp;

++start;

--end;

}

}

};

int main()

{

Solution a;

//vector<int> nums{3};

string str{ "student. a am I" };

cout << a.ReverseSentence(str) << ' ';

system("pause");

return 0;

}