Skip to content

编码面试的矩阵备忘单

原文:https://www.techinterviewhandbook.org/algorithms/matrix/

简介

矩阵是一个二维数组。涉及矩阵的题通常与动态规划遍历有关。

矩阵可以用来表示图形,其中每个节点是矩阵上的一个单元,它有 4 个邻居(除了边和角上的那些单元)。本页将集中在不使用矩阵作为图表的问题。旨在将矩阵用作图表的问题可在图表部分找到。

拐角情况

  • 空矩阵。检查所有数组的长度都不是 0
  • 1 x 1 矩阵
  • 只有一行或一列的矩阵

技巧

创建一个空的 N×M 矩阵

对于涉及遍历或动态编程的问题,您几乎总是希望复制一个具有相同大小/维数的矩阵,该矩阵被初始化为空值,以存储已访问的状态或动态编程表。在你选择的语言中熟悉这样一个惯例:

这可以在 Python 中用一行代码轻松完成。

# Assumes that the matrix is non-empty  zero_matrix =  [[0  for _ in  range(len(matrix[0]))]  for _ in  range(len(matrix))] 

在 Python 中复制矩阵是:

copied_matrix =  [row[:]  for row in matrix] 

转置一个矩阵

矩阵的转置是通过将矩阵的行交换成列或者将列交换成行来实现的。

很多基于网格的游戏都可以建模成一个矩阵,比如井字游戏、数独、纵横字谜、Connect 4、战舰等。被要求验证游戏获胜条件的情况并不少见。对于像井字游戏、连接 4 和纵横字谜这样的游戏,验证必须垂直和水平进行,一个技巧是编写代码来验证水平单元的矩阵,转置矩阵,并重用水平验证的逻辑来验证最初的垂直单元(现在是水平的)。

在 Python 中转置矩阵很简单:

transposed_matrix =  zip(*matrix) 

基本问题

如果你在学习这个话题,这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 19 个小时的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 结账→



回到顶部