《还在为面试发愁么Leecode习题分类整理!分类刷题效果更佳!》由会员分享，可在线阅读，更多相关《还在为面试发愁么Leecode习题分类整理!分类刷题效果更佳!（29页珍藏版）》请在金锄头文库上搜索。
1、1. Pattern: Sliding window，滑动窗口类型滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。该图中，我们的窗子不断往右一格一个移动下面是一些我们用来判断我们可能需要上滑动窗口策略的方法： 这个问题的输入是一些线性结构：比如链表呀，数组啊，字符串啊之类的 让你去求最长/最短子字符串或是某些特定的长度要求经典题目：Maximum Sum Subarray of Size K (easy)
2、Smallest Subarray with a given sum (easy)Longest Substring with K Distinct Characters (medium)Fruits into Baskets (medium)No-repeat Substring (hard)Longest Substring with Same Letters after Replacement (hard)Longest Subarray with Ones after Replacement (hard)2. Pattern: two points, 双指针类型双指针是这样的模式：两个
3、指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。我们需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 这是考虑算法的复杂度分析的时候的重要概念。虽然brute force一个指针的解法可能会奏效，但时间复杂度一般会是O(n)。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。上图是说，我们在排好序的数组里面找是否有一对数加起来刚好等于目标
4、和识别使用双指针的招数： 一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件 这种组合可能是一对数，三个数，或是一个子数组经典题目：Pair with Target Sum (easy)Remove Duplicates (easy)Squaring a Sorted Array (easy)Triplet Sum to Zero (medium)Triplet Sum Close to Target (medium)Triplets with Smaller Sum (medium)Subarrays with Product Less than a Target (me
5、dium)Dutch National Flag Problem (medium)3. Pattern: Fast & Slow pointers, 快慢指针类型这种模式，有一个非常出门的名字，叫龟兔赛跑。 咱们肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针：这种算法的两个指针的在数组上（或是链表上，序列上）的移动速度不一样。还别说，这种方法在解决有环的链表和数组时特别有用。通过控制指针不同的移动速度（比如在环形链表上），这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个（可以想象成跑道上面跑得快的人套圈跑得慢的人）。上面这个图演示了快慢两个指针最终在5相遇了咋知道需要用快慢指针模
6、式勒？ 问题需要处理环上的问题，比如环形链表和环形数组 当你需要知道链表的长度或是某个特别位置的信息的时候那啥时候用快慢指针而不是上面的双指针呢？ 有些情形下，咱们不应该用双指针，比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。经典题目：LinkedList Cycle (easy)Start of LinkedList Cycle (medium)Happy Number (medium)Middle of the LinkedList (easy)4. Pattern: Merge Intervals，区间合并类型区间合并模
7、式是一个用来处理有区间重叠的很高效的技术。在设计到区间的很多问题中，通常咱们需要要么判断是否有重叠，要么合并区间，如果他们重叠的话。这个模式是这么起作用的：给两个区间，一个是a，另外一个是b。别小看就两个区间，他们之间的关系能跑出来6种情况。详细的就看图啦。理解和识别这六种情况，灰常重要。因为这能帮你解决一大堆问题。这些问题从插入区间到优化区间合并都有。怎么识别啥时候用合并区间模式呀？ 当你需要产生一堆相互之间没有交集的区间的时候 当你听到重叠区间的时候经典题目：Merge Intervals (medium)Insert Interval (medium)Intervals Intersec
8、tion (medium)Conflicting Appointments (medium)5. Pattern: Cyclic Sort，循环排序这种模式讲述的是一直很好玩的方法：可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上，但这复杂度就会是O(n2)。这样的话，可能就不是最优解了。因此循环排序的优势就体现出来了。咋鉴别这种模式？ 这些问题一般设计到排序好的数组，而且数值一般满足于一定的区间 如果问题让你需要在排好序/翻转过的数组中，寻找
9、丢失的/重复的/最小的元素经典题目：Cyclic Sort (easy)Find the Missing Number (easy)Find all Missing Numbers (easy)Find the Duplicate Number (easy)Find all Duplicate Numbers (easy)6. Pattern: In-place Reversal of a LinkedList，链表翻转在众多问题中，题目可能需要你去翻转链表中某一段的节点。通常，要求都是你得原地翻转，就是重复使用这些已经建好的节点，而不使用额外的空间。这个时候，原地翻转模式就要发挥威力了。这种
10、模式每次就翻转一个节点。一般需要用到多个变量，一个变量指向头结点（下图中的current），另外一个（previous）则指向咱们刚刚处理完的那个节点。在这种固定步长的方式下，你需要先将当前节点（current）指向前一个节点（previous），再移动到下一个。同时，你需要将previous总是更新到你刚刚新鲜处理完的节点，以保证正确性。咱们怎么去甄别这种模式呢？ 如果你被问到需要去翻转链表，要求不能使用额外空间的时候经典题目：Reverse a LinkedList (easy)Reverse a Sub-list (medium)Reverse every K-element Sub-l
11、ist (medium)7. Pattern: Tree Breadth First Search，树上的BFS这种模式基于宽搜（Breadth First Search (BFS)），适用于需要遍历一颗树。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。这种树上的BFS模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。识别树上的BFS模
12、式： 如果你被问到去遍历树，需要按层操作的方式（也称作层序遍历）经典题目：Binary Tree Level Order Traversal (easy)Reverse Level Order Traversal (easy)Zigzag Traversal (medium)Level Averages in a Binary Tree (easy)Minimum Depth of a Binary Tree (easy)Level Order Successor (easy)Connect Level Order Siblings (medium)8. Pattern: Tree Depth
13、 First Search，树上的DFS树形DFS基于深搜（Depth First Search (DFS)）技术来实现树的遍历。咱们可以用递归（或是显示栈，如果你想用迭代方式的话）来记录遍历过程中访问过的父节点。该模式的运行方式是从根节点开始，如果该节点不是叶子节点，我们需要干三件事：1. 需要区别我们是先处理根节点（pre-order，前序），处理孩子节点之间处理根节点（in-order，中序），还是处理完所有孩子再处理根节点（post-order，后序）。2. 递归处理当前节点的左右孩子。识别树形DFS： 你需要按前中后序的DFS方式遍历树 如果该问题的解一般离叶子节点比较近。经典题目：
14、Binary Tree Path Sum (easy)All Paths for a Sum (medium)Sum of Path Numbers (medium)Path With Given Sequence (medium)Count Paths for a Sum (medium)9. Pattern: Two Heaps，双堆类型很多问题中，我们被告知，我们拿到一大把可以分成两队的数字。为了解决这个问题，我们感兴趣的是，怎么把数字分成两半？使得：小的数字都放在一起，大的放在另外一半。双堆模式就能高效解决此类问题。正如名字所示，该模式用到了两个堆，是不是很难猜？一个最小堆用来找最小元
15、素；一个最大堆，拿到最大元素。这种模式将一半的元素放在最大堆中，这样你可以从这一堆中秒找到最大元素。同理，把剩下一半丢到最小堆中，O(1)时间找到他们中的最小元素。通过这样的方式，这一大堆元素的中位数就可以从两个堆的堆顶拿到数字，从而计算出来。判断双堆模式的秘诀： 这种模式在优先队列，计划安排问题（Scheduling）中有奇效 如果问题让你找一组数中的最大/最小/中位数 有时候，这种模式在涉及到二叉树数据结构时也特别有用经典题目：Find the Median of a Number Stream (medium)Sliding Window Median (hard)Maximize Capital (hard)10. Pattern: Subsets，子集类型，一般都是使用多重DFS超级多的编程面试问题都会涉及到排列和组合问题。子集问题模式讲的是用BFS来处理这些问题。这个模式是这样的：给一组数字 1, 5, 31. 我们从空集开始：2. 把第一个数（1），加到之前已经存在的集合中：, 1;3. 把第二个数（5），加到之前的集合中得到：, 1, 5,
