太仓市住房和城乡建设局规网站,网站开发实训基本要求,汕头网站建设搭建,跨境电商平台介绍文章目录 1 双指针基础知识1.1 双指针简介1.2 左右指针#xff08;对撞指针#xff09;1.3 快慢指针1.4 分离双指针 2 滑动窗口基础知识2.1 滑动窗口算法介绍2.2 滑动窗口适用范围2.3 固定长度滑动窗口2.4 不固定长度滑动窗口 1 双指针基础知识
1.1 双指针简介
双指针… 文章目录 1 双指针基础知识1.1 双指针简介1.2 左右指针对撞指针1.3 快慢指针1.4 分离双指针 2 滑动窗口基础知识2.1 滑动窗口算法介绍2.2 滑动窗口适用范围2.3 固定长度滑动窗口2.4 不固定长度滑动窗口 1 双指针基础知识
1.1 双指针简介
双指针Two Pointers 是一种常用的算法技巧通常用于在数组或链表中进行遍历或搜索。它使用两个指针在不同的位置上移动以解决特定的问题。
双指针常见的应用场景包括
快慢指针两个指针方向相同但是使用两个指针以不同的速度遍历链表用于解决链表中的环检测、链表中点、链表倒数第k个节点等问题。左右指针对撞指针在有序数组中使用两个指针从数组的两端向中间移动以解决查找目标值、两数之和、三数之和等问题。分离双指针两个指针分别属于不同的数组/链表。
双指针算法通常具有较低的时间复杂度并且可以在一次遍历中完成任务因此在很多问题中都有很好的应用。
1.2 左右指针对撞指针
左右指针Left and Right Pointers是双指针算法中的一种常见技巧。它通常用于在有序数组或字符串中查找目标值、寻找满足某种条件的子序列等问题。
左右指针的基本思想是使用两个指针分别指向数组或字符串的左右两端然后根据问题的要求通过移动指针的位置来逼近或搜索目标。
基本步骤
两个指针 l e f t left left 和 r i g h t right right。 l e f t left left 指向序列第一个元素 l e f t 0 left0 left0 r i g h t right right 指向序列最后一个元素 r i g h t l e n ( n u m s ) − 1 rightlen(nums)-1 rightlen(nums)−1 。循环体中将左右指针相向移动当满足一定条件时将左指针右移 l e f t 1 left 1 left1 。当满足另外一定条件时将右指针左移 r i g h t 1 right 1 right1 。直到两个指针相撞 l e f t r i g h t leftright leftright 或者满足其他要求的特殊条件时跳出循环体。
伪代码模板
left, right 0, len(nums) - 1while left right:if 满足要求的特殊条件:return 符合条件的值 elif 一定条件 1:left 1elif 一定条件 2:right - 1return 没找到 或 找到对应值适用范围 有序数组或有序链表左右指针可以在有序数组或有序链表中进行查找、搜索、比较等操作。通过左右指针的移动可以快速定位目标值或满足特定条件的元素。 滑动窗口问题滑动窗口问题通常涉及在数组或字符串上定义一个窗口并通过移动窗口的左右边界来解决问题。左右指针可以用于表示窗口的左右边界并根据问题的要求进行移动和调整。 两数之和、三数之和等问题在有序数组中查找满足特定条件的数对或数组合时左右指针可以进行逼近快速找到满足条件的解。 回文字符串判断左右指针可以用于判断字符串是否是回文字符串。通过左右指针从两端向中间移动并比较对应位置的字符是否相等可以判断字符串是否是回文。
1.3 快慢指针
快慢指针Fast and Slow Pointers基本思想是使用两个指针一个指针快指针 fast移动速度较快另一个指针慢指针 slow移动速度较慢。通过两个指针的相对移动可以得到一些有用的信息从而解决问题。
基本步骤 初始化快慢指针将快指针和慢指针都指向链表的头节点或数组的起始位置。 s l o w 0 , f a s t 1 或 0 slow0, fast1 或 0 slow0,fast1或0 移动指针根据问题的要求通过移动快慢指针来逼近目标或获取有用的信息。 快指针移动通常每次移动两步或一步可以快速遍历整个链表或数组。 f a s t 1 fast 1 fast1慢指针移动通常每次移动一步慢指针的移动速度较慢。 s l o w 1 slow1 slow1 判断终止条件根据问题的要求判断是否满足终止条件。 例如在链表中环检测问题中如果快指针和慢指针相遇则存在环如果快指针到达链表末尾则不存在环。 根据问题的要求返回结果。 例如在链表中找到中间节点的问题中当快指针到达链表末尾时慢指针所指的节点就是中间节点。
伪代码模板
slow 0
fast 1
while 没有遍历完if 满足要求的特殊条件:slow 1fast 1
return 合适的值适用范围 链表中的环检测快慢指针可以用于判断链表中是否存在环。快指针每次移动两步慢指针每次移动一步如果链表中存在环则快指针最终会追上慢指针二者相遇。 链表中点的查找快慢指针可以用于找到链表的中间节点。快指针每次移动两步慢指针每次移动一步当快指针到达链表末尾时慢指针正好在链表的中间位置。 链表倒数第k个节点的查找快慢指针可以用于定位链表的倒数第k个节点。快指针先移动k个位置然后快慢指针同时向前移动当快指针到达链表末尾时慢指针所指的节点就是倒数第k个节点。 判断链表是否有交点快慢指针可以用于判断两个链表是否相交。分别使用快慢指针遍历两个链表如果两个链表相交则快指针和慢指针最终会相遇。 数组中的重复元素查找快慢指针可以用于在数组中查找重复元素。通过快慢指针的移动可以找到数组中的重复元素或判断数组是否存在重复元素。
1.4 分离双指针
分离双指针Two Pointers with Separation是一种双指针算法的变体它通常用于解决数组或链表中需要分离的问题例如将奇偶数分离、将0和非0元素分离等。分离双指针的基本思想是使用两个指针一个指针分离指针用于分离元素另一个指针遍历指针用于遍历数组或链表。通过移动遍历指针并根据特定条件将元素交换到分离指针的位置实现元素的分离。
基本步骤 两个指针 l e f t 1 left_1 left1、 l e f t 2 left_2 left2 。 l e f t 1 left_1 left1 指向第一个数组的第一个元素 l e f t 1 0 left_10 left10 l e f t 2 left_2 left2 指向第二个数组的第一个元素 l e f t 2 0 left_20 left20。 当满足一定条件时 两个指针同时右移 l e f t 1 1 、 l e f t 2 1 left_1 1、left_2 1 left11、left21。 l e f t 1 left_1 left1 右移 l e f t 1 1 left_1 1 left11。 l e f t 2 left_2 left2 右移 l e f t 2 1 left_2 1 left21。 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。
伪代码模板
left_1 0
left_2 0while left_1 len(nums1) and left_2 len(nums2):if 一定条件 1:left_1 1left_2 1elif 一定条件 2:left_1 1elif 一定条件 3:left_2 1适用范围
分离双指针一般用于处理有序数组合并求交集、并集问题
349. 两个数组的交集 - 力扣LeetCode 思路分离双指针
两个数组先排序。 n u m s 1 、 n u m s 2 nums1、nums2 nums1、nums2使用两个指针分别指向两个数组的第一个元素即第一个指针指向第一个数组的第一个元素第二个指针指向第二个数组的第一个元素。 l e f t 1 0 、 l e f t 2 0 left_10、left_20 left10、left20如果 n u m s 1 [ l e f t 1 ] n u m s 2 [ l e f t 2 ] nums1[left_1]nums2[left_2] nums1[left1]nums2[left2] 则将其加入答案数组注意去重并将 l e f t 1 left_1 left1 和 l e f t 2 0 left_20 left20 右移 l e f t 1 1 left_1 1 left11 、 l e f t 2 1 left_2 1 left21。如果 n u m s 1 [ l e f t 1 ] n u m s 2 [ l e f t 2 ] nums1[left_1] nums2[left_2] nums1[left1]nums2[left2] 则 l e f t 1 left_1 left1 右移 。如果 n u m s 1 [ l e f t 1 ] n u m s 2 [ l e f t 2 ] nums1[left_1] nums2[left_2] nums1[left1]nums2[left2] 则 l e f t 2 left_2 left2 右移 。返回答案。
代码
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) - List[int]:nums1.sort()nums2.sort()left_1 0left_2 0res []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 1left_2 1elif nums1[left_1] nums2[left_2]:left_1 1elif nums1[left_1] nums2[left_2]:left_2 1return res2 滑动窗口基础知识
2.1 滑动窗口算法介绍
滑动窗口算法Sliding Window Algorithm是一种常用的算法技巧用于解决数组或字符串相关的问题。它的基本思想是维护一个窗口通过在数组或字符串上滑动窗口不断更新窗口内的状态从而解决问题。可以对窗口进行滑动操作、缩放操作以及维护最优解操作。
滑动操作窗口向一个方向移动常见的是向右侧移动。缩放操作针对不固定长度的窗口可以从左侧缩小窗口长度也可以从右侧扩大窗口长度。
2.2 滑动窗口适用范围
滑动窗口算法通常适用于线性数据结构如数组和字符串。它在处理大规模数据时特别有用因为它可以通过滑动窗口的方式仅对部分数据进行处理而不需要遍历整个数据集。这使得滑动窗口算法具有较低的时间复杂度并且在实际应用中常常能够提供高效的解决方案。
按照窗口长度的固定情况我们可以将滑动窗口题目分为以下两种 固定长度窗口窗口大小是固定的。 不定长度窗口 窗口大小是不固定的。 求解最大的满足条件的窗口。 求解最小的满足条件的窗口。
2.3 固定长度滑动窗口
固定长度滑动窗口是一种特殊的滑动窗口算法它的窗口大小固定不会随着数据集的变化而变化。该算法通常用于需要对连续的数据序列进行处理的问题如时间序列数据分析等。
固定长度滑动窗口的基本思想是将数据序列分成若干个固定长度的子序列然后对每个子序列进行处理。在处理每个子序列时可以使用滑动窗口算法通过移动窗口来更新子序列内的状态从而得到最终的结果。
基本步骤
固定长度滑动窗口的步骤如下
初始化窗口的起始位置和结束位置窗口大小固定。对于每个窗口内的子序列根据问题要求更新窗口内的状态。如果窗口满足特定条件记录结果。继续移动窗口的起始位置重复上述步骤直到遍历完整个数据集。
代码模板
left 0
right 0while right len(nums):window.append(nums[right])# 超过窗口大小时缩小窗口维护窗口中始终为 window_size 的长度if right - left 1 window_size:# ... 维护答案window.popleft()left 1# 向右侧增大窗口right 12.4 不固定长度滑动窗口
不定长度滑动窗口算法Sliding Window在给定数组 / 字符串上维护一个不定长度的窗口。可以对窗口进行滑动操作、缩放操作以及维护最优解操作。
基本步骤
使用两个指针 l e f t left left、 r i g h t right right。初始时 l e f t left left、 r i g h t right right 都指向序列的第一个元素。即 l e f t 0 left0 left0 r i g h t 0 right0 right0区间 [ l e f t , r i g h t ] [left,right] [left,right] 被称为一个「窗口」。将区间最右侧元素添加入窗口中即 window.add(s[right])。然后向右移动 r i g h t right right从而增大窗口长度即 right 1。直到窗口中的连续元素满足要求。此时停止增加窗口大小。转向不断将左侧元素移出窗口即 window.popleft(s[left])。然后向右移动 l e f t left left从而缩小窗口长度即 left 1。直到窗口中的连续元素不再满足要求。重复 2 ~ 5 步直到 r i g h t right right 到达序列末尾。
代码模板
left 0
right 0while right len(nums):window.append(nums[right])while 窗口需要缩小:# ... 可维护答案window.popleft()left 1# 向右侧增大窗口right 1参考文献
[1] https://datawhalechina.github.io/leetcode-notes/#/
—— END —— 如果以上内容有任何错误或者不准确的地方欢迎在下面 留言。或者你有更好的想法欢迎一起交流学习~~~
更多精彩内容请前往 AXYZdong的博客
