Rotate Array 继续续

继续用C语言来完成这道题,给出的函数和参数为

void rotate(int nums[], int n, int k) {
    
}

一个数组,一个长度,一个旋转移动次数

考虑C语言可不能想脚本语言那样才想问题,比如对于[1, 2, 3, 4, 5,6],n = 6, k = 2

[1, 2, 3, 4, 5, 6] ==》 [5, 6, 1, 2, 3, 4]

[1, 2, 3, 4, 5, 6]

[4, 3, 2, 1, 6, 5]

[5, 6, 1, 2, 3, 4]

以数据n和k来确认分割的地方,左右两边都进行一次reverse,之后整个list再进行一次reverse即可

第一次提交:

void reverse(int nums[], int m, int n){
    int tmp = 0;
    while (m++ != n--){
        tmp = nums[n];
        nums[n] = nums[m];
        nums[m] = tmp;
    }
}


void rotate(int nums[], int n, int k) {
    k = k % n;
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
    reverse(nums, 0, n - 1);
}

自我感觉还很自信,结果

Submission Result: Runtime Error

Last executed input:	[1], 0

这就坑了,最基本的test case都出错了,看了看n=1,k=0,进入reverse函数,我也是醉了,while变成了一个死循环或者是根本不执行,修改一下条件继续

第二次提交

void reverse(int nums[], int m, int n){
    int tmp = 0;
    while (m++ < n--){
        tmp = nums[n];
        nums[n] = nums[m];
        nums[m] = tmp;
    }
}


void rotate(int nums[], int n, int k) {
    k = k % n;
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
    reverse(nums, 0, n - 1);
}

继续错误,信息如下

Submission Result: Wrong Answer
Input:		[1,2,3], 1
Output:		[2,1,3]
Expected:	[3,1,2]

这里test case中,n = 3, k = 1,唉,自作聪明while里面两变量弄个++,–,弄巧成拙,还没开始交换,就已经自加自减了,自然交换的元素错位了

第三次提交

void reverse(int nums[], int m, int n){
    int tmp = 0;
    while (m < n){
        tmp = nums[n];
        nums[n] = nums[m];
        nums[m] = tmp;
        ++m;
        --n;
    }
}


void rotate(int nums[], int n, int k) {
    k = k % n;
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
    reverse(nums, 0, n - 1);
}

结果终于被接收了

33 / 33 test cases passed.
Status: Accepted
Runtime: 11 ms

 

看到了交换既然能够定位到分割点进行操作,干嘛不直接更换呢

[1, 2, 3, 4, 5, 6] ==》 [5, 6, 1, 2, 3, 4]

[1, 2, 3, 4, 5, 6]

[5, 1, 2, 3, 4, 6]

[5, 6, 1, 2, 3, 4]

下表k的移到0,前面的后移动一位

下标k+1的移到1,中间的后移动一位

提交

void rotate(int nums[], int n, int k) {
    k = k % n;
    int i;
    int j;
    int tmp = 0;
    for (i = n - k; i < n; i++){
        tmp = nums[i];
        for (j = n - k - 1; j >= 0; j--)
            nums[j + 1] = nums[j];
        nums[j] = tmp;
    }
}

测试了一把,错误

Submission Result: Runtime Error
Last executed input:	[1,2], 1

仔细看了看循环,貌似是有问题的,每次内部for循环结束,j都为0,那么列表的第一个元素每次都会被覆盖???这显然是不对的

[1, 2, 3, 4, 5, 6]

[5, 1, 2, 3, 4, 6]

[5, 6, 1, 2, 3, 4]

nums[n-k] = 5,覆盖nums[0]

nums[n-k+1] = 6,覆盖nums[1]

再次提交一次

void rotate(int nums[], int n, int k) {
    k = k % n;
    int i;
    int j;
    int tmp = 0;
    for (i = n - k; i < n; i++){
        tmp = nums[i];
        for (j = n - k - 1; j >= 0; j--)
            nums[j + 1] = nums[j];
        nums[i - n + k] = tmp;
    }
}

悲剧的是,依然错误了

Input:	[1,2,3], 2
Output:	[2,3,3]
Expected:	[2,3,1]

看上去好像是最后一个元素覆盖错了,原因就是内层循环,n – k – 1是一个常数,根本每次进入内层循环,要遍历的次数都是一致的,显然这是不对的,应该次数是递减,这里n – k – 1应该用i – 1来代替,还有j > = 0,这里的0应该也是递增,用i – n + k 代替,再次提交

void rotate(int nums[], int n, int k) {
    k = k % n;
    int i;
    int j;
    int tmp = 0;
    for (i = n - k; i < n; i++){
        tmp = nums[i];
        for (j = i - 1; j >= i - n + k; j--)
            nums[j + 1] = nums[j];
        nums[i - n + k] = tmp;
    }
}

终于被接受了

33 / 33 test cases passed.
Status: Accepted
Runtime: 354 ms

总之就一句话:我的C语言真是烂~!!!!!!

发表回复