【算法】双指针算法

这篇具有很好参考价值的文章主要介绍了【算法】双指针算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页 : zxctscl
如有转载请先通知

1. 283. 移动零

【算法】双指针算法,算法,算法,双指针,c++,开发语言

1.1 分析

一、题目分析
要将0放在所有数组的最后,而且非零元素的顺序保持不变,要求原地对数组进行移动。

二、算法原理
用两个指针来讲数组进行划分,一个cur:从左往右扫描数组,遍历数组;一个dest:已经处理的区间内,非零元素的最后一个位置。
就将数组分为3个区间:非零:[0,dest];0区间:[dest+1,cur-1];待处理的区间:[cur,n-1].
要想这样划分,cur就得从前往后在遍历的过程中,遇到0元素,就加加;遇到非零元素,就将dest+1位置和cur位置的值交换。
【算法】双指针算法,算法,算法,双指针,c++,开发语言

【算法】双指针算法,算法,算法,双指针,c++,开发语言

1.2 代码

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]);
            }
        }

    }
};

2. 1089. 复写零

【算法】双指针算法,算法,算法,双指针,c++,开发语言

2.1 分析

一、题目解析
要求每次遇到0就复写,而且不能改变原数组的长度。

二、算法原理
如果用双指针从前往后遍历,就拿例1来说,
就会出现值被覆盖的情况:
【算法】双指针算法,算法,算法,双指针,c++,开发语言
所以遍历顺序就不能从前往后。
那么就把顺序改为从后往前遍历,但是不能超过原数组的长度,就得先找一下cur和dest开始的位置。
可以先用双指针算法:1.先判断cur位置;2.决定dest向后移动一步或者两步;3.判断一下dest是否已经到达结束位置;4.在把cur加加。
但是可能会出现dest越界的情况,如果n-1位置为0,那么cur就减减,dest就减2。
最后在从后往前开始复写0。

【算法】双指针算法,算法,算法,双指针,c++,开发语言

2.2 代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
    int cur=0,dest=-1;
    int n=arr.size();
    while(cur<n)
    {
        if(arr[cur])dest++;
        else dest+=2;
        if(dest>=n-1)break;
        cur++;
    }
    if(dest==n)
    {
        arr[n-1]=0;
        cur--;
        dest-=2;
    }

    while(cur>=0)
    {
        if(arr[cur])arr[dest--]=arr[cur--];
        else 
        {
            arr[dest--]=0;
            arr[dest--]=0;
             cur--;
        }
    }
    }
};

3. 202. 快乐数

【算法】双指针算法,算法,算法,双指针,c++,开发语言

3.1 分析

一、题目分析
题目中所说最后的平方和为1才是快乐数,如果不为1,就一直循环,其实可以看成两个都是循环,一个一直循环的是1,另一个循环的值都不相同。只需要判断循环里面的值是不是为1就可以。

二、算法原理
先用一个变量sum记录最后平方和,然后把最后一位平方,然后删掉原来的数,一直重复这个过程,直到最后一位为0,最后返回这个平方和sum。

定义两个快慢指针,用平方和来充当指针,slow指向第一个数,fast指向第二个数,如果这两个指针一直不相等,就一直循环,slow走一步,fast走两步。直到两个相遇为止,等于1就是快乐数,不等于就不是。
【算法】双指针算法,算法,算法,双指针,c++,开发语言

3.2 代码

class Solution {
public:
    int bitsum(int n)
    {
        int sum=0;
        while(n)
        {
            int t=n%10;
            sum+=t*t;
            n/=10;
        }
       return sum;
    } 
    bool isHappy(int n) {
      int slow=n,fast=bitsum(n);
      while(slow!=fast)
      {
        slow=bitsum(slow);
        fast=bitsum(bitsum(fast));
      }
      return slow==1;
    }
};

4. 11. 盛最多水的容器

【算法】双指针算法,算法,算法,双指针,c++,开发语言

4.1 分析

一、题目分析
题目中的数组代表每一条线的高度,来求最大的容积,来看一下例1:
【算法】双指针算法,算法,算法,双指针,c++,开发语言
选择的高度是8和7,但是题目要求不能倾斜,这里选择高度的就是7,宽度就是下标之间的差值8-1也就是7,那么容积最大就是7*7=49。

