⭐️前面的话⭐️
大家好！博主开辟了一个新的专栏——剑指offer，我要开始刷题了！这个专栏会介绍《剑指offer》书上所有的面试编程题。并且会分享一些我的刷题心得。由于博主水平有限，如有错误，欢迎指正，如果有更好的解题思路和算法可以分享给博主哦！一起加油！一起努力！
📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2021年9月10日🌴
💖祝所有的老师教师节快乐！💖
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《剑指offer第1版》，📚《剑指offer第2版》
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
博主的码云gitee，平常博主写的程序代码都在里面。
📌导航小助手📌
- ⭐️剑指 Offer 58 - II. 左旋转字符串⭐️
- 🔐题目详情
- 💡解题思路
- 🔑源代码
- 🌱总结
⭐️剑指 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，我们可以从原字符串的第1个不需要 左旋字符开始拷贝（数组下标为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次的字符串，一个进行三次字符串逆序，简称“逆序三部曲”。
时间复杂度： O(N)
🔑源代码
编程语言：C语言
在线编程平台：力扣
//方法1
char* 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;
}
//方法2
char* 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;
}
//方法3
void 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;
}
🌱总结
对于字符串左旋，根本上还是对字符串的移动操作。对字符串本身变量进行改动，可以采用遍历和分部分反转字符串的方法进行左旋，当有足够的空间，也可以巧用拷贝字符的方法对字符串进行左旋。