面试题：C语言指针操作字符串实现字符串循环移位

Question

给定一个字符串和一个整数n，使用指针操作该字符串，实现将字符串循环右移n位。例如，对于字符串“abcdef”和n = 2，结果应为“efabcd”。请编写函数void rotateString(char* str, int n)来实现此功能，要考虑空间复杂度和时间复杂度，尽量做到高效实现。

Answer 1

#include <stdio.h>
#include <string.h>

void reverse(char* start, char* end) {
    while (start < end) {
        char temp = *start;
        *start = *end;
        *end = temp;
        start++;
        end--;
    }
}

void rotateString(char* str, int n) {
    int len = strlen(str);
    n %= len;
    reverse(str, str + len - 1);
    reverse(str, str + n - 1);
    reverse(str + n, str + len - 1);
}

1. 空间复杂度：
   • 上述代码中除了输入的字符串和几个指针变量外，没有使用额外的与输入规模相关的空间，所以空间复杂度为 (O(1))。
2. 时间复杂度：
   • reverse 函数的时间复杂度为 (O(k))，其中 (k) 是反转的字符个数。
   • 三次调用 reverse 函数，总的时间复杂度为 (O(len))，其中 len 是字符串的长度。

如果要在 main 函数中测试该函数，可以参考以下代码：

int main() {
    char str[] = "abcdef";
    int n = 2;
    rotateString(str, n);
    printf("%s\n", str);
    return 0;
}