一、题目要求

给定一个字符串s和不大于该字符串长度的正整数n，要求把s的前n个字符移到字符串最后面去，要求时间复杂度为O(n)，空间复杂度为O(1)。

例如给定字符串abcdef和正整数3，则经过转换后的字符串为defabc。

二、解题思路

2.1 暴力解法

如果不考虑时间复杂度和空间复杂度，第一个想到的解法肯定是暴力移位，把所有的元素依次搬到最后。

void move_ahead(char *s, int len) {
    char ch = s[0];  // 保存第一个字符
    for (int i = 1; i < lenn; i++) // 把后面的字符依次前移
        s[i - 1] = s[i];
    s[len - 1] = ch;
}

void reverse(char *s, int n) {
    int len = strlen(s);
    for (int i = 0; i < n; i++) {
        move_ahead(s, len);
    }
}

此种解法的时间复杂度为O(n^2)，空间复杂度为O(1)，空间复杂度满足条件，时间复杂度不满足。因此这种方法肯定不是符合题意的解法。

2.2 更优解法

给定操作f(x)表示反转字符串x，例如对于x=abcdef，f(x)的值为fedcba。

我们将要反转的字符串根据分割点分为两部分s1和s2，执行操作f(f(s1)+f(s2))即可完成题目要求的结果。

例如上面的defghi，以3分隔出s1为abc，s2为def，那么f(s1)+f(s2)等于cbafed，再将这个结果反转就能得到defabc。

三、解决方案

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

typedef unsigned int uint;

void reverse_range(char *s, uint from, uint to) {
    char ch;
    while(from < to) {
        ch = s[from];
        s[from++] = s[to];
        s[to--] = ch;
    }
}

void reverse(char *s, uint idx, uint len) {
    reverse_range(s, 0, idx);
    reverse_range(s, idx + 1, len);
    reverse_range(s, 0, len);
}

int main(int argc, char **argv) {
    if (argc != 3) {
        printf("Usage: ./a.out abcdef 3\n");
        return 0;
    }

    uint len = strlen(argv[1]);
    uint cnt = atoi(argv[2]);
    if (len < cnt) {
        printf("The length of string is lager than index\n");
        return 0;
    }

    reverse(argv[1], cnt - 1, len - 1);

    printf("%s\n", argv[1]);

    return 0;
}

运行示例：

> ./reverse abcdef 3
defabc
> ./reverse helloworld 5
worldhello