滑动窗口用于对给定数组和链表的特定窗口大小执行所需的操作
“两个指针”是一种模式,其中两个指针串联遍历数据结构,直到一个或两个指针都达到特定条件。两个指针在排序数组或链接列表中搜索对时通常很有用;例如,当您必须将数组的每个元素与其他元素进行比较时。
需要两个指针,因为只有一个指针,您将不得不不断地循环遍历数组以找到答案。用单个迭代器来回进行此操作对于时间和空间复杂度而言效率低下-一种称为渐近分析的概念。尽管使用1个指针的强力或幼稚的解决方案将起作用,但它将产生类似于O(n²)的东西。在许多情况下,两个指针可以帮助您找到具有更好空间或运行时复杂性的解决方案。
确定何时使用“两指针”方法的方法:
以下是具有两个指针模式的一些问题:
快速和慢速指针方法,也称为 Hare&Tortoise算法,是一种指针算法,它使用两个指针以不同的速度在数组(或序列/链接列表)中移动。 处理循环链表或数组时,此方法非常有用。
通过以不同的速度移动(例如,在循环链表中),该算法证明两个指针必然会合。一旦两个指针都处于循环循环中,快速指针应捕获慢速指针。
您如何确定何时使用快速和慢速模式?
什么时候应该在上面提到的“两指针”方法上使用它?
具有快速和慢速指针模式的问题:
合并间隔模式是处理重叠间隔的有效技术。在很多涉及间隔的问题中,您需要找到重叠的间隔,或者如果它们重叠,则需要合并间隔。该模式如下所示:
给定两个间隔(“ a”和“ b”),两个间隔可以通过六种不同的方式相互关联:
了解和认识这六个情况将帮助您解决从插入间隔到优化间隔合并的各种问题。
您如何确定何时使用“合并间隔”模式?
此模式描述了一种有趣的方法来处理涉及包含给定范围内的数字的数组的问题。循环排序模式一次在数组上迭代一个数字,如果要迭代的当前数字不在正确的索引处,则将其与在其正确的索引处的数字交换。您可以尝试将数字放置在正确的索引中,但这会导致O(n ^ 2)的复杂度不是最优的,因此是循环排序模式。
[图片上传失败...(image-b02483-1592497226252)]
如何识别这种模式?
具有循环排序模式的问题:
在很多问题中,可能会要求您反向链接列表的一组节点之间的链接。通常,约束是您需要就地执行此操作,即使用现有的节点对象而不使用额外的内存。这是上面提到的模式有用的地方。
此模式一次反转一个节点,其中一个变量(当前)指向链接列表的开头,而一个变量(上一个)将指向您已处理的上一个节点。以锁定步骤的方式,您可以通过将当前节点指向上一个节点来反转该节点,然后再移动到下一个节点。另外,您将更新变量“ previous”以始终指向您已处理的上一个节点。
如何确定何时使用此模式:
链表模式就地反转的问题:
此模式基于广度优先搜索(BFS)技术来遍历树,并使用队列来跟踪某个级别的所有节点,然后再跳转到下一个级别。使用这种方法可以有效地解决涉及逐级遍历树的任何问题。
Tree BFS模式的工作原理是将根节点推送到队列,然后不断迭代直到队列为空。对于每次迭代,我们都删除队列开头的节点,然后“访问”该节点。从队列中删除每个节点后,我们还将其所有子节点插入队列。
如何识别Tree BFS模式:
具有Tree BFS模式的问题:
二叉树级顺序遍历(简单)
树DFS基于深度优先搜索(DFS)技术遍历树。
您可以使用递归(或使用堆栈进行迭代)在遍历时跟踪所有先前的(父)节点。
Tree DFS模式通过从树的根部开始工作,如果节点不是叶子,则需要做三件事:
如何识别Tree DFS模式:
具有Tree DFS模式的问题: