14种模式搞定面试算法编程题（PART II）

面试锦囊之知识整理系列

面试锦囊系列一直有收到大家的反馈，包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等，非常高兴小破号的这些整理分享能够真正地帮助到大家

好了不废话啦，今天文章的主题继续分享上一篇未写完的部分，14种模式搞定面试算法编程题（PART I）。经过本人之前笔试面试经验证明确实确实非常非常高频，一定要十分熟悉。对于每一种思路会给出

• 「基本原理（附图）」
• 「应用场景」
• 「Leetcode或剑指offer具体栗子」 enjoy！

8、循环排序

循环排序模式描述了一种处理涉及包含给定范围内的数字的数组问题的有趣方法。其一次遍历数组一个数字，如果正在迭代的当前数字不是正确的索引，则将其与正确索引处的数字交换。

应用场景

• 涉及给定范围内的数字的排序数组
• 要求在已排序/旋转的数组中找到缺失/重复/最小的数字

举个栗子

• 缺失数字（LEETCODE）[1]
• 寻找重复数（LEETCODE）[2]
• 缺失的第一个正数（LEETCODE）[3]

9、就地反转链表

在许多问题中，可能会要求我们反转链表的一组节点之间的链接。通常，约束就是需要就地执行此操作，即使用现有节点对象而不使用额外内存。这是上述模式有用的地方。

此模式一次反转一个节点，从一个指向链表头部的变量（当前）开始，一个变量（上一个）将指向已处理的上一个节点。以锁步方式，将通过将当前节点指向前一个节点，然后再转到下一个节点来反转当前节点。此外，更新变量“previous”以始终指向您已处理的上一个节点。

应用场景

• 就地反转链表

举个栗子

• 反转链表（LEETCODE）[4]
• 反转链表II（LEETCODE）[5]

10、Two heaps

在许多问题中，给出了一系列元素，需要我们将其分成两部分。为了解决这个问题，我们想要知道一个部分中的最小元素和另一个部分中的最大元素。这种模式是解决此类问题的有效方法。

这种模式使用两个堆：找到最小元素的Min Heap和找到最大元素的Max Heap。该模式的工作原理是将前半部分的数字存储在Max Heap中，这是因为我们希望在上半部分找到最大的数字。然后将数字的后半部分存储在Min Heap中，因为我们希望在后半部分找到最小的数字。在任何时候，可以从两个堆的顶部元素计算当前数字列表的中值。

应用场景

• 优先队列，调度等情况
• 找到集合中的最小/最大/中值元素
• 有时，在以二叉树数据结构为特征的问题中很有用

举个栗子

• 数据流的中位数（LEETCODE）[6]
• 滑动窗口的最大值（剑指offer）[7]

11、Modified binary search

无论何时给定排序数组，链表或矩阵，并要求查找某个元素，你可以使用的最佳算法是二分搜索。此模式描述了处理涉及二分搜索的所有问题的有效方法。二分搜索这么经典的思路我就不多介绍啦，直接看一个可视化复习一下

举个栗子

• 搜索旋转排序数组（LEETCODE）[8]
• 寻找两个有序数组的中位数（LEETCODE）[9]
• 寻找旋转排序数组中的最小值（LEETCODE）[10]

12、Top K

任何要求我们在给定集合中找到最大/最小/频繁“K”元素的问题都属于这种模式。

跟踪'K'元素的最佳数据结构是Heap。这种模式将利用Heap来解决从一组给定元素一次处理'K'元素的多个问题。大致思路是这样的：

• 根据问题将'K'元素插入到最小堆或最大堆中；
• 迭代剩余的数字，如果找到一个比堆中的数字大的数字，则删除该数字并插入较大的数字

应用场景

• 要求找到给定集合的最大/最小/频繁“K”元素；
• 要求对数组进行排序以找到确切的元素

举个栗子

