零、写在前面

  上一节 《算法零基础100讲》(第2讲) 数列 主要讲解的是数列，也就是程序中的一维数组；那么这一节要讲解的矩阵，就是程序中的二维数组。多了一维，情况是不是会复杂许多呢？说复杂也不复杂，但是说简单，也不简单。理解问题的本质最重要，让我们来看下以下一些关于矩阵的概念吧。如果还有不清楚的，可以顺便复习一下大学的一门课程 《线性代数》。

一、概念定义

1、矩阵的定义

  矩阵 $A_{n \times m}$ 的定义是按照长方阵列排列的复数或实数集合，其中 $n$ 代表行数， $m$ 代表列数。如下所示，代表的是一个 $4 \times 3$ 的矩阵

$$A_{4 \times 3} = \left[ \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\1 & 0 & 0 \end{matrix} \right]$$

  在C语言中，我们可以用A[n][m]来代表一个 $n \times m$ 的矩阵，其中A[i][j]代表矩阵第 $i$ 行，第 $j$ 列的值。

2、矩阵的水平翻转

  矩阵的水平翻转，就是将矩阵的每一行的元素进行逆序，矩阵 $A_{4 \times 3}$ 水平翻转后的结果如下所示：

$$A'_{4 \times 3} = \left[ \begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\0 & 0 & 1 \end{matrix} \right]$$

3、矩阵的垂直翻转

  矩阵的垂直翻转，就是将矩阵的每一列的元素进行逆序，矩阵 $A_{4 \times 3}$ 水垂直翻转后的结果如下所示：

$$A''_{4 \times 3} = \left[ \begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \right]$$

4、矩阵的顺时针旋转

  矩阵的顺时针旋转 90 度，顾名思义，就是绕着垂直屏幕向里的方向，对矩阵进行 90度旋转，这时候行列会交换，所以矩阵 $A_{4 \times 3}$ 顺时针90度旋转后的结果如下所示：

$$A'''_{3 \times 4} = \left[ \begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} \right]$$

5、矩阵的逆时针旋转

  矩阵的逆时针旋转 90 度，我们可以理解成 顺时针旋转 270 度，所以就是做 3 次顺时针旋转 90 度的操作。

6、矩阵的转置

  矩阵的转置，就是对矩阵的主对角线对称的元素进行交换的操作，矩阵 $A_{4 \times 3}$ 转置的结果如下：

$$A_{T3 \times 4} = \left[ \begin{matrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} \right]$$

二、题目描述

   给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转：就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 $[1, 1, 0]$ 的结果是 $[0, 1, 1]$。
反转图片：就是将图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 $[0, 1, 1]$ 的结果是 $[1, 0, 0]$。

三、算法详解

  算法本身的实现较为简单，对于一个 $n \times m$ 的矩阵，遍历矩阵的每一行，然后对这一行单独处理，逆序以后，再取反（0变1,1变0）。
  大致代码实现如下：

int i, j;
for(i = 0; i < n; ++i) {                 // (1)
    for(j = 0; j < m; ++j) {             // (2)
        tar[i][j] = 1 - src[i][m-1-j];   // (3)
    }
}

• $(1)$ 第一步代表遍历矩阵的每一行，总共 $n$ 行；
• $(2)$ 第二步代表遍历矩阵的每一列，总共 $m$ 列；
• $(3)$ src代表源矩阵，tar代表 翻转+反转 后的矩阵，我们可以把两步合在一起做，先逆序 ，再用 1 去减，从而实现取反。

四、源码剖析

  本来这个问题的代码可以很短，但是在 LeetCode 上用 c语言 刷题的话，对于二维数组的理解成本较高，如果只是为了对算法有更深入的理解，这里建议用 c++ 的 vector 来代替，会更好理解一点。
  不过，我这边的源码剖析还是会采用 c语言 来进行讲解。

int** flipAndInvertImage(int** image, int imageSize, int* imageColSize, int* returnSize, int** returnColumnSizes){
    int i, j, col;
    int **ret = (int **)malloc( sizeof(int *) * imageSize );        // (1)
    *returnColumnSizes = (int *)malloc( sizeof(int) * imageSize );  // (2)
    for(i = 0; i < imageSize; ++i) {
        col = imageColSize[i];                                      // (3)
        ret[i] = (int *)malloc( sizeof(int) * col );                // (4)
        (*returnColumnSizes)[i] = col;                              // (5)
        for(j = 0; j < col; ++j) {
            ret[i][j] = 1 - image[i][ col-1-j ];                    // (6)
        }
    }
    *returnSize = imageSize;                                        // (7)
    return ret;                                                     // (8)
}

• $(1)$ 利用malloc函数申请一个二维数组，第一维的长度为 imageSize，第二维则又是一个一维数组，所以类型为int *，二维数组首地址为ret；
• $(2)$ 为这个二维数组的第二维申请一个数组来记录它第二维的长度；
• $(3)$ 二维数组的第二维的长度为flipAndInvertImage函数传参进来的值，用临时变量col进行存储；
• $(4)$ 申请二维数组第二维的内存空间，并且第二维的长度为col；
• $(5)$ 二维数组的第二维的长度需要作为返回值返回，所以需要给(*returnColumnSizes)这个数组的每个元素进行赋值；
• $(6)$ 按照题意进行水平翻转后取反；
• $(7)$ *returnSize是需要返回的二维数组的第一维的长度；
• $(8)$ 返回二维数组首地址；

五、推荐专栏

六、习题练习

请参考原文