算法专题一：双指针

算法专题一：双指针

  • 一：移动零
    • 1.GIF题目解析：
  • 二：复写零
    • 2.GIF题目解析：
  • 三：快乐数
    • 3.GIF题目解析：
  • 四：装水最多容器：
    • 4.GIF题目解析：
  • 五：有效三角形的个数：
    • 5.GIF题目解析：
  • 六：查找总价格为目标价格的两个商品：
    • 6.GIF题目解析：
  • 七：三数之和：
    • 7.GIF题目解析：
  • 八：四数之和：
    • 8.GIF题目解析：

一：移动零

在这里插入图片描述
移动零

1.GIF题目解析：

在这里插入图片描述

在这里插入图片描述

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int destion = 0;
        for(int cur = 0;cur<nums.size();cur++)
        {
            if(nums[cur] != 0 )
            {
                swap(nums[cur],nums[destion++]);
            }
        }
    }
};

二：复写零

在这里插入图片描述
复写零

2.GIF题目解析：

情况一：
在这里插入图片描述

情况二

在这里插入图片描述

在这里插入图片描述

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {

        int cur = 0;
        int des = -1;
        int n = arr.size();

        //1.找到cur和des位置：

        while (cur<n)
        {
            if (arr[cur] != 0)
            {
                des++;
            }
            else if (arr[cur] == 0)
            {
                des += 2;
            }
            if (des >= n - 1)
            {
                break;
            }
            cur++;
        }


        //2.判断特殊情况：
        if (des == n)
        {
            arr[n-1] = 0;
            cur--;
            des-=2;
        }

        //3.进行复写操作：

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

三：快乐数

在这里插入图片描述
快乐数

3.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    int sum_of_squares(int n)
    {
        int sum = 0;
        while(n!=0)
        {
            int tmp = n%10;
            sum += (tmp*tmp);
            n/=10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int falst = sum_of_squares(n);

        while(slow!=falst)
        {
            slow = sum_of_squares(slow);
            falst = sum_of_squares(sum_of_squares(falst));
        }

        return slow==1;
    }
};

四：装水最多容器：

在这里插入图片描述

4.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    int maxArea(vector<int>& height) {
        int front = 0;
        int last = height.size()-1;

        int capacity = 0;
        while(front<=last)
        {
            int cap = (min(height[last] , height[front]))*(last-front);

            if(cap>=capacity)
            {
                capacity = cap;
            }

            if(height[front]>=height[last])
            {
                last--;
            }
            else if(height[front]<height[last])
            {
                front++;
            }
        }

        return capacity;
    }
};

五：有效三角形的个数：

在这里插入图片描述
有效三角形的个数

思路一：暴力解法：
1.满足三角形的条件是任意两边之和大于第三边：
2.题目不允许同一个位置的元素重复出现：
3.因为只需要拿出三个数所以循环遍历三次：
4.三角形条件的判断需要判断三次：
5.时间复杂度就是O(3*N^3)

思路二：排序+双指针

在这里插入图片描述

5.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    int triangleNumber(vector<int>& nums) {

        //1.排序
        sort(nums.begin(),nums.end());

        //2.固定最大的数：
        int count =0;

        for(int i=nums.size()-1;i>=2;i--)
        {
            int left = 0;
            int right = i-1;

            while(left<right)
            {
                int sum = nums[left]+nums[right];

                if(sum > nums[i])
                {
                    count+=(right-left);
                    right--;
                }
                else if(sum <= nums[i])
                {
                    left++;
                }
            }
        }
        return count;
    }
};

六：查找总价格为目标价格的两个商品：

在这里插入图片描述

查找总价格为目标价格的两个商品

思路一:暴力解法：
1.双for循环可以重复遇到满足情况的值就返回：
2.双for的i和j price[i]+price[j] == target

思路二：排序+双指针
在这里插入图片描述

6.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        //1.排序：
        sort(price.begin(),price.end());
        //2.确定指针位置和三种情况：
        int left=0;
        int right = price.size()-1;

        while(left<right)
        {
            int sum = price[left]+price[right];

            if(sum > target)
            {
                right--;
            }
            else if(sum<target)
            {
                left++;
            }
            else 
            {
                return {price[left],price[right]};
            }
        }
        return {-1,-1};
    }
};

七：三数之和：

在这里插入图片描述
三数之和

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

