asp.net做网站后台,关键词竞价广告,广电如何做视频网站,帝国做网站是选择静态还是伪静态算法#xff1a;双指针 双指针快慢指针对撞指针总结 双指针 LeetCode 283.移动零 以上题目要求我们把所有0移动到数组的末尾#xff0c;也就是说#xff0c;我们要把数组转化为以下状态#xff1a; [ 非0区域 ] [ 0区域 ] 像这种把一个数组划分为多个区域的题型#xff0… 算法双指针 双指针快慢指针对撞指针总结 双指针 LeetCode 283.移动零 以上题目要求我们把所有0移动到数组的末尾也就是说我们要把数组转化为以下状态 [ 非0区域 ] [ 0区域 ] 像这种把一个数组划分为多个区域的题型就是数组划分。而数组划分非常适合使用双指针算法。
对于这道题我们可以用两个指针对数组进行动态的区域划分。 其中dest指针维护一段区域表示非0区域cur指针与dest之间的区域是0区域。而cur后面的区域是待处理区域。
也就是我们的数组被划分为了以下情况 [ 非0区域 ] [ 0区域 ] [ 待处理区域 ] 当我们的cur移动后对于一个新的数据就要根据条件来决定把它放到哪一个区域去。当cur指针走到末尾数组就被处理为了 [ 非0区域 ] [ 0区域 ] 也就是题目要求的样子了。
对于本题而言如果新插入的数据是0那就放到cur维护的区域里面此时直接cur即可如果新插入的数据是非0那么就放到dest的末尾为了保证dest不会覆盖掉cur原本维护的0因此要进行一个交换操作。 代码如下
class Solution
{
public:void moveZeroes(vectorint nums) {int dest -1;int cur 0;int sz nums.size();while (cur sz){if (nums[cur])swap(nums[dest], nums[cur]);cur;}}
};LeetCode 75.颜色分类 这一题也是一个区域划分问题根据上一题的思路我们可以把数组划分为以下状态 [ 0区域 ] [ 1区域 ] [ 2区域 ] 相比于上一题这次我们要划分出三个区域来毫无疑问就需要更多的指针来维护区域大致可以划分为 [ 0区域 ] [ 1区域 ] [ 待处理 ] [ 2区域 ] 我们让维护0区域的指针left向右拓展维护2区域的指针right向左拓展以及利用cur指针向右遍历数组 上图中left指针左侧维护了一段0区域left与cur之间维护了一段1区域cur与right之间是待处理区域right右侧是2区域。当cur往后遍历如果遇到一个新的数据就要决定把它放到哪一个区域去 遇到0就交换left与cur的值把0放到left后面一位拓展left指针维护的区域遇到1就直接cur把1放到cur与left之间遇到2就交换--right与cur的值把2放到right的前面一位拓展right维护的区域 要注意的是当把0交给left后cur但是当把2交给right后cur不能移动。因为left后面的一位数一定是符合cur范围要求的也就是区间(left, cur]之间的数据被交换到了cur的位置此时不用判断被交换过来的数据。而right的前面一位数据是不确定的也就是把区间(cur, right)之间的数据交换给了cur。而(cur, right)之间的数据是待处理的不确定数据因此还需要额外判断一次。比如上图中right的前一位数据就是0交换后状态如下 可以看到cur得到的数据是0应该被放到left维护的区域去。
总代码如下
class Solution
{
public:void sortColors(vectorint nums){int left -1;int right nums.size();int cur 0;while (cur right){if (nums[cur] 0)swap(nums[left], nums[cur]);else if (nums[cur] 2)swap(nums[--right], nums[cur]);//交换后不能cur进入下一轮循环在判断一次cur的值elsecur;}}
};快慢指针 LeetCode 202.快乐数 该题的意思是每个数字的下一个数字是该数字所有位的平方和比如 19 的下一位数字就是 1 2 9 2 82 1^{2} 9^{2} 82 129282。一直以这个规则操作下去会出现两种情况 最后该数字变为1那么该数字是快乐数该数字陷入死循环那么该数字不是快乐数 比如19 - 82 - 68 - 100 - 1 最后19变成了1所以19是一个快乐数比如2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4可以发现其陷入了一个死循环从4开始又以4结束那么2就不是一个快乐数
这题的难点不在于如何计算下一位快乐数字而在于如何判断一个数字陷入了死循环。
对于这种循环问题就可以使用快慢指针。
快慢指针规则如下 定义两个变量fast与slowfast走2步slow走一步如果fast走到终点说明没有循环如果fast与slow相遇说明陷入了循环 一开始fast和slow都在起点 fast走两步slow走一步 由于这是一个循环结构当fast进入第二圈循环slow还没有走完第一圈 这个时候由于slow的速度为1fast的速度为2那么每次行动fast与slow的距离就会缩短1最后fast一定可以遇到slow 此时两者相遇说明这是一个循环结构。
因此代码逻辑如下 定义两个变量fast和slowfast走两步slow走一步如果fast变成1那么该数字是快乐数返回true如果fast与slow相遇那么有循环结构该数字不是快乐数返回false 代码如下
class Solution
{
public:int getNextNum(int n) //到下一个数字的函数{int num 0;while (n){int tmp n % 10;num tmp * tmp;n / 10;}return num;}bool isHappy(int n) {int fast n;int slow n;while (fast ! 1){fast getNextNum(getNextNum(fast));//fast走两步slow getNextNum(slow);//slow走一步if (fast slow fast ! 1)//两者相遇有循环return false;} return true;//到这里说明fast 1是快乐数}
};其中有一个注意点就是条件fast slow fast ! 1这里一种情况就是fast虽然和slow相等但是两者都为1此时是快乐数。
比如数字1010 - 1 - 1slow走第一步就是1了fast走两步也是1此时两者相等。 LeetCode 141.环形链表 本题要求判断一个链表中有没有环结构那就是一个循环问题要使用快慢指针。
我们刚刚已经讲解过快慢指针了现在我们直接说明代码逻辑 定义两个指针fast和slowfast走两步slow走一步如果fast为nullptr说明链表无环返回true如果fast与slow相遇说明有环返回false 代码如下
class Solution {
public:bool hasCycle(ListNode* head){ListNode* slow head;ListNode* fast head;while (fast fast-next){fast fast-next-next;slow slow-next;if (fast slow)return true;}return false;}
};注意事项 进入循环时因为fast要走两步因此要判断fast-next是不是空指针否则fast-next--next就是访问空指针行为 LeetCode 142.环形链表II 这道题要求我们求出环形链表的环入口这就麻烦了通过之前的fast与slow的快慢指针追击问题我们已经可以判断是否存在环结构了那么我们要如何求环入口呢
看到以下示意图 现在slow和fast刚好相遇参数含义如下 L从起点到环入口的距离 C环周长 X相遇点和环入口的距离 由于fast的速度是slow的两倍当slow走的距离是L X因此此时fast走了2(L X)的距离。
又由于fast一定经过了起点到入口的L距离因此此时fast在环中走了2(L X) - L L 2X的距离。
假设fast已经在环中转了n圈因此此时fast在环中走了nC X的距离
那么可以列出公式 n C X L 2 X nC X L 2X nCXL2X
变形得到 n C − X L \mathbf{{\color{Red} nC - X L} } nC−XL
这个公式具有重大意义L代表起点到入口的距离nC代表n个环周长X代表当前相遇点与入口的距离。
nC -X整体可以看成(n - 1)C (C - X)而C - X就代表相遇点开始与环入口的优弧的长度。
此时如果让一个指针A从起点开始走L的距离所用的时间和让一个指针B从相遇点开始走n - 1圈外加一个C - X的距离所用的时间是一致的。由于相遇点与环入口距离已经是X了那么指针B最后刚好会走到环入口。而指针A从入口开始走L到达的地方也是环入口因此两者相遇
通过这个公式可知让一个指针从起点开始走一个指针从相遇点开始走两者会在环入口相遇
因此我们的代码逻辑如下 定义两个指针fast和slowfast走两步slow走一步如果fast为nullptr说明链表无环返回nullptr如果fast与slow相遇说明有环开始找环入口 在相遇点定义一个指针B也就是B slow在起点定义一个指针A也就是A head两个指针各自行动速度一致最后A与B相遇的地方就是环入口返回A或B 代码如下
class Solution
{
public:ListNode* detectCycle(ListNode* head){ListNode* fast head;ListNode* slow head;while (fast fast-next){fast fast-next-next;slow slow-next;if (slow fast) // 有环开始找入口{ListNode* A head;ListNode* B slow;while (A ! B)//A与B相遇点就是环入口{A A-next;B B-next;}return A;}}return nullptr; //没有环返回空指针}
};对撞指针 LCR 179.查找总价格为目标值的两个商品 这道题给了一个升序数组要求我们求出数组中任意两个值的和刚好为target。
该数组有一个特点有序数组。像这种在一个有序区间中查找两个元素计算得到固定值的题型就可以使用对撞指针。
如果我们直接暴力解法的话那就是枚举所有两两一对的元素组直到某一对刚好和为target时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
假设现在的数组为[8, 21, 27, 34, 52]target 61
因为数组具有单调性我们可以一开始就枚举最左侧和左右侧的两个元素 当前8 52 60比61小说明我们需要一个更大的值来增大当前总和。那么由于数组升序我们只需要left即可 当前21 52 73比61大说明我们需要一个更小的值来缩小当前总和。那么由于数组升序我们只需要right--即可 当前21 34 55比61小说明我们需要一个更大的值来增大当前总和。那么由于数组升序我们只需要left即可 当前27 34 61我们就找到了目标值返回left与right下标即可。
正是由于数组单调性我们可以通过比大小来进行指针的调整来决定当前总值要变大还是变小如果最后left与right相遇了说明不存在这样的和。
为什么可以这样优化呢看到这个例子 对于34而言其要去枚举除了自己以外的所有值但是当前21 34 55比61小如果把21改为8那只总和只会更小因此我们只需要再枚举比21大的值即可。也就是通过单调性免去了很多不必要的枚举行为。
代码如下
class Solution
{
public:vectorint twoSum(vectorint price, int target){int left 0;int right price.size() - 1;while (left right){if (price[left] price[right] target) //和比target大right--right--;else if (price[left] price[right] target) //和比target小leftleft;elsereturn { price[left], price[right] };}return { 0, 0 };}
};LeetCode 11.盛水最多的容器 本题要求存储的最大水量其实也就是两个下标之间的距离right - left与min(height[left], height[right])的乘积。
如果暴力枚举那么就是枚举出每一对下标然后求出最大面积时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
本题也可以使用双指针的算法水量的值与right - left与min(height[left], height[right])两个变量正相关如果我们利用两个指针向内枚举那么right - left这个值是一直在减小的也就是有一项有单调性。
对于这种如果利用对撞指针下标向内枚举对组成结果的某一项变量的影响是单调的就可以考虑对撞指针。
假设我们已经在边界上定义好了left与right指针 第一个问题就是应该以什么规则进行向内移动指针
移动的过程中水的宽度的一直递减的那么我们就要尽可能找到height高的元素来拔高水量。
比如说当前的两个高度为3和7由于水的高度取决于较低的那个元素因此高度为7的指针无论怎么向内移动水高度都不会超过3而这个过程中宽度又是单调递减的因此right指针向内移动所有的结果都小于当前的水量。
比如这个情况 虽然right向内移动找到了比7更大的元素但是由于此时水高度取决于3而且宽度还变小了最后总水量没有变大。
因此每次都把比元素值较小的那个指针向内移动
代码如下
class Solution
{
public:int maxArea(vectorint height){int left 0;int right height.size() - 1;int ret -1;while (left right){int w right - left;//宽度int h min(height[left], height[right]);//高度ret max(ret, w * h);//更新最大水量//每次都让较小的元素向内枚举if (height[left] height[right])right--;elseleft;}return ret;}
};总结
双指针
数组划分使用双指针算法。
一般处理为[A区域][B区域]...[待处理]这样的格式当新元素符合哪一个区域特性就放到哪一个区域中。
快慢指针
循环问题利用快慢指针来判断是否有循环。
相遇就是有环如果fast走到结尾就是无环。
如果要找循环开始节点一个指针从头开始走一个指针从相遇点开始走最后会在环入口相遇。
对撞指针 在一个有序区间中查找两个元素计算得到固定值的题型使用对撞指针。 如果利用对撞指针下标向内枚举对组成结果的影响是单调的就可以考虑对撞指针。
对撞指针的特点在于利用单调性减小搜索范围。
