企业官网建设流程全解析

目录

经典例题复现

1）移动零

算法思路（快慢指针）

算法流程

解题代码

时间复杂度分析

2）复写零

算法思路（反向回填同向双指针）

算法流程

解题代码

时间复杂度分析

3）盛水最多的容器

算法思路（对撞指针）

算法流程

解题代码

算法总结

快慢指针

反向回填同向双指针

对撞指针

经典例题复现

1）移动零

题目链接：283. 移动零 - 力扣（LeetCode）

理解题意：在原数组的基础上操作，将给定数组中的所有零元素移到末尾。

双指针算法被常用作数组分块，操作序列中的元素等题目，本题很明显是数组分块，可利用快慢指针将数组分成两部分——非零元素和零元素。

算法思路（快慢指针）

定义两个指针分别是cur和dest，cur指针用来扫描数组中的元素，dest指针用来记录最后一个非零元素的位置。根据在cur扫描数组的过程中遇到的不同情况，采取不同的措施，实现数组划分。cur扫描完毕之后数组将被划分成两个区域，[ 0,dest ] 区间的非零元素，[ dest+1,cur-1 ]区间的零元素。

算法流程

1. 初始值cur = 0 ,dest = -1;（dest始终指向最后一个非零元素，所以还未开始扫描时指向空）。cur 开始扫描数组。
2. 当 cur 位置上是 0 ：直接 cur++ 以保证 [ dest+1,cur-1 ]区间是零元素；
3. 当 cur 位置上是非零元素 ：dest++（因为dest始终指向最后一个非零元素），将dest位置上的元素和cur位置数的元素交换。完事之后，cur++；

以例题1为例，如图：

解题代码

Java版本代码如下:

