【算法优选】双指针专题——壹

😎前言

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针
对撞指针：⼀般⽤于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。

• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

left == right （两个指针指向同⼀个位置）
left > right （两个指针错开）

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢

🌴移动零

🚩题⽬描述：

给定⼀个数组nums ，编写⼀个函数将所有 0 移动到数组的末尾，同时保持⾮零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进⾏操作。

• ⽰例1:
  输⼊: nums = [0,1,0,3,12]
  输出: [1,3,12,0,0]
• ⽰例2:
  输⼊: nums = [0]
  输出: [0]

class Solution {
    public void moveZeroes(int[] nums) {

    }
}
1
2
3
4
5

🚩算法思路

在本题中，我们可以⽤⼀个cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在cur 遍历期间，使[0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零

🚩算法流程

初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ）

cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：

1. 遇到的元素是0 ， cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内的元素全都是零，因此当cur 遇到0 的时候，直接cur ++ ，就可以让0 在cur - 1 的位置上，从⽽在[dest + 1, cur - 1] 内；

2. 遇到的元素不是0 ， dest++ ，并且交换cur位置和dest位置的元素，之后让cur++ ，扫描下⼀个元素。

• 因为des指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元素，那么它的位置应该在dest + 1的位置上，因此 dest 先⾃增1 ；
• dest++ 之后，指向的元素就是 0元素（因为⾮零元素区间末尾的后⼀个元素就是0 ），因此可以交换到cur所处的位置上，实现 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零。

🚩代码实现

class Solution
{
    public void moveZeroes(int[] nums)
    {
        for(int cur = 0, dest = -1; cur < nums.length; cur++)
            // 仅需处理⾮零元素
            if(nums[cur] != 0) {
                dest++; // dest 先向后移动⼀位
				// 交换
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍀复写零

🚩题⽬描述：

给你⼀个⻓度固定的整数数组 arr ，请你将该数组中出现的每个零都复写⼀遍，并将其余的元素向右平移。
注意：请不要在超过该数组⻓度的位置写⼊元素。请对输⼊的数组就地进⾏上述修改，不要从函数返回任何东西。

• ⽰例1：
  输⼊： arr = [1,0,2,3,0,4,5,0]
  输出： [1,0,0,2,3,0,0,4]
  解释：调⽤函数后，输⼊的数组将被修改为： [1,0,0,2,3,0,0,4]

• 示例 2：
  输入：arr = [1,2,3]
  输出：[1,2,3]
  解释：调用函数后，输入的数组将被修改为：[1,2,3]

class Solution {
    public void duplicateZeros(int[] arr) {

    }
}
1
2
3
4
5

🚩算法思路

如果「从前向后」进⾏原地复写操作的话，由于0的出现会复写两次，导致没有复写的数「被覆盖掉」。

因此我们选择「从后往前」的复写策略。但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：

• 先找到最后⼀个复写的数；

• 然后从后向前进⾏复写操作

🚩算法流程：

1. 初始化两个指针 cur = 0 ， dest = 0 ；

2. 找到最后⼀个复写的数：
   当cur < n的时候，⼀直执⾏下⾯循环：

• 判断cu位置的元素:
  ◦ 如果是0的话， dest 往后移动两位；
  ◦ 否则， dest 往后移动⼀位。
• 判断dest时候已经到结束位置，如果结束就终⽌循环；
• 如果没有结束， cur++ ，继续判断。

3. 判断dest 是否越界到 n 的位置： 如果越界，执⾏下⾯三步：

• n - 1 位置的值修改成 0 ；
• cur 向移动⼀步；
• dest 向前移动两步。

4. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
   判断 cur位置的值：

• 如果是0 ： dest 以及 dest - 1位置修改成0 ， dest -= 2 ；
• 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；

cur-- ，复写下⼀个位置

🚩代码实现

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, n = arr.length;
        // 1. 先找到最后⼀个需要复写的数
        while(cur < n) {
            if(arr[cur] == 0) {
                dest += 2;
            } else {
                dest += 1;
            }
            if(dest >= n - 1) {
                break;
            }
                cur++;
        }
        // 2. 处理⼀下边界情况
        if(dest == n)  {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3. 从后向前完成复写操作
        while(cur >= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

⭕总结

关于《【算法优选】双指针专题——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！一起加油