首页 > 代码库 > 编程珠玑--左旋字符串

编程珠玑--左旋字符串

2024-07-07 18:52:15   228人阅读

其实编程之美也有类似的题，这道题是编程珠玑第二章的题目。

题目描述：给定一个字符串，将字符串循环移位K次。

最简答的方法就是，通过O(n)的辅助空间，将数组循环移位，时间复杂度就是O(n)

但是如果要求空间复杂度为O(1)呢？

观察规律可知，对前K位反转以及后面的反转，最后对整个字符串反转就能达到O(1)的空间复杂度。

PS：注意处理k>字符串的长度的情况

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 void reverseStr(string &s,int i,int j)
 7 {
 8     while(i < j)
 9     {
10         char tmp = s[i];
11         s[i] = s[j];
12         s[j] = tmp;
13         ++i;
14         --j;
15     }
16 }
17 
18 void leftRotate(string &s,int k)
19 {
20     int len = s.length();
21     k = k%len;
22     reverseStr(s,0,k-1);
23     reverseStr(s,k,len-1);
24     reverseStr(s,0,len-1);
25 }
26 
27 int main()
28 {
29     string s("abcdefgh");
30     leftRotate(s,3);
31     cout<<s<<endl;
32     return 0;
33 }

 


联系
我们