class Solution { public void moveZeroes(int[] nums) { //1.定义指针 int cur=0; int dest=-1; //2.遍历数组元素 while(cur<nums.length){ //3.分类处理 if(nums[cur]==0){ cur++; }else{ dest++; swap(dest,cur,nums); cur++; } } } //交换数组元素位置方法 public void swap(int a,int b,int[] nums){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }

C++版本代码如下:

class Solution { public: void moveZeroes(vector<int>& nums) { for(int cur = 0, dest = -1; cur < nums.size(); cur++) { if(nums[cur]) // 处理非零元素 { swap(nums[++dest], nums[cur]); } } } };

时间复杂度分析

整个移动过程只需要 cur 遍历完一遍数组元素即可完成数组划分，则时间复杂度为O(n)，n为数组的元素个数。

2）复写零

题目链接：1089. 复写零 - 力扣（LeetCode）

理解题意：在原来的数组上操作，将数组中的每个0元素都再写一遍放到数组中，其他元素向右平移，数组长度不能改变。

由于要复写元素，那么就需要一个人来记住要被复写的元素，另一个人复写，这就涉及到读操作和写操作的概念了，试想一下，如果从左向右复写，写操作的前提是要读，但写的速度大于读的速度，那么势必就会产生错误，因为此时读的数据就是已经被写过的数据。本题可采用反向回填同向双指针解决。

算法思路（反向回填同向双指针）

从左向右不行，那就从右向左复写元素。定义两个指针cur （初始值0）和dest（初始值-1）。

• 首先就需要找到最后一个被复写的元素：cur从左向右扫描元素，dest 根据cur所在位置上的元素状态（0 / 非0）决定走几下，当dest走到数组末端或越界，cur的位置就是最后一个被复写的元素。
• 先判断dest是否越界，若越界则进行处理，处理后则开始复写cur位置的元素到dest位置的元素。

这时候有人就会比较疑问，为什么要先找到最后一个被复写的元素？为什么dest初始值是-1？

答：①：由于要再复写以便数组中的0元素，那么在数组中有0元素的情况下，势必会导致元素个数超过数组长度，那么末尾的元素就会被丢掉，那你从最后一个元素开始复写，不就会把数组最前面的元素给丢掉了嘛？那结果就一定会是错的啊。所以需要找到最后一个被复写的元素才能开始复写。②：我们要根据cur位置上的值去决定dest一次走几步（复写几遍）去找最后一个被复写的元素，如果一开始dest就在0位置上（实际上就走了一步了），dest始终会多走一步就会导致元素找错。

算法流程

1.初始值 cur = 0，dest = -1；先找到最后一个被复写的元素：

1.1 先判断cur位置数的元素：

▸cur位置上的值为非0：dest++;

▸ cur位置上的值为0：dest+=2；

1.3 最后cur++;

2.预备开始复写：

2.1 先判断dest是否越界：dest<len (数组长度)：

▸dest越界：数组最后一个元素直接改成0，dest+=2;

▸dest没越界，开始复写。

2.2 开始复写：

▸若cur位置为非0：arr[dest++] = arr[cur++]；

▸若粗人位置上为0：arr[dest++] = 0; arr[dest++] = 0; cur++;

重复2.2步骤，知道数组遍历完，复写也就完毕了。

以例题1为例，如图：

解题代码

Java版本代码如下:

class Solution { public void duplicateZeros(int[] arr) { int cur=0; int dest=-1; int n=arr.length; //1.找到最后一个被复写的元素位置 while(cur<n){ if(arr[cur]==0) dest+=2; else dest++; if(dest>=n-1) break; cur++; } //2.处理边界情况 if(dest==n){ arr[n-1]=0; dest-=2; cur--; } //3.开始复写 while(cur>=0){ if(arr[cur]==0){ arr[dest--]=0; arr[dest--]=0; cur--; }else{ arr[dest--]=arr[cur--]; } } } }

C++版本代码如下:

class Solution { public: void duplicateZeros(vector<int>& arr) { // 1. 先找到最后一个数 int cur = 0, dest = -1, n = arr.size(); while(cur < n) { if(arr[cur]) dest++; else dest += 2; if(dest >= n - 1) break; cur++; } // 2. 处理一下边界情况 if(dest == n) { arr[n - 1] = 0; cur--; dest -= 2; } // 3. 从后向前完成复写操作 while(cur >= 0) { if(arr[cur]) { arr[dest--] = arr[cur--]; } else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };

时间复杂度分析

寻找最后一个被复写的元素，从前向后遍历—>O(n)；从后向前复写数组元素—>O(n) ，O(n) + O(n) =O(n)。

3）盛水最多的容器

题目链接：11. 盛最多水的容器 - 力扣（LeetCode）

理解题意：本题就是要找到两个元素的值与下标之差（x轴）所围成面积的最大值。

本题可采用暴力解题思路，枚举任意两个元素，计算面积，最后找到最大值。但这样做势必会导致超时，所以不建议使用暴力解法。由于要找到两边的元素作为 “桶边” ，所以不妨采用对撞指针解决该问题。

算法思路（对撞指针）

首先定义左右指针——left，fight，分别位于数组的左右两侧，两个指针相当于 “桶边” ，如图：

就拿这个数组 [ 1,8,6,2,5,4,8,3,7 ] 例，最开始left在0下标位置，fight在数组末尾，此时left位置上的值明显小于right位置上的数值，根据木桶效应可知，若left不动，无论right怎么移动，此时围成的面积值只会变小；所以只能移动left值。

后续持续这样的操作，通过每次只移动一个边界就可以免去很多不必要的枚举，从而达到提高效率的目的。当left与right相遇时，这期间产生的所有"容量"值中的最大值就是我们要找的值。

算法流程

1. 对撞指针初始值left = 0，right = len-1（数组长度-1）；

2. 先计算“容量”：v = ( right - left ) * min(height [ left ]，height [ right ])。与上一次计算的v值作比较，保留较大者。

3.比较left位置与right位置上的值：

▸若height [ left ] < height [ right ]：left++

▸若height [ left ] > height [ right ]：right--

4.循环步骤3，直到 left==right，此时的v值就是最大容量；

解题代码

Java版本代码如下:

class Solution { public int maxArea(int[] height) { //1.定义对撞指针 int left=0; int right=height.length-1; int maxV=0; //2.循环比较 while(left!=right){ int curV = (right-left)*Math.min(height[left],height[right]); maxV = Math.max(maxV,curV); if(height[left]<height[right]) left++; else right--; } return maxV; } }

C++版本代码如下:

#include <vector> #include <algorithm> using namespace std; class Solution { public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1, ret = 0; while(left < right) { int v = min(height[left], height[right]) * (right - left); ret = max(ret, v); if(height[left] < height[right]) left++; else right--; } return ret; } };

时间复杂度分析

对撞指针的效率一般是双指针算法中最高的，从两头开始遍历，时间复杂度O(n/2)—>O(n)。相较于暴力解法O(n²),效率高太多了。

算法总结

双指针算法一般分为两类，同向双指针和反向双指针（对撞指针）。同向双指针又分为快慢指针和反向回填同向双指针：

但面对不同的应用场景，我们要学会选择合适的算法：

快慢指针

1. 特征 ：快慢指针一般适用于同起点、同一个方向，但是步长不同，快指针跑的更快，慢指针跑的更慢。但绝大多是单链表使用的较多，数组用的相对较少。
2. 使用场景：判断链表中是否有环、环入口，找链表中的点，删除链表中倒数第k个节点

模板特征（以Java为例）：

ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

推荐例题（快去练练叭~）：

• 142. 环形链表 II - 力扣（LeetCode）
• 234. 回文链表 - 力扣（LeetCode）

反向回填同向双指针

1. 特征：同向，都从左往右走；读指针 i 不断向前走，写指针在后面，只有满足一定条件才写入，写完 j++；
2. 使用场景：原地修改数组、除去不需要的元素，保留有效元素在某位置。

模板特征（以Java为例）：

// j：写指针；i：读指针，都从左往右 int j = 0; for (int i = 0; i < nums.length; i++) { if (满足保留条件) { nums[j] = nums[i]; j++; } } // j 就是有效元素长度 return j;

推荐例题（快去练练叭~）：

• 27. 移除元素 - 力扣（LeetCode）
• 80. 删除有序数组中的重复项 II - 力扣（LeetCode）

对撞指针

1. 特征：left再开头，right在结尾，相向而行；一般不修改原数组，用来查找和计算。
2. 使用场景：有序数组两数之和、三数之和，判断回文、反转数组。

模板特征（以Java为例）：

int left = 0, right = n - 1; while(left < right) { // 判断 if(xxx) left++; else right--; }

推荐例题（快去练练叭~）：

• 125. 验证回文串 - 力扣（LeetCode）
• 15. 三数之和 - 力扣（LeetCode）

好啦，关于优选算法中的双指针算法的相关总结就给大家分享到这儿啦！后续我还会持续分享其他算法的相关总结，都在我的《算法》专栏中哦，感兴趣的小伙伴们不妨关注博主，下期见~~