C语言——oj刷题——字符串左旋和轮转数组

第一题：字符串左旋

问题：

实现一个函数，可以左旋字符串中的k个字符。

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

实现：

当我们谈到字符串左旋时，我们指的是将字符串中的字符向左移动一定数量的位置。这个问题在编程中非常常见，特别是在字符串处理和算法实现中。

在C语言中，我们可以使用一种简单而有效的方法来完成字符串的左旋操作。下面是一个示例代码，演示了如何实现字符串左旋：

#include <stdio.h>
#include <string.h>
 
void reverse(char* str, int start, int end) {
    while (start < end) {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}
 
void leftRotateString(char* str, int k) {
    int len = strlen(str);
    k = k % len;  // 处理k大于字符串长度的情况
    reverse(str, 0, k - 1);  // 反转前k个字符
    reverse(str, k, len - 1);  // 反转剩余的字符
    reverse(str, 0, len - 1);  // 整体反转字符串
}
 
int main() {
    char str[] = "abcdefg";
    int k = 2;  // 左旋2个位置
 
    printf("原始字符串: %s\n", str);
    leftRotateString(str, k);
    printf("左旋后的字符串: %s\n", str);
 
    return 0;
}

在上面的示例代码中，我们定义了两个辅助函数：reverse和leftRotateString。

reverse函数用于反转字符串中指定范围内的字符。它使用两个指针（start和end）来遍历字符串，交换对应位置上的字符，直到两个指针相遇。

leftRotateString函数是实现字符串左旋的核心函数。它首先计算旋转位置k与字符串长度的余数，以处理k大于字符串长度的情况。然后，它分别对前k个字符、剩余字符和整个字符串进行反转操作，最终完成字符串的左旋。

在main函数中，我们定义了一个示例字符串"abcdefg"和旋转位置k为2。我们先打印出原始字符串，然后调用leftRotateString函数进行左旋操作，最后打印出左旋后的字符串。

运行上述代码，输出将是：

原始字符串: abcdefg

左旋后的字符串: cdefgab

这就是用C语言完成字符串左旋的方法和示例代码。希望对你有所帮助！如果有任何问题，请随时提问。

第二题：轮转数组（力扣189）

解法一：（暴力解法）

利用循环每次移动一位，代码如下：

//暴力做法

void rotate(int* nums, int numsSize, int k){
    k=k%numsSize;
    int temp;
    while(k--)
    {
        temp=nums[numsSize-1];
        for(int i=numsSize-1;i>0;i--)
        {
            nums[i]=nums[i-1];
        }
        nums[0]=temp;
    }

这种做法应该很好理解，但它的时间复杂度是O（n^2）的，会超时。

解法二：（时间换空间）

利用额外的数组实现，把移动完的数据放在一个新的数组里面去，然后再拷贝回来，代码如下:

void rotate(int*nums,int numsSize,int k)
{
    k=k%numsSize;
    int i,j;
    int a[100000];
    j=numsSize-k;
    for(i=0;i<k;i++) a[i]=nums[j++];
    j=0;
    for(;i<numsSize;i++) a[i]=nums[j++];
    for(i=0;i<numsSize;i++)
    {
        nums[i]=a[i];
    }
}

这样的解法时间复杂度符合要求，但是需要额外的空间实现。

解法三：（前后翻转）

先旋转前面的那部分，在旋转后面的那部分，然后再旋转整个数组。

void swap(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
void reverse(int *begin,int *end)
{
    while(begin<end)
    {
        swap(begin,end);
        begin++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    k=k%numsSize;
    reverse(nums,nums+numsSize-k-1);
    reverse(nums+numsSize-k,nums+numsSize-1);
    reverse(nums,nums+numsSize-1);
}

解法四：（环状旋转）

解题思路：

把数组看成一个环状的。按照题目的意思，我们应当让每一个元素往后面走k步,假设x为元素下标，那么它应该到（x+k）%numsSize的地方上去，如图：

我们想把1挪到4的位置上去，直接挪的话，4就会消失，那怎么办呢？可以这样做，申请一个变量temp，先让temp=nums[0]，然后temp与nums[3]交换

此时，1已经到4的位置上去了，而4被保留在temp当中,接下来当然是让4到它应当去的位置。

接下来同理：

我们要做到把所有的元素都遍历一遍，都找到它应该去的位置就可以了，我们可以用一个cnt变量来记录遍历了多少个元素，起初从nums[0]开始走，如果走了一圈之后还有元素没有遍历到的话，那就接下来从nums[1]开始走再走一圈，以此类推，显然我们需要两层循环，当cnt==numsSize的时候，就可以结束遍历了。虽然是两重循环，但是时间复杂度是O(N),因为每个元素只被遍历一次。代码如下：

void swap(int* a, int* b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}
void rotate(int* nums, int numsSize, int k)
{
    int cnt = 0;
    int temp, p;
    for (int start = 0; start < numsSize; start++)
    {
        temp = nums[start];
        p = start;
        do
        {
            p = (p + k) % numsSize;
            swap(&temp, &nums[p]);
            cnt++;
        } while (p != start);
        if (cnt == numsSize) break;
    }
 
}