FilesExpand file tree

 master

/

Coding_028.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

81 lines (68 loc) · 1.36 KB

 master

/

Coding_028.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

81 lines (68 loc) · 1.36 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

//左旋转字符串

//题目描述

//

/*

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，

就是用字符串模拟这个指令的运算结果。

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。

例如，字符序列S=“abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

是不是很简单？OK，搞定它！

*/

//思路

/*

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

XY ->YX

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

把abcXYZdef看成两部分

abc XYZdef

-》cda fedZYX

-》XYZdef abc

-》XYZdefabc

也就是对需要循环左移（旋转）的字符串

反转前k位字符串

以及再反转剩下length - k位字符串

进行全部一次反转

时间复杂度O（n）,

空间复杂度O（1）

*/

#include <iostream>

#include <vector>

#include <string>

#include <stack>

#include <queue>

using namespace std;

class Solution {

public:

string LeftRotateString(string str, int n) {

if (str.empty())

return str;

int len = str.length();

if (len <= n||n<=0)

return str;

Reverse(str, 0, n-1);

Reverse(str, n, len - 1);

Reverse(str, 0, len - 1);

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{ "abcXYZdef" };

cout << a.LeftRotateString(str,3) << ' ';

system("pause");

return 0;

}