【优选算法篇】：双指针算法--开启高效编码的两把“魔法指针”，练习题演练

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

在这里插入图片描述

文章目录

  • 一.双指针算法
  • 二.例题
    • 1.移动零
    • 2.复写零
    • 3.快乐数
    • 4.盛水最多的容器
    • 5.有效三角形的个数
    • 6.和为s的两个数
    • 7.三数之和
    • 8.四数之和

一.双指针算法

双指针算法(Two Pointers Algorithm)，又称快慢指针算法，龟兔赛跑算法等，是一种在链表，数组，矩阵等数据结构中，通过设置两个指针，并通过特定的移动策略来遍历数据元素同时解决问题的编程技巧。

双指针的分类：

  • 对撞指针：两个指针方向相反移动
  • 快慢指针：两个指针方向相同，但移动速度不同，通常快指针每次移动的距离大于慢指针
  • 分离双指针：两个指针分别属于不同的数组或者链表

双指针算法的优势：

双指针算法最核心的用途是优化时间复杂度。原本两个指针有n2中组合，时间复杂度是O(n2)。而双指针算法通过运用单调性，使得指针只能单项移动，因此总的时间复杂度只有O(n)。

下面通过几个例题来讲解双指针的使用技巧

二.例题

1.移动零

链接：leetcode.283.移动零

题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

void moveZeroes(vector<int>& nums) {
    //双指针算法
    int cur=0;
    int dest=-1;
    while(cur<nums.size()){
        //cur指针遇到0，cur向前移动
        if(nums[cur]==0){
            cur++;
        }
        //cur指针遇到非0，交换cur指针和dest+1指针指向的值，交换完后两个指针再向前移动
        else{
            swap(nums[cur],nums[dest+1]);
            dest++;
            cur++;
        }
    }
}

2.复写零

链接：leetcode.1089.复写零
题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

void duplicateZeros(vector<int> &arr)
{
    int cur = 0;
    int dest = -1;

    // 先找到复写后的最后一个元素位置
    while (dest < (int)arr.size() - 1)
    {
        if (arr[cur])
        {
            dest += 1;
        }
        else
        {
            dest += 2;
        }
        if (dest < arr.size() - 1)
        {
            cur++;
        }
    }

    // 处理边界情况
    if (dest == arr.size())
    {
        arr[arr.size() - 1] = 0;
        cur--;
        dest -= 2;
    }

    while (cur >= 0)
    {
        // cur指针遇到非0元素，复写一次，两个指针都往前移动一次
        if (arr[cur])
        {
            arr[dest--] = arr[cur--];
        }
        // cur指针遇到0元素，复写两次，dest指针先移动一次，两个指针再一起移动一次
        else
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
    }
}

3.快乐数

链接：leetcode.3.快乐数
题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

int number(int n)
{
    int sum = 0;
    while (n)
    {
        int m = n % 10;
        n /= 10;
        sum += m * m;
    }

    return sum;
}
bool isHappy(int n)
{
    int slow = n;
    int fast = number(n);
    while (slow != fast)
    {
        slow = number(slow);
        fast = number(number(fast));
    }

    return slow == 1;
}

4.盛水最多的容器

链接：leetcode.11.盛最多水的容器
题目：

在这里插入图片描述

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

int maxArea(vector<int> &height)
{
    // 定义两个左右指针
    int left = 0;
    int right = height.size() - 1;

    // 获取小的高度
    int min = height[left] < height[right] ? height[left] : height[right];

    // 求出当前容量假设为最大值
    int vmax = min * (right - left);

    // 左右两个指针向内移动，容器的宽度减少，想要获取更大的容量，只能找到大的高度
    // 也就是舍弃小的高度，移动找大的高度
    while (left < right)
    {
        if (height[left] < height[right])
        {
            left++;
        }
        else
        {
            right--;
        }

        min = height[left] < height[right] ? height[left] : height[right];

        int v = min * (right - left);

        if (v > vmax)
        {
            vmax = v;
        }
    }

    return vmax;
}

5.有效三角形的个数

链接：leetcode.5.有效三角形的个数
题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

