14种模式解决面试算法编程题（PART I）

520jefferson 2019-06-26

展开全文

作者：高开远

学校：上海交通大学

研究方向：自然语言处理

写在前面

万万没想到，暑假还没开始，有些公司的秋招提前批已经来了…很慌…数据结构和算法题可以说是秋招笔试面试必考的内容，如果你还不够熟练（just like me），那就要从现在开始疯狂刷题了啊朋友们。

附上我的部分刷题记录（不完整leetcode和完整剑指offer），内含详细解题思路：Kick_Algorithm，欢迎加入我一起刷题~

https://github.com/KaiyuanGao/Kick_Algorithm

好了，今天文章的主题就是分享14种解决面试算法编程题的思路（来自educative），经过本人之前春招笔试面试经验证明确实确实非常非常高频，一定要十分熟悉。对于每一种思路会给出

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

enjoy！

1、滑动窗口

滑动窗口模式用于对给定数组或链表的特定窗口大小执行所需操作，例如查找包含所有1的最长子序列。滑动窗口从第一个元素开始，每次向右移动一个元素并根据要解决的问题调整窗口的长度。在某些情况下，窗口的大小保持不变，而在其他情况下，大小会增大或缩小。

应用场景

okay，理解了滑动窗口原理之后，那么什么情况下我们会需要用到它呢？

问题输入是线性数据结构，如链表、数组或字符串
题目要求查找最长/最短的子字符串、子数组或所需的值

举个栗子

来看看实际应用滑动窗口解决的问题

滑动窗口的最大值（剑指offer）
滑动窗口中位数（LEETCODE）
最小覆盖子串（LEETCODE）
K 个不同整数的子数组（LEETCODE）

2、双指针

双指针的基本思想是使用两个指针串联迭代数据结构，知道一个或两个指针达到某个条件停止。在排序数组或链表中搜索元素对时，两个指针通常很有用，例如将数组的每个元素与其他元素进行比较时。

通常我们需要两个指针是因为如果只采用单个指针，必须不断循环数组才能找到答案。这种解决方案虽然确实可行，但是对时间和空间复杂度来说明显是低效的。在许多情况下，使用双指针可以帮助你找到具有更好空间或时间复杂度的解决方案。

应用场景

问题为排序数组或链表，并且需要满足某些约束的一组元素问题
数组中的元素集是一对，三元组，甚至是子数组

举个栗子

N-sum问题（LEETCODE）
无重复字符的最长自创（LEETCODE）
接雨水（LEETCODE）
长度最小的子数组（LEETCODE）

3、快慢指针

也被称为“龟兔算法”，基本思想是使用两个指针以不同的速度在数组或链表中移动。在处理循环链接列表或数组时，此方法非常有用。通过以不同的速度移动（例如，在循环链表中），算法证明两个指针必然会相遇。一旦两个指针都处于循环循环中，快速指针就应该捕获慢速指针。

应用场景

链表或数组循环
用于找中间元素
需要知道某个元素的位置或链表的总长度

举个栗子

环形链表（LEETCODE）
相交链表（LEETCODE）
环形链表入口节点（LEETCODE）

4、合并区间

合并间隔模式是处理重叠间隔的有效技术。在涉及间隔的许多问题中，你可以需要找到重叠间隔或合并间隔（如果它们重叠）。给定两个间a和b，可能存在6中不同的间隔交互情况：

应用场景

要求生成仅具有互斥间隔的列表
出现“overlapping intervals”一词

举个栗子

合并区间（LEETCODE）
会议室（LEETCODE）
Range模块（LEETCODE）
区间列表的交集（LEETCODE）

5、循环排序

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

应用场景

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

举个栗子

缺失数字（LEETCODE）
寻找重复数（LEETCODE）
缺失的第一个正数（LEETCODE）

6、就地反转链表

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

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

应用场景

就地反转链表

举个栗子

反转链表（LEETCODE）
反转链表II（LEETCODE）

7、Two heaps

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

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