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

2022 年 6 月 13 日
本文字数：1925 字
阅读完需：约 6 分钟

⭐️剑指 Offer 58 - II. 左旋转字符串⭐️

🔐题目详情

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

示例：

输入: s = "abcdefg", k = 2输出: "cdefgab"输入: s = "lrloseumgh", k = 6输出: "umghlrlose"

复制代码

限制：

1 <= k < s.length <= 10000

复制代码

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof

💡解题思路

在正式对字符串进行左旋之前，首先来看看字符串左旋次数与字符串个数的规律，假设字符串长度为len，左旋次数为k。举例一个字符串str=abcdef，此时len = 6，当k=1，左旋得bcdefa，k=3，左旋得defabc，k=6，左旋得abcdef与初始时的字符串相等，所以我们可以通过规律得到左旋次数k为字符串长度len的倍数时，左旋字符串与初始时字符串相同，所以说，当左旋len+1次与左旋1次的效果是相同的，所以在对字符串进行左旋操作时不妨先对左旋次数k取len的模，这样，当k比较大时，消耗的时间比较少，提高了程序的效率！由于力扣平台提供的字符串指针常量，不能对该指针指向的内容进行修改，需要自己申请空间进行字符串的左旋操作！方法 1： 暴力遍历。我们最先想到的就是遍历，每次左旋，我们就将第一个字符替换到最后一个字符位置，并将后面的字符左移。

时间复杂度： O(k*N)

方法 2： 巧妙拷贝。申请好内存之后，我们可以对原字符串s进行特定位置的拷贝，比如字符串abcdefg需要左旋该字符串k次，该字符串长度为len=7，不难发现下标为k%len的字符，左旋k次后，会在数组的首位置，所以我们可以从原字符串下标为 $k$ 字符开始拷贝。

但是注意要保证k的值不大于字符串长度len（先对k取len的模，即k %= len），由于访问拷贝完最后一个元素后需要访问拷贝首个元素，所以我们需要对访问的数组下标取len的模（即*(s+(k+i)%len)或s[(k+i)%len]）保证数组不越界和实现从最后一个元素过渡到首个元素，该栗子中数组下标顺序为k->k+1->...->len-1->0->...->k-1，如果k=4，进行拷贝的数组下标次序是4->5->6->0->1->2->3，得到的就是逆序的字符串efgabcd。

时间复杂度： O(N)方法 3： 逆序三部曲。还是以字符串abcdefg需要左旋该字符串k次（保证k < len），该字符串长度为len=7,左旋次数k=4为例！因为下标为k%len的字符，左旋k次后，会在数组的首位置，所以我以该元素为分界线，位于该元素之前的作为一组（不包括该分界字符）,下标范围为 $[0, k$ ，位于该元素之后的作为一组（包含该分界字符）,下标范围为 $[k$ 。先分别对两部分进行逆序，然后在整个字符串进行逆序，就能得到左旋k次的字符串，一共进行三次字符串逆序，简称“逆序三部曲”。

时间复杂度： O(N)

🔑源代码

编程语言：C 语言在线编程平台：力扣

//方法1char* reverseLeftWords(char* s, int n){  int len = strlen(s);    int k = 0;    k = n % len;//当左旋位数为字符串长度整数倍时，左旋后与初始相同    int i = 0;    char* str = (char*)malloc(sizeof(char) * len + 1) ;//申请合适空间    strcpy(str,s);    for (i = 0; i < k; i++)//每次左旋一位，需要左旋几次，就循环几次    {        int j = 0;        char tmp = *str;        for (j = 0; j < len - 1; j++)        {            *(str + j) = *(str + j + 1);//左旋一位        }        *(str + j) = tmp;    }    return str;}

复制代码

//方法2char* reverseLeftWords(char* s, int n){    int len = strlen(s);    char* str = (char*)malloc(sizeof(char) * len +1);    int i = 0;    int k = 0;    k = n % len;    for(i = 0; i < len; i++)    {        *(str + i) = *(s + (k + i) % len);    }    *(str + i) = '\0';    return str;}

复制代码

//方法3void reverse(char* str, int i, int j){    int left = i;    int right = j;    while (left < right)    {        char tmp = str[left];        str[left] = str[right];        str[right] = tmp;        right--;        left++;    }}char* reverseLeftWords(char* s, int n){    int len = strlen(s);    char* str = (char*)malloc(sizeof(char) * len + 1);    int k = n % len;    strcpy(str,s);    reverse(str, 0, k-1);    reverse(str, k, len-1);    reverse(str, 0, len-1);    str[len] = '\0';    return str;}

复制代码

🌱总结

对于字符串左旋，根本上还是对字符串的移动操作。对字符串本身变量进行改动，可以采用遍历和分部分反转字符串的方法进行左旋，当有足够的空间，也可以巧用拷贝字符的方法对字符串进行左旋。

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/8b8742a39f8856b2b0d625a17】。文章转载请联系作者。

未见花闻

关注

还未添加个人签名 2021.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景

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

⭐️剑指 Offer 58 - II. 左旋转字符串⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结

未见花闻

评论