14种模式解决面试算法编程题(PART II)

栏目: 编程工具 · 发布时间: 5年前

作者: 高开远

学校: 上海交通大学

研究方向: 自然语言处

写在前面

继续, 14种模式解决面试算法编程题(PART I)

8、树的宽度优先搜索(Tree BFS)

该模式基于广度优先搜索(BFS)技术来遍历树,并使用队列在跳到下一层之前记录下该层的所有节点。使用这种方法可以有效地解决涉及以逐级顺序遍历树的任何问题。Tree BFS模式的基本思想是将根节点push到队列然后不断迭代直到队列为空。对于每次迭代,删除队列头部的节点并“访问”该节点。从队列中删除每个节点后,我们还将其所有子节点push进队列。

14种模式解决面试算法编程题(PART II)

应用场景

  • 涉及到层序遍历树

举个栗子

  • N叉树的层序遍历(LEETCODE)

  • 二叉树的层序遍历(LEETCODE)

  • 二叉树的锯齿形层次遍历

9、树的深度优先搜索(Tree DFS)

树DFS基于深度优先搜索(DFS)技术来遍历树。Tree DFS的基本思想是使用递归(或迭代方法的堆栈)在遍历时跟踪所有先前(父)节点。从树的根开始,如果节点不是叶子,则需要做三件事:

  • 决定是立即处理当前节点(先序遍历),还是在之间处理两个子节点(中序遍历)或处理两个子节点之后(后序遍历)。

  • 为当前节点的两个子节点进行两次递归调用来处理它们。

    14种模式解决面试算法编程题(PART II)

应用场景

  • 涉及树的先序、中序或者后续遍历问题

  • 如果问题涉及搜索节点离叶子更近的目标

举个栗子

  • 求根到叶子节点数字之和(LEETCODE)

  • 二叉树的最大深度(LEETCODE)

  • 从中序与后序遍历序列构造二叉树(LEETCODE)

  • 路径总和系列(LEETCODE)

10、Subset

大量的编程面试问题涉及处理一组给定元素的排列和组合。Subsets模式描述了一种有效的广度优先搜索(BFS)方法来处理所有这些问题。

例如给定一个数组 [1, 5, 3]

  • 首先初始化一个空数组: [[ ]]

  • 将第一个数字(1)添加到所有现有子集,以创建新的子集: [[], [1]]

  • 继续添加 [[], [1], [5], [1, 5]]

  • [[], [1], [5], [1, 5], [3], [1, 3], [5, 3], [1, 5, 3]]

    14种模式解决面试算法编程题(PART II)

应用场景

  • 需要找到给定集合的组合或排列的问题

举个栗子

  • 子集系列(LEETCODE)

  • 字母大小写全排列(LEETCODE)

  • 列举单词的全部缩写(LEETCODE)

  • 单词子集(LEETCODE)

11、Modified binary search

无论何时给定 排序 数组,链表或矩阵,并要求查找某个元素,你可以使用的最佳算法是二分搜索。此模式描述了处理涉及二分搜索的所有问题的有效方法。

二分搜索这么经典的思路我就不多介绍啦,直接看一个可视化复习一下

14种模式解决面试算法编程题(PART II)

举个栗子

  • 搜索旋转排序数组(LEETCODE)

  • 寻找两个有序数组的中位数(LEETCODE)

  • 寻找旋转排序数组中的最小值(LEETCODE)

12、Top K

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

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

  • 根据问题将'K'元素插入到最小堆或最大堆中;

  • 迭代剩余的数字,如果找到一个比堆中的数字大的数字,则删除该数字并插入较大的数字

    14种模式解决面试算法编程题(PART II)

应用场景

  • 要求找到给定集合的最大/最小/频繁“K”元素;

  • 要求对数组进行排序以找到确切的元素

举个栗子

  • 前K个高频元素(LEETCODE)

  • 前K个高频单词(LEETCODE)

  • 第k个排列(LEETCODE)

13、K-way Merge

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

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

14种模式解决面试算法编程题(PART II)

应用场景

  • 适用于排序的数组,列表或矩阵

  • 问题要求合并排序列表,在排序列表中查找最小元素等

举个栗子

  • 合并两个有序链表(LEETCODE)

  • 合并K个排序链表(LEETCODE)

  • 丑数系列(LEETCODE)

14、Topological sort

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

  • 初始化。

    • a)  使用散列映射将图存储在邻接表中

    • b) 要查找所有sources,使用HashMap维护入度的计数

  • 建立图并找出所有顶点的入度

    • a) 从输入构建图形并填充内部HashMap

  • 查找所有的sources

    • 所有入度为“0”的节点被认为是source,并存入队列中

  • 排序

    • 将其添加到已排序列表中

    • 从图中获取它的所有子结点

    • 将每个子节点的入度减一

    • 如果某个子节点的入度为“0”,则将其加入队列中

    • 对于每一个source,do:

    • 重复上述步骤直到队列为空

14种模式解决面试算法编程题(PART II)

应用场景

  • 需要处理没有定向循环的图

  • 要求按排序顺序更新所有对象

  • 如果有一组遵循特定顺序的对象

举个栗子

  • 课程表系列(LEETCODE)

  • 矩阵中的最长递增路径(LEETCODE)

  • 序列重建(LEETCODE)

---

本文主要参考: 14 Patterns to Ace Any Coding Interview Question

https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed

本文由作者投稿并且原创授权AINLP首发于公众号平台,点击'阅读原文'直达原文链接,欢迎投稿,AI、NLP相关即可。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python金融大数据分析

Python金融大数据分析

[德] 伊夫·希尔皮斯科 / 姚军 / 人民邮电出版社 / 2015-12 / CNY 99.00

唯一一本详细讲解使用Python分析处理金融大数据的专业图书;金融应用开发领域从业人员必读。 Python凭借其简单、易读、可扩展性以及拥有巨大而活跃的科学计算社区,在需要分析、处理大量数据的金融行业得到了广泛而迅速的应用,并且成为该行业开发核心应用的首选编程语言。《Python金融大数据分析》提供了使用Python进行数据分析,以及开发相关应用程序的技巧和工具。 《Python金融大......一起来看看 《Python金融大数据分析》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具