[蓝桥杯算法从小白到大牛]双指针系列(一)

        那么接下来的贴子就是开始讲解算法了,在这个系列里的每个类型的算法题至少会讲解3道,每一步搞了什么会讲解的特备详细,希望对小伙伴们有所帮助,我写的如果有哪里不对的地方请指出来哦!让我们一起进步吖

鸡汤

        算法题听起来是真的高大上,但是只要我们多做几遍一定能吃透,我是每道题都做了至少3遍,但是小伙伴们肯定比我学的又快又好,刚开始不会写没关系,完整看完这篇文章以后再从头看一遍!

双指针重要技巧

        常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针.

第一种对撞指针：⼀般⽤于顺序结构中，也称左右指针.

• 对撞指针从两端向中间移动.⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近.
• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循

环），也就是：

                (1)left == right （两个指针指向同⼀个位置）

                (2)left > right （两个指针错开）

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

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

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

1->题目链接

LeetCode---移动零

2->题目讲解顺序?

1. 一起读懂题目;
2. 理解算法原理;
3. 编写代码;

3->一起读懂题目

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

示例 1:

输入: nums = [0,1,0,3,12];

输出: nums = [1,3,12,0,0];

示例 2:

输入: nums = [0];

输出: nums = [0];

我对题目的理解:把数组nums中的0全部放在数组后边,非0元素就是把他们之间的0扔到后边了,非0元素之间相对位置保持不变,如[0,1,0,3,12]你就理解为1,3,12,放到前边了最后变成[1,3,12,0,0]

4->算法原理

像这里我们要使用的就是对撞指针,顾名思义两个指针一个在左,一个在右边,向对方逼近!!本质利用的其实是快速排序的思想!!!

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

算法流程：

        a. 初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。

因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ）

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

        i. 遇到的元素是 0 ， cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内

的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1

的位置上，从⽽在 [dest + 1, cur - 1] 内；

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

• 因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元

素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 ；

• dest++ 之后，指向的元素就是 0 元素（因为⾮零元素区间末尾的后⼀个元素就是0 ），因此可以交换到 cur 所处的位置上，实现 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零

5->编写代码解题

这里就没什么好说的了,上边的原理已经讲解的清清楚楚了,只需要把思路用代码的方式写出来就行

小伙伴们一定要自己先动手利用上边的思路自己写,不会了在回过头来看哦

最后的代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cur = 0, dest = -1;//初始化两个指针
        for(; cur < nums.size(); cur++)
            if(nums[cur] != 0) // 处理⾮零元素
                swap(nums[++dest], nums[cur]);//注意++dest是让dest先向后移动一位,这时nums[dest]一定等于0,nums[cur]一定是非0
                                              //因为我们规定在交换后dest指向的一定是最后一个非0元素,交换以后就万事大吉了
    }
};

最后我写的希望对小伙伴们有所帮助,我写的如果有哪里不对的地方请指出来哦!让我们一起进步吖

任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