樣例:
對于字符串 "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; } } } }新聞熱點
疑難解答