int triangleNumber(vector<int>& nums) {
    //先将数组进行排序，可以减少三角形的判断情况
    sort(nums.begin(),nums.end());

    //设置最大值的指针max,在max指针左区间设置两个做右指针有来查找符合的组合
    int max=nums.size()-1;
    int left=0;
    int right=max-1;

    //设置变量size用来记录可以组合的个数
    int size=0;

    while(max>0){
        //如果左指针值加上右指针值大于max指针最大值，[left,right-1]区间都符合，求出个数
        //右指针减一
        if(left<right&&nums[left]+nums[right]>nums[max]){
            size+=(right-left);
            right--;
        }
        //如果左指针值加上右指针值小于等于max指针最大值，left指针加一
        else{
            left++;
        }
        //当左右指针相遇时，从新设置最大值，在[left,max-1]区间继续查找
        if(left>=right){
            max--;
            left=0;
            right=max-1;
        }
     }

     return size;
}

6.和为s的两个数

题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

vector<int> twosum(vector<int>& nums,int target){
    int left = 0;
    int right = nums.size() - 1;
    vector<int> v;

    while(left<right){
        if(nums[left]+nums[right]<target){
            left++;
        }
        else if(nums[left]+nums[right]>target){
            right--;
        }
        else{
            v.push_back(nums[left]);
            v.push_back(nums[right]);
            break;
        }
    }

    return v;
}

7.三数之和

链接：leetcode.7.三数之和
题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

因为题目要求返回的是数组元素，不是下标，所以可以先对数组进行排序，使其递增排列，这样就能使用两数之和的思想。除此之外还有一个注意点就是，每次找到符合要求的组合后，在移动指针时要判断是否会出现重复元素，如果出现重复元素要去重，减少不必要的遍历，可以降低时间复杂度。

代码实现：

vector<vector<int>> threesum(vector<int>& nums){
    //先将数组进行排序
    sort(nums.begin(), nums.end());
    //定义一个二维数组用来存放组合数组
    vector<vector<int>> vv;

    //定义三个指针
    int i = 0;
    int left = i + 1;
    int right = nums.size() - 1;

    int target = 0 - nums[i];

    //i指针指向的是小于等于零的元素，这样可以保证三数之和为0
    while(nums[i]<=0&&left<right){
        if(nums[left]+nums[right]>target){
            right--;
        }
        else if(nums[left]+nums[right]<target){
            left++;
        }
        else{
            vv.push_back({nums[i],nums[left++],nums[right--]});
            
            //左右指针遇到相等元素时，跳过去重
            //处理边界情况，左指针要保证在右指针的左边，右指针要保证在左指针的右边
            while(left<right&&nums[left]==nums[left-1]){
                left++;
            }
            while(right>left&&nums[right]==nums[right+1]){
                right--;
            }
        }

        //当出现左右指针相等或者互换方向时，重新设置i指针的值，同时i指针也要去重
        //处理边界情况，i可能会越界
        if(left>=right){
            i++;
            while(i+1<nums.size()&&nums[i-1]==nums[i]){
                i++;
            }
            left=i+1;
            right = nums.size() - 1;
            target = 0 - nums[i];
        }
    }

    return vv;
}

8.四数之和

链接：leetcode.18.四数之和
题目：

在这里插入图片描述

算法原理：

四数之和这里就不再详细地讲解算法原理，其实就是三数之和的改版，在三数之和的基础上再增加一个指针

i指针固定第一个数，j指针固定第二个数，两数之和值=target-nums[i]=nums[j]

在三数之和的基础上增加一个循环，同时也要注意去重

如果前面两数之和，三数之和明白算法原理后，这里四数之和就会比较轻松。所以一定要先明白前面两个，再来尝试解这道题

代码实现：

