剑指Offer 58 - ii. 左旋转字符串

• 题目描述
• 题解
• • 字符串复制法
  • 王道双指针
  • 切片函数
• 运行结果

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

题解

字符串复制法

定义一个辅助字符串指针h，通过单重循环先将后半部分读入h指向的内存空间，再将前半部分读入，实现旋转，算法的时间空间复杂度均为O(n)。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* reverseLeftWords(char* s, int n) { 
    int length = strlen(s);
    int i, j = 0;
    char* h = (char*)malloc(sizeof(char)*(length+n));
    for (i = n; i <= length-1; i++) { 
        h[j++] = s[i];
    }
    for (i = 0;i <= n-1; i++) { 
        h[j++] = s[i];
    }
    h[j] = '\0';
    return h;
}

int main() { 
	char* s = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

王道双指针

这题是LeetCode剑指第一题，竟然还是考研真题，王道书上对于这操作叫部分字符串左移，王道的方法就是定义一个以字符为单位的交换函数，调用三次，分别交换[0，n-1]、[n，length-1]和[0，length-1]，时间复杂度仍为O(n)，但是空间复杂度只与中转变量temp有关，为O(1)。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* reverseLeftWords(char s[], int n) { //The char* pointer points to the string constant area and it cannot be modified, so it is changed to a chartype array, but it can be submitted with a pointer on the LeetCode.
    int length = strlen(s);
    char temp;
    int low, high;
    for (low = 0, high = n-1;low <= high;low ++, high--) { 
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    for (low = n, high = length-1;low <= high;low ++, high--) { 
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    for (low = 0, high = length-1;low <= high;low ++, high--) { 
        temp = s[low];
        s[low] = s[high];
        s[high] = temp;
    }
    return s;
}

int main() { 
	char s[] = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

切片函数

采用java中的切片函数substring()时空间效率无提升，但是可以将代码精简至一行。C中没有这个函数，我自己定义了一个strcut()函数实现类似功能，也将旋转函数精简至一行，不过LeetCode会显示对h指向的内存分配空间时内存溢出，暂时还没解决，但是这个代码在编译器上是可以圆满完成要求的。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

char* strcut(char* s, int begin, int end) { 
    int i = 0, j = 0;
    char* h = (char*)malloc(end-begin);
    for (i = begin;i <= end; i++) { 
        h[j++] = s[i];
    }
    h[j] = '\0';
    return h;
}

char* reverseLeftWords(char* s, int n) { 
    return strcat(strcut(s, n, strlen(s)-1), strcut(s, 0, n-1));
}

int main() { 
	char* s = "arta!This is Sp";
	printf("%s", reverseLeftWords(s, 5));
    return 0;
}

运行结果