C语言双指针多方法旋转数组解题LeetCode

关于“C语言双指针多方法旋转数组解题LeetCode”的攻略如下：

问题描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

解题思路

考虑使用双指针的方法进行旋转。首先，指定一个指针 $L$ 指向数组的最左侧，再指定一个指针 $R$ 指向从最右端起第 $k$ 个位置。接着，利用双指针交换数组元素，即将 $L$ 指向的元素和 $R$ 指向的元素依次交换。然后，左侧指针 $L$ 向右移动一位，右侧指针 $R$ 向左移动一位，重复执行上述交换操作，直到两指针相遇。

但是，这样的操作只能将前面的 $n-k$ 个元素依次移动到数组的后面去。而后面的 $k$ 个元素则没有移动，需要再次进行旋转。因此又可以使用刚才的双指针方法进行旋转，只不过需要改变一下指定的两个指针的位置。

具体过程可以分为以下三步：

1. 对整个数组进行一次旋转，将最后 k 个元素旋转至数组的最前面
2. 对前面 $n-k$ 个元素进行一次旋转
3. 整个数组旋转后，元素的顺序就是所要求的结果

下面分别介绍各个步骤的具体实现。

步骤1：对后面 k 个元素进行旋转

首先，定义一个指针 $L$ 指向数组的最左侧（即下标为 0 的位置），再定义指针 $R$ 指向从最右端起第 $k$ 个位置（即下标为 n-k 的位置）。接着，利用双指针交换数组元素，即将 $L$ 指向的元素和 $R$ 指向的元素依次交换。然后，左侧指针 $L$ 向右移动一位，右侧指针 $R$ 向左移动一位，重复执行上述交换操作，直到两指针相遇。

下面是代码实现：

void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    if (k == 0) return;
    int L = 0, R = numsSize - k - 1;
    while(L < R){
        int temp = nums[L];
        nums[L] = nums[R];
        nums[R] = temp;
        L++; R--;
    }
}

步骤2：对前面 n-k 个元素进行旋转

接着，定义一个指针 $L$ 指向数组的最左侧（即下标为 0 的位置），再定义指针 $R$ 指向从最右端起第 $k+1$ 个位置（即下标为 n-1 的位置）。接着，利用双指针交换数组元素，即将 $L$ 指向的元素和 $R$ 指向的元素依次交换。然后，左侧指针 $L$ 向右移动一位，右侧指针 $R$ 向左移动一位，重复执行上述交换操作，直到两指针相遇。

下面是代码实现：

void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    if (k == 0) return;
    int L = 0, R = numsSize - 1 - k;
    while(L < R){
        int temp = nums[L];
        nums[L] = nums[R];
        nums[R] = temp;
        L++; R--;
    }
}

步骤3：整个数组旋转

上述两个步骤完成后，整个数组的顺序已经发生了变化，但此时整个数组还没有完全按要求旋转。因此，还需要使用上述两个步骤再次对整个数组进行旋转。

下面是完整的代码实现：

void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    if (k == 0) return;
    int L = 0, R = numsSize - k - 1;
    while(L < R){
        int temp = nums[L];
        nums[L] = nums[R];
        nums[R] = temp;
        L++; R--;
    }
    L = 0, R = numsSize - 1 - k;
    while(L < R){
        int temp = nums[L];
        nums[L] = nums[R];
        nums[R] = temp;
        L++; R--;
    }
    L = 0, R = numsSize - 1;
    while(L < R){
        int temp = nums[L];
        nums[L] = nums[R];
        nums[R] = temp;
        L++; R--;
    }
}

示例说明

下面给出两个示例，以说明以上算法的正确性。

示例1：

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

旋转前 : 1 2 3 4 5 6 7

旋转后1 : 7 6 5 4 3 2 1

旋转后2 : 5 6 7 4 3 2 1

旋转后3 : 5 6 7 1 2 3 4

示例2：

输入: nums = [-1,-100,3,99], k = 2

输出: [3,99,-1,-100]

解释:

旋转前 : -1 -100 3 99

旋转后1 : 99 3 -100 -1

旋转后2 : 3 99 -1 -100

在以上两个示例中，输入的数组经过旋转后，得到的输出数组与要求一致。因此，算法的正确性可以得到验证。