当前位置: 首页 > news >正文

双指针算法,基础算法实践,基本的算法的思想,双指针算法的实现


一,定义

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

  1. 快慢指针:在链表中,快慢指针常用于判断是否存在环,找到环的起点,以及求解中位数等问题。快指针每次移动两步,慢指针每次移动一步,它们会以不同的速度遍历链表,从而实现一些特定的目标。

  2. 左右指针:在数组或字符串中,左右指针常用于搜索满足某种条件的元素。左指针从开头开始,右指针从末尾开始,它们根据问题的要求逐渐向中间靠拢,通常在搜索有序数组或字符串中的元素时非常高效。

  3. 对撞指针:在有序数组中查找两个数的和等于特定值,对撞指针是一种常见的解决方法。左指针从开头开始,右指针从末尾开始,它们根据和的大小逐渐接近目标值。

双指针算法的优点在于它通常具有较低的空间复杂度,因为它只需要存储两个指针。同时,双指针算法的时间复杂度通常较低,因为它们在遍历过程中减少了不必要的比较和计算。


简单的来看一下双指针的思想的最常见的两种思想,快慢指针和对撞指针两种方法,实话说双指针算法更像是一种模拟的思想,不过是对工具的模拟来完成的,使用的时候重点 : 指针和指针所用维护的序列

图示
在这里插入图片描述

二,常见的双指针题型

以下是几个常见的经典双指针题型:

  1. 两数之和(Two Sum)

    • 题目描述:给定一个整数数组和一个目标值,找出数组中两个数的和等于目标值的索引。
    • 解题思路:使用一个哈希表来记录已经遍历过的元素,同时使用双指针来查找满足条件的两个数。
  2. 反转字符串(Reverse String)

    • 题目描述:给定一个字符数组,将其反转。
    • 解题思路:使用双指针,一个指向数组开头,另一个指向数组末尾,然后交换它们指向的元素,直到两指针相遇。
  3. 盛最多水的容器(Container With Most Water)

    • 题目描述:给定一组垂直线段,每个线段的长度表示该位置的高度,选择两个线段,使得它们和 x 轴构成的容器
    • 解题思路:使用双指针,一个指向数组开头,另一个指向数组末尾,然后根据指针指向的线段高度和宽度计算容器的面积,并不断移动指针以找到最大面积。
  4. 三数之和(3Sum)

    • 题目描述:给定一个整数数组,找出所有不重复的三元组,使得三元组的和等于零。
    • 解题思路:使用双指针,首先将数组排序,然后使用一个外循环遍历数组中的每个元素,内部使用双指针来寻找满足条件的三元组。
  5. 合并两个有序数组(Merge Two Sorted Arrays)

    • 题目描述:给定两个有序整数数组,将它们合并成一个有序数组。
    • 解题思路:使用双指针,一个指向第一个数组的末尾,另一个指向第二个数组的末尾,然后从后向前合并数组中的元素。
  6. 最长回文子串(Longest Palindromic Substring)

    • 题目描述:给定一个字符串,找出最长的回文子串。
    • 解题思路:使用双指针,从每个字符向两侧扩展,同时检查扩展后的子串是否是回文,记录最长的回文子串。

三 ,解题常见的模型
一般的双指针算法的思路是基于相关的循环上面的,所以我们一般的双指针算法都是能够比较简单的,并且双指针算法是一种基本的算法思路没有具体的模板可以直接实现,所以不再给出代码实现。

相关文章:

双指针算法,基础算法实践,基本的算法的思想,双指针算法的实现

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

idea http request无法识别环境变量

问题描述 创建了环境变量文件 http-client.env.json,然后在*.http 文件中引用环境变量,运行 HTTP 请求无法读取环境变量文件中定义的变量。 事故现场 IDEA 版本:2020.2 2021.2 解决步骤 2020.2 版本环境变量无法读取 2021.2 版本从 2020.…...

性能测试常见的测试指标

一、什么是性能测试 先看下百度百科对它的定义 性能测试是通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。我们可以认为性能测试是:通过在测试环境下对系统或构件的性能进行探测,用以验证在生产环境下系统性能…...

并发 04(Callable,CountDownLatch)详细讲解

