【算法】双指针-OJ题详解1

avatar
作者
筋斗云
阅读量:0

双指针-OJ题

移动零(点击跳转)

在这里插入图片描述

原理讲解

在这里插入图片描述在这里插入图片描述

因此我们定义两个指针:

  • cur:遍历数组
  • dest:已处理的区间内,最后一个非零元素的位置

这样就把数组划分成三块区间:
[0 , dest] 、[dest+1 , cur-1] 、[cur , size-1]
分别对应:
非零元素、零、待处理

具体操作:
cur遍历过程中

  • 遇到0元素
    cur++;
  • 遇到非0元素
    swap(dest+1,cur); //swap数组中下标为dest+1和cur的元素
    dest++;cur++;

代码实现

void moveZeroes(vector<int>& nums) {     int dest = -1;     int cur = 0;     while (cur < nums.size())     {         if (nums[cur])             swap(nums[++dest], nums[cur]);         cur++;     } } 

复写零(点击跳转)

在这里插入图片描述

原理讲解

这道题首先要想到从后向前遍历,因为如果从前向后遍历,会覆盖掉后面的值,较难操作,因此:
在这里插入图片描述在这里插入图片描述
第一步找到最后一个数,可以用快慢指针来实现:cur指针、dest指针。前者从前向后遍历,后者根据前者位置的值走1步或2步,具体如下:

  • 先判断cur位置的值
  • 若cur位置的值非0,dest向后移动一步;若cur位置的值为0,dest向后移动2步
  • 判断dest位置是否到了结束的位置
  • cur++

代码实现

