34.md

# 编码面试的矩阵备忘单

> 原文：<https://www.techinterviewhandbook.org/algorithms/matrix/>

<header>

## 简介[](#introduction "Direct link to heading")

矩阵是一个二维数组。涉及矩阵的题通常与[动态规划](/algorithms/dynamic-programming/)或[图](/algorithms/graph/)遍历有关。

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

## 拐角情况[](#corner-cases "Direct link to heading")

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

## 技巧[](#techniques "Direct link to heading")

### 创建一个空的 N×M 矩阵[](#creating-an-empty-n-x-m-matrix "Direct link to heading")

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

这可以在 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) 
```

## 基本问题[](#essential-questions "Direct link to heading")

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

*   [设置矩阵零点](https://leetcode.com/problems/set-matrix-zeroes/)
*   [螺旋矩阵](https://leetcode.com/problems/spiral-matrix/)

## 推荐练习题[](#recommended-practice-questions "Direct link to heading")

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

*   [旋转图像](https://leetcode.com/problems/rotate-image/)
*   [有效数独](https://leetcode.com/problems/valid-sudoku/)

## 推荐课程[](#recommended-courses "Direct link to heading")

### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)

### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式，而不是背答案！** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)

### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")

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

</header>