学会这14种模式,你可以轻松回答任何编码面试问题
共 5113字,需浏览 11分钟
· 2020-10-17
滑动窗口
两个指针或迭代器
快指针或慢指针或迭代器
合并间隔
循环排序
就地反转链表
Tree BFS
Tree DFS
两堆
子集
修改后的二进制搜索
前K个元素
K路合并
拓扑排序
问题输入是线性数据结构,例如链表,数组或字符串
要求你找到最长/最短的子字符串,子数组或所需的值
大小为" K"的最大总和子数组(简单)
带有" K"个不同字符的最长子字符串(中)
字谜(硬)
在处理排序数组(或链接列表)并且需要找到一组满足某些约束的元素时,它将遇到一些问题。
数组中的元素集是一对,三元组甚至是子数组
平方排序数组(简单)
总计为零的三元组(中)
比较包含退格键的字符串(中)
该问题将处理链表或数组中的循环
当你需要知道某个元素的位置或链表的总长度时。
在某些情况下,你不应该使用"两指针"方法,例如在单链列表中,你不能向后移动。何时使用快速和慢速模式的一个例子是,当你尝试确定链接列表是否是回文。
链接列表周期(简单)
回文链接列表(中)
循环循环阵列(硬)
如果要求你仅以互斥间隔生成列表
如果你听到术语"重叠间隔"。
区间相交(中)
最大CPU负载(硬)
它们将是涉及编号在给定范围内的排序数组的问题
如果问题要求你在排序/旋转数组中查找缺失/重复/最小的数字
查找丢失的号码(简单)
查找最小的遗漏正数(中)
如果要求你在不占用额外内存的情况下反向链接列表
撤消子列表(中)
反转每个K元素子列表(中)
如果要求你逐级遍历一棵树(或逐级遍历)
二叉树级顺序遍历(简单)
锯齿形遍历(中)
决定是立即处理当前节点(预订),还是在处理两个子节点之间(按顺序),还是在处理两个子节点之后(后处理)。
对当前节点的两个子节点进行两次递归调用以处理它们。
如果系统要求你按顺序,预定或后置DFS遍历一棵树
如果问题需要在节点更靠近叶子的位置进行搜索
路径数总和(中)
求和的所有路径(中)
在诸如"优先级队列","计划"之类的情况下很有用
如果问题表明您需要找到集合中最小/最大/中值的元素
有时,对于解决具有二叉树数据结构的问题很有用
查找数字流的中位数(中)
从一个空集开始:[[]]
将第一个数字(1)添加到所有现有子集以创建新的子集:[[],[1]];
将第二个数字(5)添加到所有现有子集:[[],[1],[5],[1,5]];
将第三个数字(3)添加到所有现有子集:[[],[1],[5],[1,5],[3],[1,3],[5,3],[1, 5,3]]。
你需要查找给定集合的组合或排列的问题
重复子集(简单)
更改大小写的字符串排列(中)
首先,找到开始和结束的中间位置。查找中间值的简单方法是:middle =(start + end)/2。但这很有可能产生整数溢出,因此建议将中间值表示为:Middle = start +(end-start) / 2
如果键等于索引中间的数字,则返回中间
如果"键"不等于中间索引:
检查键
检查key> arr [middle]。如果减少,则搜索结束=中间+1
与订单无关的二进制搜索(简单)
在排序的无限数组中搜索
根据问题将" K"元素插入最小堆或最大堆。
遍历剩余的数字,如果发现一个大于堆中数字的数字,则删除该数字并插入较大的数字。
如果系统要求你查找给定集合中顶部/最小/频繁的" K"元素
如果系统要求你对数组进行排序以查找确切的元素
前" K"个数字(简单)
前" K"个常见数字(中)
将每个数组的第一个元素插入最小堆中。
之后,从堆中取出最小的(顶部)元素并将其添加到合并列表中。
从堆中删除最小的元素后,将相同列表的下一个元素插入堆中。
重复步骤2和3,以按排序顺序填充合并列表。
该问题将出现排序的数组,列表或矩阵
如果问题要求你合并排序列表,请在排序列表中找到最小的元素。
合并K个排序列表(中)
K对最大和(硬)
初始化
a)使用HashMap将图存储在邻接列表中
b)要查找所有源,请使用HashMap保持度数
构建图并找到所有顶点的度数
a)从输入中构建图并填充度数HashMap。
查找所有源
a)所有度数为" 0"的顶点将作为源,并存储在队列中。
排序
a)对于每个来源,请执行以下操作:
—i)将其添加到排序列表中。
— ii)从图中获取其所有子级。
— iii)将每个孩子的度数减1。
— iv)如果一个孩子的度数变为" 0",则将其添加到源队列中。
b)重复(a),直到源队列为空。
该问题将处理没有定向周期的图
如果系统要求你按排序顺序更新所有对象
如果你有一类遵循特定顺序的对象
任务计划(中)
最小树高(硬)