猿创征文 | 14天刷爆LeetCode算法学习计划——Day02双指针（2）

一、前言

盲目刷题只会让自己心态爆炸，所以本期14天算法学习计划，也是LeetCode上的 [算法] 学习计划，在本专栏的每一篇文章都会整理每一天的题目并给出详细题解，以及知识点的整理

二、知识点

反转数组，顾名思义就是把数组倒过来，有点类似链表反转(见下方链接)，比如[1,2,3,4,5]数组进行反转以后就是[5,4,3,2,1]，数组的反转就相对更加简单一点，不用考虑节点的问题，其核心还是双指针，因为反转的本质是两个数对调

链表——单链表的反转

三、LeetCode189. 轮转数组

1.题目

LeetCode189. 轮转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步:[7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例2:
输入： nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步:[99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

2.解题示意图

• 首先要把整个数组倒过来
• 将k个数再倒回来
• 将剩下的数倒回来
  
  在图中有个分割线，分割线前的元素个数就是k，以此为界限，分别反转，达到题目要求的效果

3.解题思路

1. 由于要反转三次，所以要定义一个方法来实现数组反转
2. 每次交换完成后起始指针的值要加1，末尾指针的值要减1
3. 翻转整个数组
4. 翻转k个元素（前半部分）
5. 翻转剩下的元素（后半部分）

4.代码实现

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        //提高代码效率，防止k与数组长度相同时出现运行错误的情况
        k %= n; 
        //翻转整个数组
        reverse(nums, 0, n-1);
        //翻转k个元素（前半部分）
        reverse(nums, 0, k-1);
        //翻转剩下的元素（后半部分）
        reverse(nums, k, n-1);  
    }
    //定义翻转方法
    public void reverse(int[] arr, int start, int end){
        while(start < end){
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.验证代码

6.注意点

k %= n一定要写，不然当 k=nums.length 时就会出现运行结果错误的情况，读者朋友可以自己在力扣网上试验一下

四、结语

本题要实现代码很简单，但是要想到思路还是比较困难的，如果有更加简单或者别的思路的话欢迎留言评论