二、算法原理
用两个指针来记录容器两边的高度,可以直接先选择最大的宽度,记录下这个容积。
如果左边指针走一步,宽度在减小,高度可能会出现比之前的小,那么体积就比原来的小;高度如果不变,那么宽度减小,那么总容积也是在减小的。所以得干掉高度小的那一个值。
如果两个指针指向的值相等,那么干掉谁都可以,然后继续枚举里面相乘的容积,直到两个指针相遇,最后返回容积最大的值就行。
【算法】双指针算法,算法,算法,双指针,c++,开发语言

4.2 代码

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

5. LCR 179. 查找总价格为目标值的两个商品

【算法】双指针算法,算法,算法,双指针,c++,开发语言

5.1 分析

一、题目分析
只需要找到两个数,他们的和等于目标值就可以,但是题目中的数组是按照升序排列的,暴力解法会超时,就不考虑了。

二、算法原理
利用数组是有序的,用双指针算法来算。
定义两个指针,一个在左边,一个在右边。
先计算两个指针指向值的和,判断一下和目标值的大小,会出现三种情况:1.小于目标值,那么左边指针就加加;2.等于就返回这两个值;3.大于目标值,那么右边指针就减减。
【算法】双指针算法,算法,算法,双指针,c++,开发语言

5.2 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
    int left=0,right=price.size()-1,sum=0;
    while(left<right)
    {
        sum=price[left]+price[right];
        if(sum<target)left++;
        else if(sum>target)right--;
        else return{price[left],price[right]};
    }
    return {-1,-1};
    }
};

6. 15. 三数之和

【算法】双指针算法,算法,算法,双指针,c++,开发语言

6.1 分析

一、题目分析
题目要求返回三元数组和为1的三个不同的数,而且要求去重,来看一下例1:
它里面有[-1,0,1]、[0,1,-1]、[-1,2,-1],但是第一组和第二组的元素是相同的,就只能返回一个。
【算法】双指针算法,算法,算法,双指针,c++,开发语言
为了避免去重,可以先给数组排个序。

二、算法原理
排序之后,数据是有序的,这里就用双指针算法。
这里是三个数的和,可以先固定一个数a,仅想要保证这个a是小于0就行(在后面等于0相加的值不可能等于0),然后在该数后面的区间内,利用双指针算法,快速找到两个数的和,者两个数的和是a的相反数,这样这三个数相加的时候,值就为0。
这里还有可能不止一种情况,所以不要漏掉,在找到一种情况时候,左边指针和右边指针继续缩小区间找,直到两个指针相同。
那么怎么去重,已经是有序的数组,那么连续相同值的情况就不考虑了,就是在左边指针和右边指针已经找到值,就跳过重复的值。当使用完重复的元素时候,固定值也得跳过重复值。还得避免越界的情况。
【算法】双指针算法,算法,算法,双指针,c++,开发语言

6.2 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());

        vector<vector<int>> ret;
        int n=nums.size();
        for(int i=0;i<n;)
        {
          if(nums[i]>0)break;
          int left=i+1,right=n-1,target=-nums[i];

            while(left<right)
            {
                int sum=nums[left]+nums[right];
                 if(sum<target) left++;
                 else if(sum>target)right--;
                 else
                 {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    left++;right--;
                    while(left<right&&nums[left]==nums[left-1])left++;
                     while(left<right&&nums[right]==nums[right+1])right--;
                    }

            }
            i++;
            while(i<n&&nums[i]==nums[i-1])i++;

        }
        return ret;

    }
};

有问题请指出,大家一起进步!!!文章来源地址https://www.toymoban.com/news/detail-857462.html