并发 Callable 1 可以返回值 2可以抛出异常 泛型指的是返回值的类型 public class Send {public static void main(String[] args) {//怎么启动Callable//new Thread().start();Aaa threadnew Aaa();FutureTask futureTasknew FutureTask(thread);new Thread(futureTask,&qu…...

Json路径表达式

原json路径 {"timeStamp": "20220801110008","transIDO": "6ba9088c981b407fb38feasdf09","version": "1.0.0","signMethod": "md5","content": "{\"companyName\&quo…...

【uniapp 上传图片示例】

以下是 uniapp 上传图片的详细步骤示例: 定义一个方法,用于选择图片并上传: methods: {chooseImage() {uni.chooseImage({count: 1, // 最多选择的图片数量sizeType: [original, compressed], // 可以指定原图或压缩图sourceType: [album, …...

apache2配置文件 Require all granted是什么意思

修改apache2的配置文件 /etc/apache2/apache2.conf&#xff0c;需要增加网站代码的路径&#xff0c;下列配置是什么意思呢 <Directory "/var/www/html">Options FollowSymLinksAllowOverride AllRequire all granted </Directory> 1. Options Options …...

c/c++ 的一些知识

c 面向对象是一种思想&#xff0c;通常情况下都是以组合为主&#xff0c;也就是在子类里定义一个基类struct base_t {void (*method)(base_t *base_p); };struct children_t {int a;int b;base_t base;void (*method)(children_t *children_p); };children_t children_creat(i…...

Rancher上的应用服务报错:413 Request Entity Too Large

UI->rancher的ingress->UI前端(在nginx里面)->zuul->server 也就是说没经过一次http servlet 都要设置一下大小 1.rancher的ingress 当出现Request Entity Too Large时&#xff0c;是由于传输流超过1M。 1、需要在rancher的ingress中设置参数解决。 配置注释&a…...

【LeetCode题目详解】第八章 贪心算法 part01 理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和 day31补

贪心算法理论基础 关于贪心算法&#xff0c;你该了解这些&#xff01; 题目分类大纲如下&#xff1a; # 什么是贪心 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 这么说有点抽象&#xff0c;来举一个例子&#xff1a; 例如&#xff0c;有一堆钞票&…...

ssm+vue中国咖啡文化宣传网站源码和论文

ssmvue中国咖啡文化宣传网站源码和论文078 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 课题背景 随着时代的发展和人们生活理念的进一步改变&#xff0c;咖啡业已经成为了全球经济中发展最迅猛的产业之一。…...

基于MATLAB开发AUTOSAR软件应用层Code mapping专题-part 4 Data store标签页介绍

这篇文章我们继续讲解code-mapping的Data stores页,这个页的内容对应的SIMULINK中的模块是Data store memory。 我们首先在模型中创建一个Data store memory模块,如图: Data store memory模块的作用相当于一个全局变量,我们可以在模型的功能逻辑里将一个信号存进去,在另…...

区间型动态规划典型题目:lintcode 476 · 石子归并【中等,免费】lintcode 593 · 石头游戏 II【中等 vip】

题目lintcode476 链接&#xff0c;描述 https://www.lintcode.com/problem/476/description 有一个石子归并的游戏。最开始的时候&#xff0c;有n堆石子排成一列&#xff0c;目标是要将所有的石子合并成一堆。合并规则如下&#xff1a;每一次可以合并相邻位置的两堆石子 每次…...

4. 池化层相关概念

4.1 池化层原理 ① 最大池化层有时也被称为下采样。 ② dilation为空洞卷积&#xff0c;如下图所示。 ③ Ceil_model为当超出区域时&#xff0c;只取最左上角的值。 ④ 池化使得数据由5 * 5 变为3 * 3,甚至1 * 1的&#xff0c;这样导致计算的参数会大大减小。例如1080P的电…...

ChatGPT Prompting开发实战(一)

一、关于ChatGPT Prompting概述 当我们使用ChatGPT或者调用OpenAI的API时&#xff0c;就是在使用prompt进行交互&#xff0c;用户在对话过程中输入的一切信息都是prompt&#xff08;提示词&#xff09;&#xff0c;当然工业级的prompt与人们通常理解的prompt可能不太一样。下面…...

VB车辆管理系统SQL设计与实现

摘 要 随着信息时代的到来,信息高速公路的兴起,全球信息化进入了一个新的发展时期。人们越来越认识到计算机强大的信息模块处理功能,使之成为信息产业的基础和支柱。 我国经济的快速发展,汽车已经成为人们不可缺少的交通工具。对于拥有大量车辆的机关企事业来说,车辆的…...

java 泛型

概述 泛型在java中有很重要的地位&#xff0c;在面向对象编程及各种设计模式中有非常广泛的应用。 泛型&#xff0c;就是类型参数。 一提到参数&#xff0c;最熟悉的就是定义方法时有形参&#xff0c;然后调用此方法时传递实参。 那么类型参数理解呢&#xff1f; 顾名思义&…...

git 查看/配置 local/global 用户名称和用户邮箱

1、--local: 本地设置&#xff08;仅对当前仓库有效&#xff09; git config --local user.name “你的名称” git config --local user.email “你的邮箱” 2、--global 全局设置&#xff08;对当前用户的所有仓库有效&#xff09; git config --global user.name “你的名称…...

无涯教程-分类算法 - 简介

分类可以定义为根据观测值或给定数据点预测类别的过程。分类的输出可以采用"黑色"或"白色"或"垃圾邮件"或"非垃圾邮件"的形式。 在数学上&#xff0c;分类是从输入变量(X)到输出变量(Y)近似映射函数(f)的任务&#xff0c;它属于有监督…...

python venv 打包,更换路径后,仍然读取到旧路径 ,最好别换路径,采用docker封装起来

机械盘路径 /home/yeqiang/code/xxx 移动到 /opt/xxx 编辑/opt/xxx/venv/bin/activate VIRTUAL_ENV"/home/yeqiang/code/xxx/venv" 改为 VIRTUAL_ENV"/opt/xxx/venv" 下面还有这么多&#xff0c;参考&#xff1a; (venv) yeqiangyeqiang-MS-7B23:/…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...