vector<vector<int>> foursum(vector<int>& nums,int target){
    //先排序
    sort(nums.begin(),nums.end());

    vector<vector<int>> vv;

    int left, right;

    //i指针固定第一个值
    for(int i=0;i<nums.size();){
        //j指针用来固定第二个值
        for (int j = i + 1; j < nums.size();){
            long long targetj = (long long)target - nums[i] - nums[j];
            left = j + 1;
            right = nums.size() - 1;

            while(left<right){
                if(nums[left]+nums[right]>targetj){
                    right--;
                }
                else if(nums[left]+nums[right]<targetj){
                    left++;
                }
                else{
                    vv.push_back({nums[i], nums[j], nums[left++], nums[right--]});

                    //去重，同时处理边界情况
                    while(left<right&&nums[left]==nums[left-1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        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;
}

以上就是关于双指针算法的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/930255.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Figma入门-旋转效果

Figma入门-旋转效果

Figma入门-旋转效果 前言 在之前的工作中&#xff0c;大家的原型图都是使用 Axure 制作的&#xff0c;印象中 Figma 一直是个专业设计软件。 最近&#xff0c;很多产品朋友告诉我&#xff0c;很多原型图都开始用Figma制作了&#xff0c;并且很多组件都是内置的&#xff0c;对…
阅读更多...
ffmpeg转码与加水印

ffmpeg转码与加水印

文章目录 转码 与加水印引入jar包代码ffmpeg安装错误解决方法 转码 与加水印 引入jar包 <dependency><groupId>net.bramp.ffmpeg</groupId><artifactId>ffmpeg</artifactId><version>0.6.2</version></dependency>代码 impo…
阅读更多...
网络原理 网络协议栈

网络原理 网络协议栈

POSIX API与网络协议栈 unix有不同的衍生版本&#xff0c;针对不同的版本&#xff0c;通过Posix定义了一套标准的操作系统接口API&#xff0c;使得不同的开发版本可以使用相同的API调用&#xff0c;具有可移植性。 网络连接相关API&#xff1a; 客户端 socket() bind() con…
阅读更多...
将vscode上的项目提交到github上

将vscode上的项目提交到github上

1.windows终端中 创建github仓库 创建完成 提交代码 git init git config --global user.email "fuyulai2024163.com" git config --global user.name "Fuyulai-Hub" git add . git commit -m "first commit" git remote add origin https://g…
阅读更多...
P4645 [COCI2006-2007#3] BICIKLI(Tarjan+topsort求到某点的方案数）

P4645 [COCI2006-2007#3] BICIKLI(Tarjan+topsort求到某点的方案数）

P4645 [COCI2006-2007#3] BICIKLI - 洛谷 | 计算机科学教育新生态 思路&#xff1a; 我们考虑输出inf的情况&#xff0c;可以发现当从1出发到2经过的任意一个点处于一个环内时&#xff0c;路径条数是无穷多的。 有向图上从s到t的经过点&#xff0c;就是从s出发所能经过的所有…
阅读更多...
Linux C/C++编程中的多线程编程基本概念

Linux C/C++编程中的多线程编程基本概念

【图书推荐】《Linux C与C一线开发实践&#xff08;第2版&#xff09;》_linux c与c一线开发实践pdf-CSDN博客《Linux C与C一线开发实践&#xff08;第2版&#xff09;&#xff08;Linux技术丛书&#xff09;》(朱文伟&#xff0c;李建英)【摘要 书评 试读】- 京东图书 (jd.com…
阅读更多...
MongoDB整合SpringBoot

MongoDB整合SpringBoot

MongoDB整合SpringBoot 环境准备 1.引入依赖 <!--spring data mongodb--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-mongodb</artifactId> </dependency> 2.配置yml spr…
阅读更多...
记录过程校准器：精准测量的未来驱动力与市场蓝海

记录过程校准器：精准测量的未来驱动力与市场蓝海

在科技日新月异的今天&#xff0c;精确测量已成为工业制造、科学研究、环境监测等众多领域的核心要素。记录过程校准器&#xff0c;作为确保测量设备准确性和可靠性的关键工具&#xff0c;正扮演着越来越重要的角色。随着智能制造、物联网技术的快速发展&#xff0c;以及全球对…
阅读更多...
【NLP 9、实践 ① 五维随机向量交叉熵多分类】

【NLP 9、实践 ① 五维随机向量交叉熵多分类】

目录 五维向量交叉熵多分类 规律&#xff1a; 实现&#xff1a; 1.设计模型 2.生成数据集 3.模型测试 4.模型训练 5.对训练的模型进行验证 调用模型 你的平静&#xff0c;是你最强的力量 —— 24.12.6 五维向量交叉熵多分类 规律&#xff1a; x是一个五维(索引)向量&#xff…
阅读更多...
STM32使用RCC（Reset Clock Contorl，复位时钟控制器）配置时钟以及时钟树

STM32使用RCC（Reset Clock Contorl，复位时钟控制器）配置时钟以及时钟树

RCC主要作用 设置系统时钟SYSCLK&#xff08;System Clock&#xff09;频率&#xff1b;设置AHB、APB2、APB1以及各个外设分频因子&#xff0c;从而设置HCLK、PCLK2、PCLK1以及各个外设的时钟频率&#xff1b;控制AHB、APB2、APB1这三条总线时钟以及每个外设的时钟开启&#xf…
阅读更多...
使用mtools搭建MongoDB复制集和分片集群

使用mtools搭建MongoDB复制集和分片集群

mtools介绍 mtools是一套基于Python实现的MongoDB工具集&#xff0c;其包括MongoDB日志分析、报表生成及简易的数据库安装等功能。它由MongoDB原生的工程师单独发起并做开源维护&#xff0c;目前已经有大量的使用者。 mtools所包含的一些常用组件如下&#xff1a; mlaunch支…
阅读更多...
随记：win11 win+g 捕获 不能录视频 不用下载注册表修复工具

随记：win11 win+g 捕获 不能录视频 不用下载注册表修复工具

问题&#xff1a; 我解决的方法&#xff1a; win R 打开 再去 计算机\HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\GameDVR 这是我的问题&#xff0c;要是没有这个&#xff0c;可能是其他原因了 还有就是我还看到一个 上面那个不能解决的可以试试这个
阅读更多...
算法刷题Day11: BM33 二叉树的镜像

算法刷题Day11: BM33 二叉树的镜像

点击题目链接 思路 转换为子问题&#xff1a;左右子树相反转。遍历手法&#xff1a;后序遍历 代码 class Solution:def Transverse(self,root: TreeNode):if root None:return rootnewleft self.Transverse(root.left)newright self.Transverse(root.right)# 对root节点…
阅读更多...
【赵渝强老师】PostgreSQL的服务器日志文件

【赵渝强老师】PostgreSQL的服务器日志文件

PostgreSQL数据库的物理存储结构主要是指硬盘上存储的文件&#xff0c;包括&#xff1a;数据文件、日志文件、参数文件、控制文件、WAL预写日志文件等等。下面重点讨论一下PostgreSQL的服务器日志文件。 视频讲解如下 【赵渝强老师】PostgreSQL的服务器日志文件 通过使用pg_ct…
阅读更多...
【人工智能】深度解剖利用人工智能MSA模型

【人工智能】深度解剖利用人工智能MSA模型

目录 情感分析的应用一、概述二、研究背景三、主要贡献四、模型结构和代码五、数据集介绍六、性能展示七、复现过程 情感分析的应用 近年来社交媒体的空前发展以及配备高质量摄像头的智能手机的出现&#xff0c;我们见证了多模态数据的爆炸性增长&#xff0c;如电影、短视频等…
阅读更多...
行业标杆！鸿翼入选WAIC 2024《2024大模型典型示范应用案例集》

行业标杆！鸿翼入选WAIC 2024《2024大模型典型示范应用案例集》

​7月5日&#xff0c;在2024世界人工智能大会“迈向 AGI&#xff1a;大模型焕新与产业赋能”论坛上&#xff0c;《2024大模型典型示范应用案例集》&#xff08;以下简称《案例集》&#xff09;重磅发布&#xff01;鸿翼AI项目成功入选&#xff0c;彰显了鸿翼在大模型应用领域的…
阅读更多...
nodejs循环导出多个word表格文档

nodejs循环导出多个word表格文档

文章目录 nodejs循环导出多个word表格文档一、文档模板编辑二、安装依赖三、创建导出工具类exportWord.js四、调用五、效果图nodejs循环导出多个word表格文档 结果案例： 一、文档模板编辑 二、安装依赖 // 实现word下载的主要依赖 npm install docxtemplater pizzip --save/…
阅读更多...
ABAP DIALOG屏幕编程1

ABAP DIALOG屏幕编程1

一、DIALOG屏幕编程 DIALOG屏幕编程是SAP ABAP中用于创建用户交互界面的一种技术&#xff0c;主要用于开发事务性应用程序。它允许用户通过屏幕输入或操作数据&#xff0c;程序根据用户的操作执行逻辑处理。 1、DIALOG编程的主要组件 a、屏幕 (Screen) DIALOG程序的核心部分…
阅读更多...
Shell免交互

Shell免交互

Shell免交互 一. 变量配置1.1 在E0F外面的变量可以直接传入使用1.2 EOF的输入内容可以直接赋值给变量 二. expect语句2.1 转义符2.2 expect的语法2.3 格式2.4 脚本外传参2.5 嵌套 三. 访问其它主机 交互&#xff1a;当我们使用程序时&#xff0c;需要进入程序发出对应的指令&am…
阅读更多...
清风数学建模学习笔记——Topsis法

清风数学建模学习笔记——Topsis法

数模评价类&#xff08;2&#xff09;——Topsis法 概述 Topsis:Technique for Order Preference by Similarity to Ideal Solution 也称优劣解距离法&#xff0c;该方法的基本思想是&#xff0c;通过计算每个备选方案与理想解和负理想解之间的距离&#xff0c;从而评估每个…
阅读更多...
最新文章

Copyright @ 2022~2023