样例:
对于字符串 "abcdefg".offset=0 => "abcdefg"offset=1 => "gabcdef"offset=2 => "fgabcde"offset=3 => "efgabcd"算法要求:
在数组上原地旋转，使用O(1)的额外空间解题思路:
用直接定位法，来进行每个字符的定位。可以理解城对号入座，只需要进行n-1次就可以了。此算法的时间复杂度为O(n),进行n-1次交换。算法如下:
void rotateString(string &str, int offset) { int length = str.length(); int now = 0;//当前last位置所代表字符的初始位置 int last = 0;//考虑到可以能重复循环，用来记录是否重复了， char tempStr; if (length == 0 || str == NULL) { return; } if (offset >= length) { offset = offset % length; } if (offset == 0) { return; } else { for (int i = 1; i < length ; i++) { tempStr = str[abs((offset + now) % length)]; str[abs((now + offset) % length)] = str[last]; str[last] = tempStr; now = abs((offset + now) % length); if (now == last) {//如果重复操作了，就进行+1操作 last++; now = last; } } } }新闻热点
疑难解答
