JS版数据结构第四篇(矩阵)

本篇博客参考银国徽老师的《Javascript版数据结构与算法》

背景

其实从严格意义上来讲矩阵不能算一种典型的数据结构

而之所以把矩阵放到这个系列里面是因为矩阵在面试和笔试中是非常高频出现的

今天我们将会用js实现两道LeetCode上两道比较经典的矩阵相关的算法题

矩阵的定义对于大学学习过《线性代数》这门课程的同学们来讲应该都不会很陌生，如果有同学不了解可以自行查下百度百科。

不多废话,我们直接看题。

螺旋矩阵

LeetCode第54题原题地址

题目难度: 中等

题目描述:

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]复制代码

示例2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]复制代码

题目理解:

题目要求的是我们按照顺时针的顺序从外向内遍历每一个元素,并将他们按顺序返回出来。

根据这张图我们应该很清除的理解题目的要求了,题目要求的元素的返回顺序就是图中的1到16

思路分析:

我们可以注意到:

无论是几×几的矩阵,都是需要我们先将外圈遍历完成后才进入到它相邻内圈元素的遍历

如上图中我们将1-12看作第一圈,将13-16看作第二圈,第一圈全部遍历完成后才会遍历第二圈

如果有阶数更高的矩阵(更多圈数),还会有第三圈,第四圈的遍历

所以我们可以把每一圈的遍历视为一个步骤,不断地重复这个步骤就会得到我们需要的结果

相信有一些同学已经猜出我们要用递归解决这道题目了

接下来我们看一下代码具体是怎样实现的

代码实现

arr => {
    // map函数用来完成当前矩阵最外一圈的遍历
    // @param1{Array}二维数组 arr 表示当前矩阵
    // @param2{Array}一维数组 result 用来保存遍历结果  
    let map = (arr, result) => {
        // 矩阵的高度即行数
        let n = arr.length
        // 遍历矩阵的每一行
        for(let i = 0; i < n; i++){
            // 若第一行 按顺序插入
            if(i === 0){
                result = result.concat(arr[i])
            } else if (i === n-1){
                // 若最后一行 倒序插入
                result = result.concat(arr[i].reverse())
            } else {
                // 若中间行 插入该行最后一个元素 并将该元素从矩阵中删除
                result.push(arr[i].pop())
            }
        }
        // 将已经遍历的第一行和最后一行从矩阵中删除
        arr.pop()
        arr.shift()
        // 遍历插入最左侧一列 此时删除首位两行后矩阵高度已变为n-2
        for(let j = n - 3; j >= 0; j--){
            // 避免arr[j]长度为空时插入undefined
            if(arr[j].length){
                result.push(arr[j].shift())
            }
        }
        // 截止条件 矩阵有元素就继续递归
        if(arr.length){
            // 把已将遍历元素删除的矩阵进行递归
            return map(arr, result)
        }else{
            return result
        }
    }
    // 将初始矩阵传入, 保存结果的数组初始为空
    return map(arr, [])
}复制代码

思考

可能有些同学不太清除我们是怎样想到通过递归解决这样的问题。

这里根据个人的一些经验 我总结了一下满足递归的三个通用条件:

• 可以将一个操作拆解为处理过程相同的小步骤
• 每次步骤的输入数据格式都相同
• 运行次数未知

在这个题目中

• 首先我们将顺时针螺旋遍历拆解为每一圈的遍历
• 我们最开始接收一个二维数组(矩阵),每次遍历完成一圈后传入删除最外圈元素的新矩阵,它同样是一个二维数组
• 递归直到矩阵为空(传入的矩阵宽高并不确定)

符合了递归的三个条件。

大家今后碰到类似的题目就可以参照这三点来判断是否可以使用递归。

旋转图像

LeetCode第48题原题地址

题目难度:中等

题目描述

给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。

说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。

请不要使用另一个矩阵来旋转图像。

示例1:

给定 matrix =

[

[1,2,3], 

[4,5,6], 

[7,8,9] 

], 

原地旋转输入矩阵，使其变为: 

[

[7,4,1], 

[8,5,2], 

[9,6,3] 

]

示例2:

给定 matrix =

[

[ 5, 1, 9,11],

[ 2, 4, 8,10],

[13, 3, 6, 7],

[15,14,12,16]

]

原地旋转输入矩阵，使其变为: 

[

[15,13, 2, 5],

[14, 3, 4, 1],

[12, 6, 8, 9],

[16, 7,10,11]

]

题目理解

题目很好理解,直接将矩阵顺时针旋转,有点类似于我们平时使用的将图片顺时针旋转90度的功能

而这个题目之所以叫做'旋转图像'也正是因为这道题目的实现方法就是图片旋转功能的原理。

思路分析

表面上看这道题很简单,我们只需要建立一个新的矩阵(二维数组),然后遍历原矩阵matrix的每一

列,按照从下到上的顺序添加至新矩阵的每一行中即可。

但是这道题的难度就在于题目中要求我们“原地旋转图像”,这意味着我们不可以新建一个二维数

组(矩阵),然后向里面添加数据,我们只能处理原矩阵,那处理原矩阵的话我们除了将数字交换位置

以外并没有其他的方法了。

那具体怎样交换呢?

以示例1为例,首先我们以中间行为轴,将矩阵进行轴对称

然后我们再以对角线753作为轴进行轴对称

此时就得到了我们想要的结果,接下来我们用代码实现它

代码实现

arr => {
    // 获取矩阵阶数
    let n = arr.length
    let temp
    // 垂直翻转 考虑n的奇偶
    for(let i = 0; i < Math.floor(n / 2); i++){
        for(let j = 0; j< n; j++){
            temp = arr[i][j]
            arr[i][j] = arr[n -1 -i][j]
            arr[n -1 -i][j] = temp
        }
    }
    // 沿对角线反转
    for(let p = 0;p < n - 1; p++){
        for(let q = p + 1; q < n; q++){
            temp = arr[p][q]
            arr[p][q] = arr[q][p]
            arr[q][p] = temp
        }
    }
    return arr
}复制代码

总结

LeetCode上面也有很多有关矩阵的题目,大家都可以去尝试着做一下,如果对我的方法有疑问也欢迎大家来评论区探讨,多交流才会有所进步,希望你早日成为大牛。