• 前K个高频元素（LEETCODE）[11]
• 前K个高频单词（LEETCODE）[12]
• 第k个排列（LEETCODE）[13]

13、K-way Merge

K-way Merge可以用于解决涉及一组排序数组的问题。

给出'K'排序数组，可以使用Heap有效地执行所有数组的所有元素的排序遍历。我们可以在Min Heap中push每个数组的最小元素以获得最小值。获得总体最小值后，将下一个元素从同一个数组推送到堆中。然后，重复此过程以对所有元素进行排序遍历。

应用场景

• 适用于排序的数组，列表或矩阵
• 问题要求合并排序列表，在排序列表中查找最小元素等

举个栗子

• 合并两个有序链表（LEETCODE）[14]
• 合并K个排序链表（LEETCODE）[15]
• 丑数系列（LEETCODE）[16]

14、Topological sort

拓扑排序用于查找彼此依赖的元素的线性排序。例如，如果事件“B”依赖于事件“A”，则“A”在拓扑排序中位于“B”之前。流程大概是这样的：

• 初始化。
  • a) 使用散列映射将图存储在邻接表中
  • b) 要查找所有sources，使用HashMap维护入度的计数
• 建立图并找出所有顶点的入度
  • a) 从输入构建图形并填充内部HashMap
• 查找所有的sources
  • 所有入度为“0”的节点被认为是source，并存入队列中
• 排序
  • 将其添加到已排序列表中
  • 从图中获取它的所有子结点
  • 将每个子节点的入度减一
  • 如果某个子节点的入度为“0”,则将其加入队列中
  • 对于每一个source，do：
  • 重复上述步骤直到队列为空

  

应用场景

• 需要处理没有定向循环的图
• 要求按排序顺序更新所有对象
• 如果有一组遵循特定顺序的对象

举个栗子

• 课程表系列（LEETCODE）[17]
• 矩阵中的最长递增路径（LEETCODE）[18]
• 序列重建（LEETCODE）[19]

本文参考资料

[1]

缺失数字（LEETCODE）: https://leetcode-cn.com/problems/missing-number/

[2]

寻找重复数（LEETCODE）: https://leetcode-cn.com/problems/find-the-duplicate-number/

[3]

缺失的第一个正数（LEETCODE）: https://leetcode-cn.com/problems/first-missing-positive/

[4]

反转链表（LEETCODE）: https://leetcode-cn.com/problems/reverse-linked-list/

[5]

反转链表II（LEETCODE）: https://leetcode-cn.com/problems/reverse-linked-list-ii/

[6]

数据流的中位数（LEETCODE）: https://leetcode-cn.com/problems/find-median-from-data-stream/

[7]

滑动窗口的最大值（剑指offer）: https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

[8]

搜索旋转排序数组（LEETCODE）: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

[9]

寻找两个有序数组的中位数（LEETCODE）: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

[10]

寻找旋转排序数组中的最小值（LEETCODE）: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

[11]

前K个高频元素（LEETCODE）: https://leetcode-cn.com/problems/top-k-frequent-elements/

[12]

前K个高频单词（LEETCODE）: https://leetcode-cn.com/problems/top-k-frequent-words/

[13]

第k个排列（LEETCODE）: https://leetcode-cn.com/problems/permutation-sequence/

[14]

合并两个有序链表（LEETCODE）: https://leetcode-cn.com/problems/merge-two-sorted-lists/

[15]

合并K个排序链表（LEETCODE）: https://leetcode-cn.com/problems/merge-k-sorted-lists/

[16]

丑数系列（LEETCODE）: https://leetcode-cn.com/problems/ugly-number-ii/

[17]

课程表系列（LEETCODE）: https://leetcode-cn.com/problems/course-schedule/

[18]

矩阵中的最长递增路径（LEETCODE）: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

[19]

序列重建（LEETCODE）: https://leetcode-cn.com/problems/sequence-reconstruction/

- END -