class Solution {
    bool pwd(vector<int>& v1,vector<vector<int>>& vv)
    {
        int flag = vv.size();

        for(int i=0;i<vv.size();i++)
        {
            vector<int> v2=vv[i];

            for(int i=0;i<3;i++)
            {
                if(v1[i]!=v2[i])
                {
                    flag--;
                    break;
                }
            }
        }

        if(flag == 0)
        {
            return false;
        }
        else 
        {
            return true;
        }
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vv;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                for(int k=j+1;k<nums.size();k++)
                {
                    int sum = nums[i]+nums[j]+nums[k];
                    vector<int> tmp ={nums[i] , nums[j] ,nums[k]};
                    //1.排序：
                    sort(tmp.begin(),tmp.end());

                    if(sum==0)
                    {
                        //2.判断是否重复：
                        if(vv.size()==0)
                        {
                            vv.push_back(tmp);
                            continue;
                        }
                        else if(!pwd(tmp,vv))
                        {
                            vv.push_back(tmp);
                        }
                    }
                    
                }
            }
        }
        return vv;
    }
};

在这里插入图片描述

7.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> vv;
        //1.排序：
        sort(nums.begin(), nums.end());
        //2.遍历固定一个
        if ((nums.size() == 3) && (nums[0] + nums[1] + nums[2] == 0))
        {
            vv.push_back(nums);
            return vv;
        }

        for (int i = 0; i <nums.size();)
        {
            int des = -(nums[i]);

            if(nums[i] > 0)
                break;

            int left = i+1;
            int right = nums.size()-1;

                while (left < right)
                {
                    int sum = nums[left] + nums[right];

                    if (sum > des && right >= 0)
                    {
                        right--;
                    }
                    else if (sum < des && left < nums.size())
                    {
                        left++;
                    }
                    else
                    {
                        vector<int> tmp = { nums[left],nums[right],nums[i] };
                        vv.push_back(tmp);

                        left++;
                        right--;

                        while(left<right && nums[left]==nums[left-1])
                            left++;
                        while(left<right && nums[right]==nums[right+1])
                            right--;
                    }
               }

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

            return vv;
        }
};

八：四数之和：

在这里插入图片描述
四数之和

在这里插入图片描述

