字符串循环左移算法实现

"字符串左旋是一种常见的编程问题，通常出现在笔试和面试中，涉及到字符串处理。该操作将字符串中的字符循环向左移动指定位置。本文介绍了一种空间复杂度为O(1)、时间复杂度为O(n)的字符串左旋实现方法。" 在字符串左旋操作中，给定一个字符串`a`和一个整数`k`，目标是将字符串`a`的每个字符向左移动`k`个位置，保持字符串长度不变。例如，字符串"abcdef"左旋2位后变成"cdefab"。这个问题可以通过不同的算法来解决，但这里介绍的方法利用了最大公约数（GCD）的概念。 函数`fun(char a[], int k, int n)`是实现字符串左旋的核心，其中`a`是待处理的字符串，`k`是左旋的位数，`n`是字符串的长度。首先，`k`需要取模`n`，以确保它在字符串的有效范围内。接下来，计算`k`和`n`的最大公约数`d`，这是由于`d`次之后，字符串会恢复原状，因此只需处理`d`个字符即可。 通过双重循环实现左旋。外层循环遍历`d`个字符，内层循环根据`k`的步长移动并赋值。在这个过程中，为了避免重复赋值导致的错误，引入变量`last`来记录最后一个被赋值的位置，并使用`tmp`作为临时存储。当`j`回到初始位置`i`时，需要将`tmp`的值赋给`a[last]`，然后继续下一轮赋值。 为了计算最大公约数`d`，使用欧几里得算法`gcd(int I, int j)`，通过不断交换`i`和`j`的值，直到它们相等，此时的值就是两者的最大公约数。 这个算法的时间复杂度是O(n)，因为它遍历了整个字符串一次。空间复杂度是O(1)，因为它只使用了常数个额外变量，不依赖于输入字符串的长度。 理解和实现字符串左旋的关键在于找到合适的方法处理字符的循环移动，同时确保在有限的内存空间内完成操作。这个特定的实现方式既简洁又高效，是处理此类问题的一个好选择。在实际编程中，掌握这样的算法对于提升问题解决能力和优化代码性能都至关重要。