技术标签: 算法面试精选汇编 算法 双指针 数据结构 排序算法
双指针(Two Pointers):指的是在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针进行访问,从而达到相应的目的。如果两个指针方向相反,则称为「对撞指针」。如果两个指针方向相同,则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表,则称为「分离双指针」。
在数组的区间问题上,暴力算法的时间复杂度往往是 $O(n^2)$。而双指针利用了区间「单调性」的性质,可以将时间复杂度降到 $O(n)$。
对撞指针:指的是两个指针
left
、right
分别指向序列第一个元素和最后一个元素,然后left
指针不断递增,right
不断递减,直到两个指针的值相撞(即left == right
),或者满足其他要求的特殊条件为止。
使用两个指针 left
,right
。left
指向序列第一个元素,即:left = 0
,right
指向序列最后一个元素,即:right = len(nums) - 1
。
在循环体中将左右指针相向移动,当满足一定条件时,将左指针右移,left += 1
。当满足另外一定条件时,将右指针左移,right -= 1
。
直到两指针相撞(即 left == right
),或者满足其他要求的特殊条件时,跳出循环体。
left, right = 0, len(nums) - 1
while left < right:
if 满足要求的特殊条件:
return 符合条件的值
elif 一定条件 1:
left += 1
elif 一定条件 2:
right -= 1
return 没找到 或 找到对应值
对撞指针一般用来解决有序数组或者字符串问题:
查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。
字符串反转问题:反转字符串、回文数、颠倒二进制等问题。
下面我们根据具体例子来讲解如何使用对撞指针来解决问题。
2.4.2 题目大意
描述:给定一个下标从 1
开始计数、升序排列的整数数组:numbers
和一个目标值 target
。
要求:从数组中找出满足相加之和等于 target
的两个数,并返回两个数在数组中下的标值。
说明:
$2 \le numbers.length \le 3 * 10^4$。
$-1000 \le numbers[i] \le 1000$。
$numbers$ 按非递减顺序排列。
$-1000 \le target \le 1000$。
仅存在一个有效答案。
示例:
输入:numbers = [2,7,11,15], target = 9 输出:[1,2] 解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 输入:numbers = [2,3,4], target = 6 输出:[1,3] 解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
2.4.3 解题思路
这道题如果暴力遍历数组,从中找到相加之和等于 target
的两个数,时间复杂度为 $O(n^2)$,可以尝试一下。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
size = len(numbers)
for i in range(size):
for j in range(i + 1, size):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return [-1, -1]
结果不出意外的超时了。所以我们要想办法减少时间复杂度。
思路 1:对撞指针
可以考虑使用对撞指针来减少时间复杂度。具体做法如下:
使用两个指针 left
,right
。left
指向数组第一个值最小的元素位置,right
指向数组值最大元素位置。
判断两个位置上的元素的和与目标值的关系。
如果元素和等于目标值,则返回两个元素位置。
如果元素和大于目标值,则让 right
左移,继续检测。
如果元素和小于目标值,则让 left
右移,继续检测。
直到 left
和 right
移动到相同位置停止检测。
如果最终仍没找到,则返回 [-1, -1]
。
思路 1:代码
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1
return [-1, -1]
思路 1:复杂度分析
时间复杂度:$O(n)$。
空间复杂度:$O(1)$。只用到了常数空间存放若干变量。
2.5.1 题目链接
2.5.2 题目大意
描述:给定一个字符串 s
。
要求:判断是否为回文串(只考虑字符串中的字母和数字字符,并且忽略字母的大小写)。
说明:
回文串:正着读和反着读都一样的字符串。
$1 \le s.length \le 2 * 10^5$。
s
仅由可打印的 ASCII 字符组成。
示例:
输入: "A man, a plan, a canal: Panama" 输出:true 解释:"amanaplanacanalpanama" 是回文串。 输入:"race a car" 输出:false 解释:"raceacar" 不是回文串。
2.5.3 解题思路
思路 1:对撞指针
使用两个指针 left
,right
。left
指向字符串开始位置,right
指向字符串结束位置。
判断两个指针对应字符是否是字母或数字。 通过 left
右移、right
左移的方式过滤掉字母和数字以外的字符。
然后判断 s[start]
是否和 s[end]
相等(注意大小写)。
如果相等,则将 left
右移、right
左移,继续进行下一次过滤和判断。
如果不相等,则说明不是回文串,直接返回 False
。
如果遇到 left == right
,跳出循环,则说明该字符串是回文串,返回 True
。
思路 1:代码
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
思路 1:复杂度分析
时间复杂度:$O(len(s))$。
空间复杂度:$O(len(s))$。
2.6.1 题目链接
2.6.2 题目大意
描述:给定 $n$ 个非负整数 $a_1,a_2, ...,a_n$,每个数代表坐标中的一个点 $(i, a_i)$。在坐标内画 $n$ 条垂直线,垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。
要求:找出其中的两条线,使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。
说明:
$n == height.length$。
$2 \le n \le 10^5$。
$0 \le height[i] \le 10^4$。
示例:
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
2.6.3 解题思路
思路 1:对撞指针
从示例中可以看出,如果确定好左右两端的直线,容纳的水量是由 左右两端直线中较低直线的高度 * 两端直线之间的距离
所决定的。所以我们应该使得 较低直线的高度尽可能的高,这样才能使盛水面积尽可能的大。
可以使用对撞指针求解。移动较低直线所在的指针位置,从而得到不同的高度和面积,最终获取其中最大的面积。具体做法如下:
使用两个指针 left
,right
。left
指向数组开始位置,right
指向数组结束位置。
计算 left
和 right
所构成的面积值,同时维护更新最大面积值。
判断 left
和 right
的高度值大小。
如果 left
指向的直线高度比较低,则将 left
指针右移。
如果 right
指向的直线高度比较低,则将 right
指针左移。
如果遇到 left == right
,跳出循环,最后返回最大的面积。
思路 1:代码
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
ans = 0
while left < right:
area = min(height[left], height[right]) * (right-left)
ans = max(ans, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return ans
思路 1:复杂度分析
时间复杂度:$O(n)$。
空间复杂度:$O(1)$。
快慢指针:指的是两个指针从同一侧开始遍历序列,且移动的步长一个快一个慢。移动快的指针被称为 「快指针(fast)」,移动慢的指针被称为「慢指针(slow)」。两个指针以不同速度、不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或者满足其他特殊条件时为止。
使用两个指针 slow
、fast
。slow
一般指向序列第一个元素,即:slow = 0
,fast
一般指向序列第二个元素,即:fast = 1
。
在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即 slow += 1
。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即 fast += 1
。
到快指针移动到数组尾端(即 fast == len(nums) - 1
),或者两指针相交,或者满足其他特殊条件时跳出循环体。
slow = 0 fast = 1 while 没有遍历完: if 满足要求的特殊条件: slow += 1 fast += 1 return 合适的值
快慢指针一般用于处理数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。
下面我们根据具体例子来讲解如何使用快慢指针来解决问题。
3.4.1 题目链接
3.4.2 题目大意
描述:给定一个有序数组 nums
。
要求:删除数组 nums
中的重复元素,使每个元素只出现一次。并输出去除重复元素之后数组的长度。
说明:
不能使用额外的数组空间,在原地修改数组,并在使用 $O(1)$ 额外空间的条件下完成。
示例:
输入:nums = [1,1,2] 输出:2, nums = [1,2,_] 解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 输入:nums = [0,0,1,1,1,2,2,3,3,4] 输出:5, nums = [0,1,2,3,4] 解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
3.4.3 解题思路
思路 1:快慢指针
因为数组是有序的,那么重复的元素一定会相邻。
删除重复元素,实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下:
定义两个快慢指针 slow
,fast
。其中 slow
指向去除重复元素后的数组的末尾位置。fast
指向当前元素。
令 slow
在后, fast
在前。令 slow = 0
,fast = 1
。
比较 slow
位置上元素值和 fast
位置上元素值是否相等。
如果不相等,则将 slow
右移一位,将 fast
指向位置的元素复制到 slow
位置上。
将 fast
右移 1
位。
重复上述 3 ~ 4 步,直到 fast
等于数组长度。
返回 slow + 1
即为新数组长度。
思路 1:代码
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
slow, fast = 0, 1
while (fast < len(nums)):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1
思路 1:复杂度分析
时间复杂度:$O(n)$。
空间复杂度:$O(1)$。
分离双指针:两个指针分别属于不同的数组 / 链表,两个指针分别在两个数组 / 链表中移动。
使用两个指针 left_1
、left_2
。left_1
指向第一个数组 / 链表的第一个元素,即:left_1 = 0
,left_2
指向第二个数组 / 链表的第一个元素,即:left_2 = 0
。
当满足一定条件时,两个指针同时右移,即 left_1 += 1
、left_2 += 1
。
当满足另外一定条件时,将 left_1
指针右移,即 left_1 += 1
。
当满足其他一定条件时,将 left_2
指针右移,即 left_2 += 1
。
当其中一个数组 / 链表遍历完时或者满足其他特殊条件时跳出循环体。
left_1 = 0
left_2 = 0
while left_1 < len(nums1) and left_2 < len(nums2):
if 一定条件 1:
left_1 += 1
left_2 += 2
elif 一定条件 2:
left_1 += 1
elif 一定条件 3:
left_2 += 1
分离双指针一般用于处理有序数组合并,求交集、并集问题。
下面我们根据具体例子来讲解如何使用分离双指针来解决问题。
4.4.1 题目链接
4.4.2 题目大意
描述:给定两个数组 nums1
和 nums2
。
要求:返回两个数组的交集。重复元素只计算一次。
说明:
$1 \le nums1.length, nums2.length \le 1000$。
$0 \le nums1[i], nums2[i] \le 1000$。
示例:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的
4.4.3 解题思路
思路 1:分离双指针
对数组 nums1
、nums2
先排序。
使用两个指针 left_1
、left_2
。left_1
指向第一个数组的第一个元素,即:left_1 = 0
,left_2
指向第二个数组的第一个元素,即:left_2 = 0
。
如果 nums1[left_1]
等于 nums2[left_2]
,则将其加入答案数组(注意去重),并将 left_1
和 left_2
右移。
如果 nums1[left_2]
小于 nums2[left_2]
,则将 left_1
右移。
如果 nums1[left_2]
大于 nums2[left_2]
,则将 left_2
右移。
最后输出答案数组。
思路 1:代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
left_1 = 0
left_2 = 0
res = []
while left_1 < len(nums1) and left_2 < len(nums2):
if nums1[left_1] == nums2[left_2]:
if nums1[left_1] not in res:
res.append(nums1[left_1])
left_1 += 1
left_2 += 1
elif nums1[left_1] < nums2[left_2]:
left_1 += 1
elif nums1[left_1] > nums2[left_2]:
left_2 += 1
return res
思路 1:复杂度分析
时间复杂度:$O(n)$。
空间复杂度:$O(1)$。
双指针分为「对撞指针」、「快慢指针」、「分离双指针」。
对撞指针:两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。
快慢指针:两个指针方向相同。适合解决数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。
分离双指针:两个指针分别属于不同的数组 / 链表。适合解决有序数组合并,求交集、并集问题。
文章浏览阅读86次。首发地址:https://yq.aliyun.com/articles/221708谈到机器学习,相信很多除学者都是通过斯坦福大学吴恩达老师的公开课《Machine Learning》开始具体的接触机器学习这个领域,但是学完之后又不知道自己的掌握情况,缺少一些实际的项目操作。对于机器学习的相关竞赛挑战,有些项目的门槛有些高,参加后难以具体的实现,因此造..._scrath五子棋下载
文章浏览阅读83次。原标题:Oracle 12c新特性系列专题-安徽Oracle授权认证中心 随着Oracle database 12c的普及,数据库管理员 (DBA) 的角色也随之发生了转变。 Oracle 12c数据库对 DBA 而言是下一代数据管理。它让 DBA 可以摆脱单调的日常管理任务,能够专注于如何从数据中获取更多价值。未来我们会推出基于Oracle12c的技术文章,帮助DBA尽快掌握新一代数据库的新特性..._ilm add policy row store compress advanced row after
文章浏览阅读150次。问题及代码:*Copyright(c)2016,烟台大学计算机与控制工程学院 *All right reserved. *文件名称:负数把正数赶出队列.cpp *作者:张冰 *完成日期;2016年10月09日 *版本号;v1.0 * *问题描述: 设从键盘输入一整数序列a1,a2,…an,试编程实现: 当ai>0时,ai进队,当ai<0时,将队首元素出队,当ai
文章浏览阅读376次。贪心+构造
文章浏览阅读150次。本文讲的是Linux命名空间学习教程(二) IPC,【编者的话】Docker核心解决的问题是利用LXC来实现类似VM的功能,从而利用更加节省的硬件资源提供给用户更多的计算资源。而 LXC所实现的隔离性主要是来自内核的命名空间, 其中pid、net、ipc、mnt、uts 等命名空间将容器的进程、网络、消息、文件系统和hostname 隔离开。本文是Li..._主机的 ipc 命名空间
文章浏览阅读2w次,点赞5次,收藏7次。在设备上强制安装apk。在app已有的情况下使用-r参数在app版本低于现有版本使用-d参数命令adb install -r -d xxx.apk_adb绕过安装程序强制安装app
文章浏览阅读290次。如果是越界进入硬件错误中断,MSP 或者 PSP 保存错误地址,跳转前会保存上一次执行的地址,lr 寄存器会保存子函数的地址,所以如果在 HardFault_CallBack 中直接调用 C 语言函数接口会间接修改了 lr,为了解决这个问题,直接绕过 lr 的 C 语言代码,用汇编语言提取 lr 寄存器再决定后面的操作。由于 STM32 加入了 FreeRTOS 操作系统,可能导致无法准确定位,仅供参考(日常编程需要考虑程序的健壮性,特别是对数组的访问,非常容易出现越界的情况)。_stm32flash地址越界怎么解决
文章浏览阅读1.8k次。学到了一种操作,说实话,我从来没想过还能这样正常情况下,为了管理方便,许多管理员都会开放MySQL数据库的secure_file_priv,这时就可以导入或者导出数据当我如图输入时,就会在D盘创建一个名为123456.php,内容为<?php phpinfo();?>的文件我们可以利用这一点运用到SQL注入中,从拿下数据库到拿下目标的服务器比如我们在使用联合查询注入,正常是这样的语句http://xxx?id=-1 union select 1,'你想知道的字段的内容或查询语句',
文章浏览阅读2.9w次,点赞12次,收藏63次。感谢原文:https://blog.csdn.net/abc5382334/article/details/24260817感谢原文:https://blog.csdn.net/jiaqingge/article/details/52564348Html CSS的三种链接方式css文本的链接方式有三种:分别是内联定义、链入内部css、和链入外部css1.代码为:<html>..._html链接css代码
文章浏览阅读625次。近几年,蓝牙耳机市场发展迅速,越来越多的消费者希望抛弃线缆,更自由地听音乐,对于运动人士来说,蓝牙耳机的便携性显得尤为重要。但目前市面上的大多数蓝牙耳机实际上都是“有线”的,运动过程中产生的听诊器效应会严重影响听歌的感受。而在“真无线”耳机领域,除了苹果的AirPods外,可供选择的产品并不多,而AirPods又不是为运动场景打造的,防水能力非常差。那么对于喜欢运动又想要“自由”的朋友来说,有没有一款产品能够满足他们的需求呢?下面这十款小编专门为大家搜罗的蓝牙耳机或许就能找到适合的!网红击音F1_适合游戏与运动的高音质蓝牙耳机
文章浏览阅读1k次,点赞6次,收藏7次。在本篇博文中,我们在 iOS 17 beta 4(SwiftUI 5.0)测试版中发现了 SwiftUI 视图首次显示时状态的改变会导致动画“副作用”的问题,并提出多种解决方案。
文章浏览阅读1.9k次。 在 上篇文章–Flutter 实现支持上拉加载和下拉刷新的 ListView 中,我们最终实现的效果是在 listView 上面留下了一段空白,本意是用来加载轮播图的,于是今天就开发了一下,希望能给各位灵感。一 、效果如下说一下大体思路 其实图片展示是用的 PageView ,然后,下面的指示器 是用的 TabPageSelector ,当然整体是用 Stack 包裹起来的。1、..._flutter pageview轮播图 site:csdn.net