到了这里,关于【算法】双指针算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】指针进阶:字符指针&&数组指针&&函数指针

    ✨作者:@平凡的人1 ✨专栏:《C语言从0到1》 ✨一句话:凡是过往,皆为序章 ✨说明: 过去无可挽回, 未来可以改变 🌹 感谢您的点赞与关注,同时欢迎各位有空来访我的 🍁平凡舍 回想之前,我们学了 指针 的一些基础👉 指针与结构体 我们知道了指针的概念: 指针就是

    2023年04月08日
    浏览(42)
  • c语言指针(深入了解指针)

    前沿:       有人曾说过不会指针等于没有学习c语言,而我也是非常认同这个观点的,要想学习好c语言,指针是比不可缺少的,如果指针学不会c语言也就没办法学好,而向如此越重要的东西越比较难学,但难学并不代表学不会,这片文章将由简单到复杂让你深刻的了解指针

    2023年04月08日
    浏览(44)
  • 【C语言】——指针四:字符指针与函数指针变量

      在前面的学习中,我们知道有一种指针类型为 字符指针: c h a r ∗ char* c ha r ∗ 。下面我们来介绍它的使用方法。    使用方法:      如果我们想 存储字符串 ,可以用什么方法呢?之前我们一般都是用 字符数组 ,那还有什么办法呢?其实, 字符指针 也是可以

    2024年04月12日
    浏览(43)
  • 双指针算法,基础算法实践,基本的算法的思想,双指针算法的实现

    双指针算法是一种常用于解决数组和链表问题的算法技巧。它的核心思想是使用两个指针在数据结构中按照一定的规则移动,从而达到快速搜索或处理数据的目的。这个技巧通常用于 优化算法 , 降低时间复杂度 ,提高程序的执行效率。双指针算法有多种应用场景,以下是其

    2024年02月11日
    浏览(38)
  • 【C语言进阶】指针数组 —— 数组指针

    🎬 鸽芷咕 : 个人主页  🔥 个人专栏 : 《C语言进阶篇》 《C语言初阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊,前面我们已经把指针大部分内容给学完了,今天就给大家带来数组指针or指针数组!    ⛳️ 很多说这俩名字不是差不

    2024年02月14日
    浏览(35)
  • C语言 二级指针和多级指针

    什么是二级指针? 假设: 如上,p是指针变量,寄存的是a的地址,指向的是元素a 那么,指针变量p有地址吗?指针变量p的指针指向的是? 答案是有的,指针变量也有地址,并且指针变量p也有着指向它地址的指针变量pp,也因为指针pp变量指向的地址是指针变量p的,而指针变

    2024年02月13日
    浏览(35)
  • C语言 ——指针数组与数组指针

    目录 一、二维数组 二、指针数组 (1)概念  (2)书写方式 (3)指针数组模拟二维数组 三、数组指针 (1)概念 (2)使用数组指针打印一维数组  (3)模拟二维数组的传参 首先,我们要理解一下二维数组和指针变量之间的一些相关概念。 二维数组 : int arr [ 3 ][ 5 ]  

    2024年02月13日
    浏览(48)
  • 【C语言】初阶指针(指针及其类型以及野指针)

    简单不先于复杂,而是在复杂之后。 目录 1. 指针是什么? 2. 指针和指针类型  2.1  指针+-整数 2.2 指针的解引用  3. 野指针  3.1 野指针成因  3.2 如何规避野指针  指针理解的两个要点: 1. 指针是内存中最小单元的编号,也就是地址。 2. 平时口语中说的指针,通常指的是指

    2023年04月16日
    浏览(47)
  • C语言--指针详解(下)--字符指针、数组指针、指针数组、函数指针、函数指针数组(转移表)

    在C语言中有一种指针类型为字符指针 char*,常用其来表示字符,使用如下: 除了上述用法之外,还可以有以下的用法: 在上面的代码中,字符 \\\" hello word \\\"是常量字符串,将\\\"hello word\\\"放入 pstr 指针的实质是将第一个字符 “ h \\\" 的地址传递给了 pstr ,通过首字符 ” h \\\" 就可以访问

    2024年02月03日
    浏览(47)
  • 【C语言】指针的基本知识详细讲解(指针数组、数组指针、函数指针....

    接着上次的函数的基本知识,今天我们来讲一讲🔍指针 目录 一、指针的概念 二、指针变量 三、野指针 四、字符指针 五、指针与数组 六、指针数组 七、数组指针  八、指针与函数 总结 一、指针的概念 1.1、变量和地址 所谓指针,也就是内存的地址;所谓指针变量,也就是

    2023年04月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包