8.GIF题目解析：

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        //1.排序：
        sort(nums.begin(),nums.end());

        //2.记录数据个数：
        int n=nums.size();
        vector<vector<int>> vv;
        //3.开始遍历：

        //情况一：
        
        //特殊优化！
        if(nums[0]>target && nums[0]>0)
            return vv;

        //情况二：
        for(int i=0;i<n;)
        {
            for(int j=i+1;j<n;)
            {
                int left=j+1;
                int right = n-1;

                long long   sum_1 = ((long long)target - 
                (long long)(nums[i] + nums[j]));

                while(left<right)
                {
                    long long  sum_2 = nums[left]+nums[right];

                    if(sum_2 > sum_1)
                    {
                        right--;
                    }
                    else if(sum_2 < sum_1)
                    {
                        left++;
                    }
                    else
                    {
                        vector<int> tmp={nums[i],nums[j],nums[left],nums[right]};
                        vv.push_back(tmp);
                        right--;
                        left++;

                        while(left<right && nums[right]==nums[right+1])
                            right--;
                        while(left<right && nums[left]==nums[left-1])
                            left++;
                    }

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

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

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

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

相关文章

0007Java程序设计-ssm基于微信小程序的在线考试系统

0007Java程序设计-ssm基于微信小程序的在线考试系统

文章目录 **摘要**目 录系统实现开发环境 编程技术交流、源码分享、模板分享、网课分享 企鹅&#x1f427;裙&#xff1a;776871563 摘要 网络技术的快速发展给各行各业带来了很大的突破&#xff0c;也给各行各业提供了一种新的管理技术&#xff0c;基于微信小程序的在线考试…
阅读更多...
Spring Boot中使用Swagger

Spring Boot中使用Swagger

1. 启用Swagger 1.1 启用注解扫描和文档接口 直接在POM文件引入依赖 <dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.9.2</version> </dependency>1.2 启动swagger-u…
阅读更多...
系统设计-微服务架构

系统设计-微服务架构

典型的微服务架构图 下图展示了一个典型的微服务架构。 负载均衡器&#xff1a;它将传入流量分配到多个后端服务。CDN&#xff08;内容交付网络&#xff09;&#xff1a;CDN 是一组地理上分布的服务器&#xff0c;用于保存静态内容以实现更快的交付。客户端首先在 CDN 中查找内…
阅读更多...
ElementUI 时间选择器如何限定选择时间

ElementUI 时间选择器如何限定选择时间

DatePicker 日期选择器 | Element Plus 我们如何限定我们的选择时间呢&#xff0c;比如限定选择时间为今天之前&#xff0c;或者今天之后的时间&#xff1f; 我们可以使用官方提供的disabled-date来实现 我们通过这个属性 做一个回调函数&#xff0c;在里面比较我们想要限定的时…
阅读更多...
《数据库系统概论》学习笔记——王珊 萨师煊

《数据库系统概论》学习笔记——王珊 萨师煊

第一章 绪论 一、数据库系统概述 1.数据库的4个基本概念 &#xff08;1&#xff09;数据 描述事物的符号记录称为数据 &#xff08;2&#xff09;数据库 存放数据的仓库 &#xff08;3&#xff09;数据库管理系统 主要功能&#xff1a; &#xff08;1&#xff09;数据定…
阅读更多...
【QED】井字棋

【QED】井字棋

目录 题目背景题目描述输入格式输出格式测试样例 思路核心代码 题目背景 井字棋&#xff0c;英文名叫Tic-Tac-Toe&#xff0c;是一种在 3 3 3 \times 3 33格子上进行的连珠游戏&#xff0c;和五子棋类似。游戏时&#xff0c;由分别代表O和X的两名玩家轮流在棋盘格子里留下棋子…
阅读更多...
【恋上数据结构】前缀树 Tire 学习笔记

【恋上数据结构】前缀树 Tire 学习笔记

Tire 需求分析 如何判断一堆不重复的字符串是否以某个前缀开头&#xff1f; 用 Set\Map 存储字符串&#xff08;不重复&#xff09;遍历所有字符串进行判断缺点&#xff1a;时间复杂度 O(n) 有没有更优的数据结构实现前缀搜索&#xff1f; Tire&#xff08;和 Tree 同音&a…
阅读更多...
快速整合EasyExcel实现Excel的上传下载

快速整合EasyExcel实现Excel的上传下载

1.EasyExcel 2.Excel的上传&#xff08;读Excel&#xff09; 3.Excel的下载&#xff08;写Excel&#xff09; 4.结语 1.EasyExcel 首先&#xff0c;这里给出EasyExcel的官方文档&#xff1a;https://easyexcel.opensource.alibaba.com/ alibaba.com不用我多说了吧&#xff0c;大…
阅读更多...
2023-12-05 Qt学习总结2

2023-12-05 Qt学习总结2

点击 <C 语言编程核心突破> 快速C语言入门 Qt学习总结 前言五 Hello Qt!六 Qt控件和事件七 Qt信号和槽八 Qt自定义信号和槽总结 前言 要解决问题: 学习qt最核心知识, 多一个都不学. 五 Hello Qt! 现在我们已经有了一个空窗口工程, 传统上, 我们要实现一个"Hello …
阅读更多...
HXDSP2441-Demo板

HXDSP2441-Demo板

板卡图示 下图为HXDSP2441DEMO板&#xff0c;HXDSP2441DEMO板是围绕HXDSP2441构建的芯片演示验证平台。 板卡简介 除了为HXDSP2441芯片提供供电、时钟、储存、网络及调试电路&#xff0c;来实现芯片最基本的功能&#xff0c;也添加了相关模块以搭建HXDSP2441的典型应用场景…
阅读更多...
活久见—当设置不同坐标系统时，ArcMap中的图形相关位置关系会变化

活久见—当设置不同坐标系统时，ArcMap中的图形相关位置关系会变化

这两天一件十分神奇的事情发生了&#xff1a;当设置不同坐标系统时&#xff0c;ArcMap中的图形相对位置关系会变化。 事情起因是这样的&#xff1a;博主和同行用ArcMap同时验证2个相邻多边形的相对位置关系&#xff0c;见下图图1和图2的多边形&#xff0c;在博主的ArcMap中&am…
阅读更多...
快速登录界面关于如何登录以及多账号列表解析以及config配置文件如何读取以及JsLogin模块与SdoLogin模块如何通信(4)

快速登录界面关于如何登录以及多账号列表解析以及config配置文件如何读取以及JsLogin模块与SdoLogin模块如何通信(4)

1、### Jslogin模块与前端以及JsLogin模块与Sdologin的交互 配置文件的读取: <CompanyIdForQq value"301"/> <CompanyIdForWx value"300"/><CompanyIdForWb value"302"/><qq value"https://graph.qq.com/oauth2.0/au…
阅读更多...
爱智EdgerOS之深入解析如何应用爱智的视频流模块完成拉流

爱智EdgerOS之深入解析如何应用爱智的视频流模块完成拉流

一、ONVIF 规范和常见视频流传输协议 ① ONVIF 规范 随着视频监控产业链的成熟&#xff0c;市面上陆陆续续出现了各式各样的网络摄像设备&#xff0c;这些设备都需要通讯协议才能进行数据传输。早期厂商都采用私有协议&#xff0c;但是现在厂商分工明确&#xff0c;有的负责生…
阅读更多...
计算机毕业设计springboot+ssm停车场车位预约系统java

计算机毕业设计springboot+ssm停车场车位预约系统java

管理员不可以注册账号 停车位包括车位所在楼层、车位编号、车位类型(全时间开放/高峰期开放)、预定状态等 用户预约时要求支付预约时间段的停车费用 违规行为&#xff1a;1.停车超过预约时间段 2.预约未使用 于系统的基本要求 &#xff08;1&#xff09;功能要求&am…
阅读更多...
【go-zero】go-zero使用ent框架 如何使用源生sql完成查询

【go-zero】go-zero使用ent框架 如何使用源生sql完成查询

背景 本篇教程我们采用的是go-zero的快速脚手架工具 simple-admin 框架的开发 github地址：https://github.com/suyuan32/simple-admin-core 因为框架推荐使用Ent 这篇教程我们则对Ent的基本使用的几种形式进行一个总结 一、开启ent的源生sql 1、simple-admin生成rpc 【go-…
阅读更多...
BUUCTF [CISCN2019 华北赛区 Day2 Web1]Hack World 1(SQL注入之布尔盲注）

BUUCTF [CISCN2019 华北赛区 Day2 Web1]Hack World 1(SQL注入之布尔盲注）

题目环境判断注入类型 1 2 3 1’ 输入1’报错提示bool(false) 可知是字符型的布尔注入&#xff08;盲注&#xff09; 尝试万能密码 1’ or ‘1’1 已检测SQL注入 猜测某些关键字或者字符被过滤 FUZZ字典爆破 可以看到部分关键字被过滤&#xff0c;包括空格 All You Want Is In …
阅读更多...
[面试题～Docker] 云原生必问基础篇

[面试题～Docker] 云原生必问基础篇

文章目录 基础相关1. Docker 是什么&#xff1f;2. 镜像是什么3. 容器是什么4. 数据卷是什么5. Docker 和虚拟机的区别&#xff1f;6. Docker 常用命令有哪些&#xff1f; 原理相关1. docker 有几种网络模式host 模式container模式none模式bridge模式 2. docker 网络实现在Linu…
阅读更多...
AWTK 串口屏开发(1) - Hello World

AWTK 串口屏开发(1) - Hello World

1. 功能 这个例子很简单&#xff0c;制作一个调节温度的界面。在这里例子中&#xff0c;模型&#xff08;也就是数据&#xff09;里只有一个温度变量&#xff1a; 变量名数据类型功能说明温度整数温度。范围 (0-100) 摄氏度 2. 创建项目 从模板创建项目&#xff0c;将 hmi/…
阅读更多...
物奇平台CLI MIC切换对应ADC关系

物奇平台CLI MIC切换对应ADC关系

是否需要申请加入数字音频系统研究开发交流答疑群(课题组)&#xff1f;可加我微信hezkz17, 本群提供音频技术答疑服务&#xff0c;群赠送语音信号处理降噪算法&#xff0c;蓝牙耳机音频&#xff0c;DSP音频项目核心开发资料, 物奇平台CLI MIC切换对应ADC关系 1 发送CLI指令…
阅读更多...
tqdm详细教程，实现tqdm进度条完美设计；解决进度条多行一直刷新的问题；如何使得滚动条不上下滚动(保持一行内滚动)

tqdm详细教程，实现tqdm进度条完美设计；解决进度条多行一直刷新的问题；如何使得滚动条不上下滚动(保持一行内滚动)

一、tqdm简介 tqdm是一个python进度条库&#xff0c;可以在 Python长循环中添加一个进度提示信息。 二、3种使用方法 1.tqdm(range)-自动更新 import time from tqdm import range# 自动更新 for i in tqdm(range(10)): # 共可以更新10次进度条time. Sleep(0.5) # 每次更新间…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站