[LeetCode][189][Rotate Array]

首先，一点题外话。

这是大学学计算机到现在近6年来的时间，第一次认真刷题（PS：中间学习生涯有各种原因碰过两三道。。。）。

作为一个计算机专业出身的程序媴真的很不称职，本科以来，没写过几次代码，算法，数据结构，数据库也一塌糊涂。一直觉得像OJ这么高深厉害的东西我肯定不会，如今浑浑噩噩已经混到研究生要毕业找工作的阶段了，终于抬起手开始练练代码。

好了，作如上铺垫只是为了说明，我将要写的这一系列日志（不知能不能坚持下来）都是自己平时练习时的思路和收获，对其他人不一定具有参考意义。主要是为了记录自己的思维训练过程，方便以后回顾。

首先感谢LeetCode这个平台。https://oj.leetcode.com/

在LeetCode的Algorithms中Easy级别排在最上面的题就是【189】Rotate Array。所以第一道就是它。

（这里插一句，注册好久了，一直没有做是上一次注册后做的第一道题发现只能用Java或者C++，鄙人不才，只有C就会那么一点点，所以以为LeetCode只支持Java或者C++，就一直没做。这次本来是抱着边学Java边做题的节奏刷题来着，后来才发现，原来LeetCode每道题支持的语言种类不一样。。。

）

题目链接：https://oj.leetcode.com/problems/rotate-array/

题目描述：

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array

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

is rotated to

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

.

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:

Could you do it in-place with O(1) extra space?

做这道题的时候第一反映就是我能不能第一次就按照Hint中提到的只用O(1)的空间复杂度。然后想了半天没思路。

（再插一句，写代码一直有个缺点，总想一步到位，写出perfect令人惊叹的代码，所以每次看书写代码都往难了去做，导致每次写代码用的时间很长，遇到的问题很多，反倒继续不下去了。后来得一同学点播，说这样不行，还不太会呢，就给自己提高难度，应该从简单的一点点练起，要不太慢了。这里是为了给跟我有一样强迫症患者的童鞋提个方法，换个思路，说不定有用。）

忽然想到这，我就想那我就用最笨的方法做吧。

所以，方法一：

1. 用一个链表存储数组中后K个数；

2. 将剩下的数从最后一个开始向后移动K位，将这些数移到目标位置；

3. 再将链表的K个节点的数复制给原数组的前K位。

4. 得到目标数组。

方法一只是个思路啦，因为我链表学的不好，所以代码有问题，在LeetCode上一直没通过。。。一会粘一下我的错误代码，留作日后思考和修改。

方法二：

就在我不断想这道题，准备方法一的时候，我忽然想到了方法二，也就是网上普遍的三次反转法。

1.现将整个数组倒转；

2.将数组的前K位倒转；

3.将数组的剩下n-k位倒转；

4.得到目标数组。

开始写代码：

（补充一句，本人英语也不太好，一开始没读懂题，根据题中例子，以为只是把数组的后k位统一挪到数组前面去，后来才知道是一个循环向右移位的问题。所以这道题在一开始还要对k做个简单处理，这里就直接展示读懂题后正确代码了）：

void rotate(int nums[], int n, int k) {
    
    if(n == 0 || k == 0){
        return;
    }
    
    int i, temp;
    int m = k%n;   //这里就是前面提到的对k做的简单处理，因为是循环移位，所以k可能大于n，对后面的操作不适用，对n取模后得到要移动的m位
    
    for(i = 0; i < n/2; i++){
        temp = nums[i];
        nums[i] = nums[n-1-i];
        nums[n-1-i] = temp;
    }    //第一次翻转，以中间数字为中心，调换位置，所以只要对数组的前一半元素进行操作即可。因为C语言整除的商无论小数点后是多少，都进行舍位操作，所以这里的中间元素的处理是(n/2)；
    
    for(i = 0; i < m/2; i++){
        temp = nums[i];
        nums[i] = nums[m-1-i];
        nums[m-1-i] = temp;
    }    //第二次翻转，对前m位进行翻转，得到前m位的目标位置。
    
    for(i = m; i < (n-m)/2+m; i++){
        temp = nums[i];
        nums[i] = nums[n-1+m-i];
        nums[n-1+m-i] = temp;
    }    //第三次翻转，对剩下的n-m位进行翻转，这里的中间元素要注意一下，因为前面还有m位，所以是(n-m)/2+m,没有测试直接用(n+m)/2是否可以。
    
     /*三次翻转后，得到目标数组。*/
}
           

下面是方法一中未通过的代码，留着日后解决，或者哪位大神好心能帮忙看看~~~

void rotate(int nums[], int n, int k) {
    
    if(n == 0 || k == 0){
        return;
    }
    
    int m = k % n;
    
    typedef struct LNode{
        int data;
        struct LNode * next;
    }ListNode;
    
    ListNode *head, *p, *q;
    head = (ListNode *)malloc(sizeof(ListNode));
    head->data = 0;
    head->next = NULL;
    p = head;
    int i;
    
    for(i = 0; i++; i < m){
        ListNode *node;
        node = (ListNode *)malloc(sizeof(ListNode));
        node->data = nums[n-m+i];
        node->next = NULL;
        p->next = node;
        p = node;
    }
    
    for(i = n-m; i > 0; i--){
        nums[i+m] = nums[i];
    }
    
    q = head->next;
    for(i = 0; i < m; i++){
        nums[i] = q->data;
        q = q->next;
    }
    
}