网站开发目录结构,clannad制作公司,佛山免费自助建站模板,花生壳免费域名注册网站文章目录 实现原理实现思路典型例题移动0复写0快乐数盛最多水的容器有效三角形的个数三数之和四数之和 总结 在快速排序或者是其他和数组有关的题目中#xff0c;有很经典的一类题目是关于数组划分的#xff0c;数组划分就是把数组按照一定的规则划分为不同的区间#xff0c… 文章目录 实现原理实现思路典型例题移动0复写0快乐数盛最多水的容器有效三角形的个数三数之和四数之和 总结 在快速排序或者是其他和数组有关的题目中有很经典的一类题目是关于数组划分的数组划分就是把数组按照一定的规则划分为不同的区间使得达到某种目的
首先先看实现的原理是什么
实现原理
两个指针的作用
cur从左向右扫描数组遍历数组
dest已处理的区间内非零元素的最后一个位置
数组划分就是把数组划分成三个区间
[0dest]、[dest1cur-1]、[curn-1]
而这三个区间就对应到了题目要求的区间假设现在有这样的题目 那经过区间划分就可以把[0dest]划分为非0的区域[dest1cur-1]划分为只有0的区间而剩下的就是待处理的区间
实现思路
有了上面的理论基础实现思路就简单多了
我们让cur从前向后遍历如果cur遇到0元素就让cur因为cur相当于是一个用来探路的指针而dest的作用就是用来进行区间的划分于是根据这个原理当cur遇到了非0的元素时就让dest再让cur和dest这两个位置的元素进行一次交换交换后的结果就达到了把非0元素交换到前面0元素换到后面的结果
技巧
永远让dest初始值为-1cur的初始值为0并且让cur最后更变值可以有效处理掉很多越界问题
典型例题
先看几个简单的题目熟悉这个算法的思路
移动0 void moveZeroes(vectorint nums)
{int cur0;int dest-1;while(curnums.size()){if(nums[cur]0){cur;}else{dest;swap(nums[dest],nums[cur]);cur;}}
}看上述代码就严格执行了刚才代码的思路 如果cur遇到0元素就让cur 当cur遇到了非0的元素时就让dest再让cur和dest这两个位置的元素进行一次交换 复写0 既然通篇介绍的主要是双指针算法那这个题也要使用双指针的基本原理
如果此题可以创建多个数组那么创建一个数组上面一个指针控制原数组下面控制新数组如果是0就填入两个0如果不是0就填入该数字到达对应数量就不再进行写入数据
但这里要求不能够使用额外的空间因此就要把异地的双指针变成原地双指针
那原地双指针如何实现
首先原地的双指针问题在于如果从前向后遍历当遍历到的数字是0写入两个0后原来的数据就被覆盖掉了这样就会一直进行0的循环因此解决方案就是从后向前遍历
那么接下来思考如何遍历一个从最后开始那另外一个显然这是下一个需要解决的问题另外一个部分应该从哪里开始 通过这里画图也能看出cur的位置其实就是复制结束后的位置那么这个位置的寻找过程就是下一步要进行的问题
cur应该如何寻找其实又可以演化为双指针的问题从开始找当遇到0就向后走两次遇到非0就走一次那么这样就可以找到cur
这样的思路是没有问题的但是也有特殊情况如果最后元素是0那dest向后走两步不就越界了吗因此这里也需要对边界做特殊处理如果边界为0那么就让最后输出的dest和cur向前一步走即可避免越界的情况出现
class Solution
{
public:void duplicateZeros(vectorint arr) {int cur0,dest-1,narr.size();while(curn){if(arr[cur]0){dest2;}else{dest;}if(destn-1){break;}cur;}if(destn){arr[n-1]0;cur--;dest-2;}while(cur0){if(arr[cur]0){arr[dest--]arr[cur];arr[dest--]arr[cur--];}else{arr[dest--]arr[cur--];}}}
};快乐数 这个题思路也很奇特先模拟一下实现的流程
情景1 情景2 此时对题意就有了基本了解那么这个图其实和链表中的环形链表很相似我们其实就可以把他抽象成一个环形链表的相遇问题当相遇的时候如果对应的值不是1那么就证明这里并不是快乐数相反就是快乐数
因此这个题就很好解决了本质上这个原理和环形链表的快慢指针的过程是一样的
class Solution
{
public:int CalRes(int num){int res 0;while (num){res (num % 10) * (num % 10);num num / 10;}return res;}bool isHappy(int n) {int num n;int slow CalRes(num);int fast CalRes(CalRes(num));while (slow ! fast){slow CalRes(slow);fast CalRes(CalRes(fast));}if (fast 1){return true;}else{return false;}}
};盛最多水的容器 本题设计也很巧妙但依旧是利用双指针来解决知道了双指针的解决原理后解决并非难事
一个从左走 一个从右走 根据木桶效应计算出结果后要舍弃小的部分继续向内遍历使得最终时间复杂度控制在O(N)内
class Solution
{
public:int maxArea(vectorint height){int left 0;int right height.size() - 1;int v 0;int max 0;while (left right){v min(height[left], height[right]) * (right - left);if (v max){max v;}if (height[left] height[right]){left;}else{right--;}}return max;}
};有效三角形的个数 看到这个题第一思路是直接暴力枚举三次for循环直接找但最后是通过不了的时间复杂度过高了因此这里还是使用双指针的解法但是要利用单调性进行解决
首先对于三个数字我们要进行判断的时候如果这个数字是单调排序的比如这里是升序排序那么只需要判断前两个数相加的和大于第三个数即可因此根据这个原理我们就可以采取下面的思维方式
依据单调性采用双指针解决问题
这个算法的思路就是先固定右边最大的数字作为最大的数倒数第二大的数字为right左边的数为left
如果此时leftright固定那么此时left右边的数同样符合条件那么只需要right--即可
如果此时leftright固定那么此时left后面的数也不符合要求就让left
循环结束后再通过挪动右边的数进行循环这样时间复杂度在O(N^2)的基础上就解决了这个问题
class Solution
{
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int cut0;for(int maxnums.size()-1;max2;max--){int left0,rightmax-1;while(leftright){if(nums[left]nums[right]nums[max]){cutright-left;right--;}else{left;}}}return cut;}
};三数之和 此题难度在于代码实现的细节处理和去重的问题上
代码思路有两数之和的思路铺垫整体难度不大控制住其中一个进行另外两个数据的相加即可但在边界的处理上需要进行一些操作
最后是去重的操作去重的操作是很重要的一步细节很多要处理区间内的去重和区间外单独的去重
vectorvectorint threeSum(vectorint nums)
{vectorvectorint v;// 排序sort(nums.begin(),nums.end());for(int i0;inums.size();){// 优化if(nums[i]0){break;}int lefti1,rightnums.size()-1;while(leftright){if(nums[left]nums[right]nums[i]0){right--;}else if(nums[left]nums[right]nums[i]0){left;}else{v.push_back({nums[i],nums[left],nums[right]});left;right--;// 去重1while(leftright nums[left]nums[left-1]){left;}while(leftright nums[right]nums[right1]){right--;}}} // 去重2i;while(inums.size() nums[i]nums[i-1]){i;}}return v;
}四数之和 代码思路和三数之和基本相同注意long long问题即可
class Solution
{
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint v;// 排序sort(nums.begin(),nums.end());// 控制第一个数for(int i0;inums.size();){// 控制第二个数for(int ji1;jnums.size();){// 在区间内找int leftj1,rightnums.size()-1;while(leftright){long long tmp(long long)nums[i]nums[j]nums[left]nums[right];if(tmptarget){right--;}else if(tmptarget){left;}else{v.push_back({nums[i],nums[j],nums[left],nums[right]});left;right--;// 去重while(leftright nums[left]nums[left-1]){left;}while(leftright nums[right]nums[right1]){right--;}}}// 对固定数去重j;while(jnums.size() nums[j]nums[j-1]){j;}}i;while(inums.size() nums[i]nums[i-1]){i;}}return v;}
};总结
双指针问题是入门算法题但却有很大的使用场景具体来说当要进行数组划分和数组分块的时候可以选择先进行排序进行有序数组
对于有序数组来说利用单调性解决问题是常见的手段在实际应用题目中有很大的利用价值