void duplicateZeros(vector<int>& arr) {     int dest = -1;     int cur = 0;     //找到最后一个数     while (cur < arr.size())     {         if (arr[cur])             dest++;         else             dest += 2;         if (dest >= arr.size() - 1)             break;         cur++;     } //处理特殊情况:cur指向的最后一个数是0,dest越界     if (dest == arr.size())     {         arr[dest - 1] = 0;         cur--;         dest -= 2;     } //复写     while (cur >= 0)     {         if (arr[cur])             arr[dest--] = arr[cur--];         else         {             arr[dest--] = 0;             arr[dest--] = 0;             cur--;         }     } } 

快乐数(点击跳转)

在这里插入图片描述

原理讲解

在这里插入图片描述
最后一定会成环(可以证明,用鸽巢原理)
因此可以通过判断环的起点是否为1,决定返回true还是false

→ 快慢指针
快慢指针有⼀个特性,就是在⼀个圆圈中,快指针总是会追上慢指针的,也就是说他们总会相遇在⼀个位置上。就本题而言,如果相遇位置的值是 1 ,那么这个数⼀定是快乐数;如果相遇位置不是 1 ,那么就不是快乐数。

代码实现

//求x每一位数的平方和     int SqSum(int x)     {         int ret = 0;         while(x)         {             int n = x%10;             ret += n*n;             x/=10;         }         return ret;     }      bool isHappy(int n) {         int slow = n,fast = SqSum(n);//fast不能设成n,否则进不了循环         while(slow != fast)         {             slow = SqSum(slow);             fast = SqSum(SqSum(fast));         }         return slow==1;     } 

盛最多水的容器(点击跳转)

在这里插入图片描述

原理讲解

我们首先想到的大概率是两层循环暴力枚举,但是复杂度高,这道题不能通关

那应该如何解这题呢?
首先,容器的容积(这道题只考虑面积)是S = h * w
h表示高度,即height[?]
w表示宽度,即两条垂线间隔的距离

为了方便叙述,我们假设左边边界height[left]小于右边边界height[right]

如果此时我们固定⼀个边界,改变另⼀个边界,水的容积会有如下变化形式:

  • 容器的宽度w一定变小。
  • 由于左边界较小,决定了水的高度。①如果改变左边界,新的水面高度不确定,但是一定不会超过右边的柱子高度,因此容器的容积可能会改变(可能变大、变小、不变)。
  • ②如果改变右边界,无论右边界移动到哪里,新的水面的高度一定不会超过左边界,也就是不会超过现在的水面高度,但由于容器的宽度减小,因此容器的容积⼀定会变小的。

所以我们可以舍去情况②,只需要讨论情况①(因为我们的目的是求最大的容积)

因此,我们定义两个指针left和right,然后比较height[left]height[right],移动height小的位置的指针,循环这个过程,期间产生的所有的容积里的最大值,就是要return的最终答案

代码实现

    int maxArea(vector<int>& height) {         int left = 0;         int right = height.size()-1;         int _max = 0;         while(left < right)         {             int tmp = (right-left)*min(height[right],height[left]);             _max = max(_max,tmp);             if(height[left] < height[right])                 left++;             else                 right--;          }         return _max;     } 

有效三角形的个数(点击跳转)

在这里插入图片描述

原理讲解

我们小学五年级都学过,三角形的三条边必须满足:任意两边之和大于第三边、任意两边之差小于第三边~

假设三角形三条边长度分别为:a, b, c

  • 方法① a+b < c ; a+c < b ; b+c < a

  • 方法② 在①的基础上优化:先排序,a ≤ b ≤ c,只需要判断 a+b > c即可

解法一:三层循环暴力枚举 → O(n3)

解法二:利用(排序后)单调性,用双指针算法来解决。 → O(n2)

  • 先固定最大的数
  • 在最大数的左边区间内,用双指针算法,快速统计出符合要求的另外两个数:
    • 如果 nums[left] + nums[right] > nums[max],说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[max] 大的二元组,此时满足条件的有 right - left 种;此时 right 位置的元素的所有情况相当于全部考虑完毕, right-- ,进入下一轮判断
    • 如果 nums[left] + nums[right] <= nums[max],说明 left 位置的元素是不可能与 [left + 1, right] 位置上的任意元素构成满足条件的二元组,left++ 进入下一轮循环
  • 向左移动最大数,循环上面的过程

代码实现

    int triangleNumber(vector<int>& nums) {         int left,right;         int cmax = nums.size() - 1;         int ret = 0;         sort(nums.begin(),nums.end());         while (cmax > 1) {             left = 0;             right = cmax-1;             while (left < right) {                 if (nums[left] + nums[right] > nums[cmax]) {                     ret+=(right-left);                     right--;                      } else {                     left++;                 }             }             cmax--;//向左移动最大数         }         return ret;     } 

查找总价值为目标值的两个商品(点击跳转)

在这里插入图片描述

原理讲解

类比上面《有效三角形的个数》,会发现利用单调性同样很香:利用对撞指针优化时间复杂度

  • 初始化 leftright 分别指向数组的左右两端
  • 接下来无非三种情况:
    • price[left] + price[right] == target,说明找到了,跳出循环返回即可
    • price[left] + price[right] > target,说明两数之和大了,right–
    • price[left] + price[right] < target,说明两数之和小了,left++

代码实现

    vector<int> twoSum(vector<int>& price, int target) {         int left = 0,right = price.size()-1;         vector<int> ret;         while(left < right)         {             if(price[left] + price[right] == target)             {                 ret.push_back(price[left]);                 ret.push_back(price[right]);                 break;             }             else if(price[left] + price[right] > target)                 right--;             else                 left++;          }         return ret;     } 

或者不需创建vector直接返回:

    vector<int> twoSum(vector<int>& price, int target) {         int left = 0,right = price.size()-1;         while(left < right)         {             if(price[left] + price[right] == target)                 return {price[left] , price[right]};             else if(price[left] + price[right] > target)                 right--;             else                 left++;         }         return {-1};//注意这里必须return一个数组,目的是照顾编译器,否则编译不通过     } 

三数之和(点击跳转)

在这里插入图片描述

原理讲解

我们可以利用在两数之和那道题的双指针思想,来对暴力枚举做优化:

  • 先排序
  • 然后固定一个数 a
  • 在这个数后面的区间内,利用双指针快速找到两个数之和等于 -a 即可

但是要注意的是,这道题需要有去重操作~
(除了用set,我们可以自己实现)

  • 找到一个结果之后, left 和 right 指针要跳过重复的元素;
  • 当用完⼀次双指针算法之后,固定的 a 也要跳过重复的元素。

代码实现

    vector<vector<int>> threeSum(vector<int>& nums) {         sort(nums.begin(),nums.end());         int i =0,left,right;         vector<vector<int>> vv;         while(i < nums.size()-2)         {             if(nums[i] > 0)                 break;             //left+right             left = i+1;             right = nums.size()-1;             while(left < right && right < nums.size())             {                 if(nums[left] + nums[right] == -nums[i])                 {                     vv.push_back({nums[i],nums[left],nums[right]});                     left++;right--;                     while(left < right && right < nums.size()&&nums[left] == nums[left-1])                         left++;//left跳过重复元素                     while(left < right && right < nums.size()&&nums[right] == nums[right+1])                         right--;//right跳过重复元素                 }                 else if(nums[left] + nums[right] > -nums[i])                     right--;                 else                     left++;             }             i++;             while(nums[i] == nums[i-1] && i<nums.size()-2)                 ++i;//“固定”的数跳过重复元素         }         return vv;       } 

四数之和(点击跳转)

在这里插入图片描述

原理讲解

这道题和上面的《三数之和》几乎一模一样,区别在于多了一层

  • 固定一个数a
  • 在这个数 a 的后面区间上,利用「三数之和」找到三个数,使这三个数的和等于 target - a 即可

代码实现

    vector<vector<int>> fourSum(vector<int>& nums, int target) {         sort(nums.begin(),nums.end());         vector<vector<int>> vv;         int i=0,j,left,right;         while(i<nums.size())         {             j = i+1;             while(j<nums.size())             {                 left = j+1;                 right = nums.size()-1;                 long long aim =  (long long)target-nums[i]-nums[j];//有些用例不强转会越界                 while(left<right)                 {                     int sum =nums[left]+nums[right];                     if(sum == aim)                     {                         vv.push_back({nums[i],nums[j],nums[left],nums[right]});                         left++;right--;                         while(left<right && nums[left] == nums[left-1])                             left++;                         while(left<right && nums[right] == nums[right+1])                             right--;                     }                     else if(sum < aim)                         left++;                     else                         right--;                 }                 ++j;                 while(j < nums.size() && nums[j] == nums[j-1])                     ++j;             }             ++i;             while(i<nums.size() && nums[i] == nums[i-1])                 ++i;         }         return vv;     } 

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!