🍬题目描述：
实现一个函数，可以左旋字符串中的k个字符。例如：
- ABCD左旋一个字符得到BCDA
- ABCD左旋两个字符得到CDAB
🍭思路一：
要左旋 k 个字符，我们首先应该考虑左旋 1 11 个字符怎么做。左旋一个字符分为以下的三步：
取出字符串中最左边的一个字符
将字符串中剩下的字符按从左到右的顺序依次左移一位
把第一步取出来的字符放到第二步结束得到的字符串的末尾
知道左旋 1 11 个字符的做法，那左旋 k 个字符就只需要把上面的步骤重复执行 k 次就可以。分析的差不多了，接下来上代码：
void left_move(char arr[], int k)//k为左旋次数 { int len = strlen(arr);//计算字符串的长度 int i = 0; for (i = 0; i < k; i++)//循环执行k次 { //1：取出字符串中最左边的一个字符 char tmp = arr[0]; //2:将字符串中剩下的字符按从左到右的顺序依次左移一位 int j = 0; for (j = 0; j < len - 1; j++)//除了第一个字符，还剩len-1个字符 { arr[j] = arr[j + 1]; } //3:把第一步取出来的字符放到第二步结束得到的字符串的末尾 arr[len - 1] = tmp; } } int main() { char arr[] = "ABCDE" ; left_move(arr, 2); printf("%s\n", arr); return 0; }
🍡代码优化：
上面的代码已经可以满足题目的要求，但是还可以进行优化。上面的字符串一共只有 5 55 个字符串，如果我们要左旋 7 77 个字符，那其实就相当于左旋 2 22 个字符。如果就按照上面的代码，那左旋 7 77 个字符可是要比左旋 2 22 个字符多浪贵一些时间，但它们两个最终得到的结果却是一样的，有没有什么办法能够把左旋 7 77 个字符变成左旋 2 22 个字符呢？答案是有的。这里问题的关键出在循环次数 k 的身上，当左旋 7 77 个字符时，只要让 k=2 就可以。因此我们可以在进入 for 循环之前加入下面这句代码： k%=len;。这样一来就可以大大优化代码的运行时间。分析的差不了，接下来上代码：
void left_move(char arr[], int k)//k为左旋次数 { int len = strlen(arr);//计算字符串的长度 k %= len;//重中之重 int i = 0; for (i = 0; i < k; i++) { //1：取出字符串中最左边的一个字符 char tmp = arr[0]; //2:将字符串中剩下的字符按从左到右的顺序依次左移一位 int j = 0; for (j = 0; j < len - 1; j++)//出了第一个字符，还剩len-1个字符 { arr[j] = arr[j + 1]; } //3:把第一步取出来的字符放到第二步结束得到的字符串的末尾 arr[len - 1] = tmp; } } int main() { char arr[] = "ABCDE" ; left_move(arr, 7); printf("%s\n", arr); return 0; }
虽然优化后的代码，在某些情况下运行时间会有所下降，但整体来看，这种方法还是存在大量的字符移动，效率还是比较低的，接下来介绍一种更加高效的方法。
🍭思路二：
思路二只需要对字符串进行三次逆序就可以。
- 先逆序左边的 k 个字符
- 再逆序剩下的 len-k 个字符
- 最后逆序整个字符串
以上动图就是左旋两个字符的过程。分析的差不多了，接下来上代码：
void reverse(char* left, char* right)//逆序函数，只要知道待逆序字符串中第一个字符的地址和最后一个地址就可以 { assert(left && right);//判断指针的有效性 while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } void left_move(char arr[], int k) { int len = strlen(arr); k %= len; //1:先逆序左边的 `k` 个字符 reverse(arr, arr + k - 1); //2:再逆序剩下的 `len-k` 个字符 reverse(arr + k, arr + len - 1); //3:最后逆序整个字符串 reverse(arr, arr + len - 1); } int main() { char arr[] = "ABCDE"; left_move(arr, 7); printf("%s\n", arr); return 0; }
本题到这里就结束了，在本题的基础上还衍生出来了下面这道题，还请各位看官继续往下看。
🍬题目描述：
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。例如：给定s1 =AABCD和s2=BCDAA，返回1；给定s1=abcd和s2=ACBD，返回0。AABCD左旋一个字符得到ABCDA，AABCD左旋两个字符得到BCDAA，AABCD右旋一个字符得到DAABC。
🍭思路一：
我们首先判断两个字符串的长度是否相等，如果长度不相等，那必不可能通过旋转一个字符串而得到另一个字符串。如果对于两个字符串 s1 和 s2 ，它们的长度相等，那只需要取其中的一个字符串每次旋转一个字符，然后与另一个字符串比较，看是否相等，此时就可以用到上面的字符串左旋函数了。分析的差不多了，接下来上代码：
void reverse(char* left, char* right)//逆序函数，只要知道待逆序字符串中第一个字符的地址和最后一个地址就可以 { assert(left && right);//判断指针的有效性 while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } void left_move(char arr[], int k) { int len = strlen(arr); k %= len; //1:先逆序左边的 `k` 个字符 reverse(arr, arr + k - 1); //2:再逆序剩下的 `len-k` 个字符 reverse(arr + k, arr + len - 1); //3:最后逆序整个字符串 reverse(arr, arr + len - 1); } int is_left_move(char* s1, char* s2) { //先判断两个字符串的长度是否相等 int len1 = strlen(s1); int len2 = strlen(s2); if (len1 != len2)//如果长度不相等就直接返回0 { return 0; } int i = 0; for (i = 0; i < len1; i++)//对s1旋转，然后与s2比较 { left_move(s1, 1);//每次旋转一个字符 if (strcmp(s1, s2) == 0) { return 1; } } return 0;//代码执行到这里说明s1旋转了一轮和s2都不相等 } int main() { char s1[] = "AABCD"; char s2[] = "BCDAA"; int ret = is_left_move(s1, s2); if (ret == 1) { printf("YES\n"); } else { printf("NO\n"); } return 0; }
上面的代码可以实现题目的要求，但是这种方法比较依赖字符串旋转函数，接下来介绍一种更加巧妙地方法。
🍭思路二：
在字符串 s1 的后面追加上 s1 ，得到一个新的字符串 s3 ，看 s2 是不是 s3 的一个字串，如果是，那说明 s1 可以通过旋转得到 s2 ，如果不是，那说明无法通过旋转 s1 得到 s2 。
接下来上代码：
int is_left_move(char* s1, char* s2) { int len1 = strlen(s1); int len2 = strlen(s2); if (len1 != len2)//如果两个字符串的长度不相等就直接返回0 { return 0; } char* s3 = strncat(s1, s1, len1);//strncat是字符串追加函数 if (strstr(s3, s2) != NULL)//strstr是子串查找函数 { return 1;//如果s2是s3的一个子串，说明可以通过旋转s1得到s2，就返回1 } return 0;//如果代码执行到这里，说明s2不是s3的一个子串，说明不能通过旋转s1得到s2，就返回0 } int main() { char s1[20] = "AABCDF"; char s2[] = "BCDFAA"; int ret = is_left_move(s1, s2); if (ret == 1) { printf("YES\n"); } else { printf("NO\n"); } return 0; }
🎶结语：
今天首先介绍了两种旋转字符串的方法，思路一是比较常规的方法，思路二就比较巧妙，通过三次逆序就实现了字符串旋转，大大提高了效率。紧接着，在字符串旋转的基础上又介绍了：一个字符串能否通过另一个字符串旋转得到的问题，利用字符串自身追加结合查找子串巧妙地解决了这一问题。
今天的分享到这里就结束啦，以上的内容如果对你有帮助的话，可以动动小手点赞、评论、收藏，你的支持就是我前进路上最大的动力！
