C++,
time: O(n)
space:O(n)
1 class Solution { 2 public: 3 /** 4 * @param str: a string 5 * @param offset: an integer 6 * @return: nothing 7 */ 8 void rotateString(string &str, int offset) { 9 // wirte your code here 10 // empty string->return 11 if ("" == str) { 12 return; 13 } 14 // offset is 0, return 15 int size = str.size(); 16 offset = offset%size; 17 if (0 == offset) { 18 return; 19 } 20 // tmp = str+str->substr 21 string tmp(str); 22 tmp.reserve(size<<1); 23 tmp.insert(tmp.end(), str.begin(), str.end()); 24 str = tmp.substr(size-offset, size); 25 } 26 };
C++,
time:O(n)
space:O(1)
1 class Solution { 2 public: 3 /** 4 * @param str: a string 5 * @param offset: an integer 6 * @return: nothing 7 */ 8 void rotateString(string &str, int offset) { 9 // wirte your code here 10 // empty string->return 11 if ("" == str) { 12 return; 13 } 14 // offset is 0, return 15 int size = str.size(); 16 offset = offset%size; 17 if (0 == offset) { 18 return; 19 } 20 // 3-steps reverse 21 reverse(str, 0, size-offset-1); 22 reverse(str, size-offset, size-1); 23 reverse(str, 0, size-1); 24 } 25 void reverse(string &str, int from, int to) { 26 char tmp; 27 while( from<to ) { 28 tmp = str[from]; 29 str[from] = str[to]; 30 str[to] = tmp; 31 from++; 32 to--; 33 } 34 } 35 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/4999687.html，如需转载请自行联系原作者
