【面试高频算法解析】算法练习3 双指针
前言
本专栏旨在通过分类学习算法,使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目,帮助您深度理解每种算法,避免出现刷了很多算法题,还是一知半解的状态
专栏导航
- 二分查找
- 回溯
- 双指针
- 滑动窗口
- 深度优先搜索
- 广度优先搜索
算法解析
双指针技术是一种常用的算法策略,它使用两个指针以不同的速度或方向遍历数据结构(通常是线性结构如数组或链表),从而达到解决问题的目的。双指针技术可以帮助我们简化复杂度,减少不必要的运算,尤其是在解决一些与序列相关的问题时非常有效。
双指针通常有以下几种分类:
-
快慢指针:
快慢指针通常用于解决链表中的问题,例如检测链表中的循环。快指针每次移动两步,慢指针每次移动一步。如果链表中有循环,则快指针最终会追上慢指针。 -
左右指针:
左右指针通常用于有序数组或字符串,开始时一个指向头部(左指针),另一个指向尾部(右指针),然后向中间移动。例如在二分查找、合并两个有序数组或是计算一组数的对数(如两数之和)时会用到。 -
滑动窗口(面试中很常见我将另开一篇详细介绍):
滑动窗口可以看作是一种特殊的双指针,通常用于解决数组/字符串的子区间问题。两个指针共同定义了一个窗口,可以增加或减少窗口的大小以满足特定条件,例如找出满足条件的最长/最短的子数组/子字符串。
双指针技术的优势在于它可以减少时间复杂度。例如,在排序数组中寻找两数之和等于特定值的问题中,暴力解法需要 O(n^2) 的时间复杂度,而使用双指针技术则可以降低到 O(n)。
下面是一个使用双指针(左右指针)解决“两数之和”问题的示例:
def two_sum_sorted(numbers, target):left, right = 0, len(numbers) - 1while left < right:current_sum = numbers[left] + numbers[right]if current_sum == target:return [left + 1, right + 1] # 返回的是位置,不是索引elif current_sum < target:left += 1 # 和太小,移动左指针else:right -= 1 # 和太大,移动右指针return [-1, -1] # 如果没有找到,返回[-1, -1]
在这个函数中,左指针从数组的开始位置向右移动,右指针从数组的结束位置向左移动,直到找到两数之和等于目标值或左右指针相遇。通过这种方式,我们只需要遍历数组一次,从而提高了算法的效率。
实战练习
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1:
输入:nums = [1,3,4,2,2]
输出:2
示例 2:
输入:nums = [3,1,3,4,2]
输出:3
提示:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
进阶:
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?
官方题解
三数之和
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
官方题解
删除排序链表中的重复元素II
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
示例 1:
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
示例 2:
输入:head = [1,1,1,2,3]
输出:[2,3]
提示:
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
官方题解
相关文章:
【面试高频算法解析】算法练习3 双指针
前言 本专栏旨在通过分类学习算法,使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目,帮助您深度理解每种算法,避免出现刷了很多算法题,还是一知半解的状态 专栏导航 二分查找回溯双指针滑动窗口深度优先搜索…...
React16源码: Why16, 研究源码的意义, 源码目录核心结构分析
为什么要选择React16 现在React18都早已实践很多,为何回过头来看16版本的代码理由如下 从实际出发,企业内老旧项目多为16版本,理解16的核心能够帮助我们快速解决问题16版本React是完全重写了核心代码, 是一次重大的更新 引入了 fiber 这个概…...
mybatis-flex笔记
MyBatis-Flex 的增删改功能 - MyBatis-Flex 官方网站https://mybatis-flex.com/zh/base/add-delete-update.html 代码https://gitee.com/hntianshu/mybatis-flex-test 一 新增数据 不忽略 null 值。 就是允许有null 忽略null 就是不允许有null BaseMapper 的接口提供了 inser…...
Debezium发布历史47
原文地址: https://debezium.io/blog/2019/02/13/debezium-0-9-1-final-released/ 欢迎关注留言,我是收集整理小能手,工具翻译,仅供参考,笔芯笔芯. Debezium 0.9.1.Final 发布 二月 13, 2019 作者: Gunna…...
Python爬虫抓包常见问题解决
对于Python爬虫和Fiddler抓包,可能遇到的问题及解决: 代理设置错误:如果你在使用Python爬虫时遇到抓不到包的问题,首先应该检查你的浏览器代理设置是否正确。以Chrome为例,代理设置为:右上角菜单按钮>设…...
c++跨平台ui
fltk https://gitee.com/mirrors_fltk/fltk.git codeblock中有fltk项目开发模板,可以快速构建项目 wxwidget https://gitee.com/sofu456/wxWidgets.git git submodule update --init --recursive 打开demo和sample set(wxBUILD_SAMPLES ALL) set(wxBUILD_DEMOS ON) build/…...
stable diffusion 基础教程-提示词之艺术风格用法
展现夕阳 golden hour, (rim lighting):1.2, warm tones, sun flare, soft shadows, vibrant colors, hazy glow, painterly effect, dreamy atmosphere阴影 chiaroscuro, (high contrast):1.2, dramatic shadows, bold highlights, moody atmosphere, captivating inte…...
【日积月累】Java中 正则表达式
目录 日积月累】Java中 正则表达式 1.前言2.基本语法3.Pattern和Matcher类4.校验的表达式大全5.参考文章所属专区 日积月累 1.前言 正则表达式是一种用于匹配文本模式的语法,它通常与编程语言一起使用。在Java中,正则表达式用于匹配字符串,可以使用Pattern和Matcher类来实…...
Java调用百度云语音识别【音频转写】
百度云文档 ttps://ai.baidu.com/ai-doc/SPEECH/Bk5difx01 示例代码: import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.JSONArray; import lombok.extern.slf4j.Slf4j; import okhttp3.*; import org.json.JSONObject; import org.springframework.stereotyp…...
pyparamvalidate 项目背景和需求分析
目录 一、前置说明1、总体目录2、本节目标 二、项目背景三、需求分析三、后置说明1、要点小结2、下节预告 一、前置说明 1、总体目录 《 pyparamvalidate 参数校验器,从编码到发布全过程》 2、本节目标 阐述 pyparamvalidate 项目背景和需求分析。 二、项目背景…...
Docker Linux快速安装及Nginx部署
前言 最近正在部署一套新的Linux服务器环境,基于Docker来部署所有的应用,顺便整理了一套经过验证的操作手册,以便大家遇到类似需求时,可以直接拿来用。 本文会涉及以下知识点:Docker的Linux安装和卸载、Docker用户组…...
Mac M1 Parallels CentOS7.9 Install Parallels Tools
一、挂载parallels-tools安装包 mkdir /media/cdrom/ mount /dev/cdrom /media/cdrom/ mount: /dev/sr0 写保护,将以只读方式挂载二、GCC升级 yum install -y centos-release-scl yum install -y devtoolset-8-gcc*# 切换当前会话中gcc版本为8 scl enable devtool…...
计算机网络物理层 习题答案及解析
2-1 下列选项中,不属于物理层接口规范定义范畴的是( D )。 A. 引脚功能 B. 接口形状 C. 信号电平 D. 传输媒体 【答案】D 【解析】 2-2 某网络在物理层规定,信号的电平范围为- 15V~15V , 电线长…...
【解决】Unity 设置跨设备分辨率表现
开发平台:Unity 2018版本以上 开发语言:CSharp 编程平台:Visual Studio 2022 问题描述 使用 UnityEngine.dll 中关于设置分辨率的方法时,无法满足应用以设定分辨率进行屏幕显示问题。因而造成画面不同程度的拉伸情况。而这种情…...
基于单片机的智能衣柜设计
一、摘要 随着科技的不断发展,人们对于生活品质的要求越来越高。智能衣柜作为智能家居的一个重要组成部分,能够为用户提供便捷、个性化的衣物管理服务。本文主要研究了基于单片机的智能衣柜设计,通过对硬件系统和软件系统的设计与实现&#…...
HttpSession的使用
1 HttpSession 概述 在 Java Servlet API 中引入 session 机制来跟踪客户的状态。session 指的是在一段时间内,单个客户与 Web 服务器的一连串相关的交互过程。在一个 session 中,客户可能会多次请求访问同一个网页,也有可能请求访问各种不同…...
人工智能在金融领域的应用存在的4大挑战
金融服务供应商应该有计划地应对AI面临的难题 金融行业投资人工智能热潮带来有关数据安全和透明度的新问题。由于数据管理实践随着新的 AI 解决方案的引入而不断发展,应对这些新问题以及金融服务领域 AI 面临的其他挑战尤为重要。各组织必须认识到可能面临以下挑战…...
EasyExcel写出包含多个sheet页的Excel
https://blog.csdn.net/qq_38751895/article/details/131852740...
分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】
分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】 目录 分类预测 | Matlab实现RP-CNN-LSTM-Attention递归图优化卷积长短期记忆神经网络注意力机制的数据分类预测【24年新算法】分类效果基本描述模型描述程…...
【教学类-09-04】20240102《游戏棋N*N》数字填写,制作棋子和骰子
作品展示 背景需求: 最近在清理学具材料库,找到一套1年多前的《N*N游戏棋》,把没有用完的棋盘拿出来,,想给大4班换花样,并把它们用掉。 程序代码在这里 【教学类-09-03】20221120《游戏棋10*10数字如何直接…...
【flink番外篇】9、Flink Table API 支持的操作示例(14)- 时态表的join(java版本)
Flink 系列文章 一、Flink 专栏 Flink 专栏系统介绍某一知识点,并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分,比如术语、架构、编程模型、编程指南、基本的…...
【leetcode100-30】【链表】两两交换链表节点
【题干】 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 【思路】 先说递归的,退出条件很明显,当剩…...
小秋SLAM入门实战ubuntu所有文章汇总
Ubuntu系统安装详细教程 Ubuntu系统安装ROS详细教程 Ubuntu系统下如何搭建深度学习和SLAM开发环境 Ubuntu系统搭建SLAM开发环境 ubuntu 终端如何停止快速打印的输出以及恢复命令 ubuntu 终端如何快速打开当前路径下的图形化窗口界面? killall -9用途用法 ps -xu | …...
深度学习课程实验二深层神经网络搭建及优化
一、 实验目的 1、学会训练和搭建深层神经网络; 2、掌握超参数调试正则化及优化。 二、 实验步骤 初始化 1、导入所需要的库 2、搭建神经网络模型 3、零初始化 4、随机初始化 5、He初始化 6、总结三种不同类型的初始化 正则化 1、导入所需要的库 2、使用非正则化…...
Elasticsearch:Serarch tutorial - 使用 Python 进行搜索 (二)
这个是继上一篇文章 “Elasticsearch:Serarch tutorial - 使用 Python 进行搜索 (一)” 的续篇。在今天的文章中,我们接着来完成如何进行分页及过滤。 分页 - pagination 应用程序处理大量结果通常是不切实际的。 因此࿰…...
力扣labuladong——一刷day84
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣743. 网络延迟时间 前言 Dijkstra 算法(一般音译成迪杰斯特拉算法)无非就是一个 BFS 算法的加强版,它们都是从二叉…...
Linux环境vscode clang-format格式化:vscode clang format command is not available
问题现象 vscode安装了clang-format插件,但是使用就报错 问题原因 设置中配置的clang-format插件工具路径不正确。 解决方案 确认本地安装了clang-format工具:终端输入clang-format(也可能是clang-format-13等版本,建议tab自…...
【KingbaseES】实现MySql函数WEEKS_BETWEEN
WEEKS_BETWEEN CREATE OR REPLACE FUNCTION weeks_between(start_date date, end_date date) RETURNS integer AS $$ BEGIN RETURN EXTRACT(WEEK FROM end_date) - EXTRACT(WEEK FROM start_date); END; $$ LANGUAGE plpgsql IMMUTABLE;结果展示...
@Scheduled定时任务现状与改进
项目场景: 定时任务现状:每个项目都会有一些配置信息,这些信息我们是都放在一个配置服务中,这个服务会定时从配置表中加载所有配置存入本地JVM内存,以供调用方获取(调用方集成了配置服务的SDK,…...
python+selenium爬虫笔记
本文只是做例子,具体网站路径麻烦你们换下,还有xpath路径也换下 一、安装所需要的组件(此处采用谷歌) 1、安装驱动 查看你的浏览器版本,去安装对应的版本 下载驱动 下载驱动路径 之前版本的 输入这个路径下载下来解压…...
营销型网站外包/山东网站seo
第一部分必读系列: 01.学习算法和刷题的思路指南 02.学习数据结构和算法读什么书 03.动态规划解题套路框架 04.动态规划答疑篇 05.动态规划答疑篇 06.回溯算法解题套路框架 07.二分查找解题套路框架 08.滑动窗口解题套路框架 09.双指针技巧总结 10.BFS算法套…...
上海企业网站设计制作/销售网站排名
hash赋能前言一、缺失的第一个正数二、hash赋能1、hashSet2、原地数组hash总结参考文献前言 hash赋能可以为后面的工作大大减少搜索的时间,可用hash数组、hashSet、hashMap、原地数组hash。 一、缺失的第一个正数 二、hash赋能 1、hashSet //hash赋能//Time:O(n…...
网站策划设计招聘/小程序开发框架
作者:朱金灿 来源:https://blog.csdn.net/clever101 将一个Windows程序从32位转为64位程序,出现用户回调期间遇到未经处理的异常的错误,如下图: 经过调试发现是调用GetWindowLong返回为空指针,经过搜索&am…...
找网站开发公司/色盲眼镜
1. 题目 2. 解答 2.1 方法 1 定义快慢两个指针,慢指针每次前进一步,快指针每次前进两步,若链表有环,则快慢指针一定会相遇。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* …...
淘宝式网站建设/软文推广文案范文
微信h5端 外部浏览器中支付: 后端写一个接口去访问微信的接口,微信会返回一段链接,直接回调给前端,前端处理代码如下 后端返的值 orderString:‘https://wx.tenpay.com/cgi-bin/mmpayweb-bin/checkmweb?prepay_idwx…...