leetcode hot100(矩阵)模块题解（73.矩阵置零54.螺旋矩阵48.旋转图像...）
前言：本文适合初入算法题的前端学习者（语言使用javascript）。我也是刚开始刷hot100不久，算法天赋极低，经常一道题写1个多小时也写不出来....给出的算法题解在空间复杂度层面不一定是最优解，只是选择了易于自己理解的方法进行整理
首先需要明白什么是矩阵
这张图翻译成矩阵表示就是-->[[1,2,3],[4,5,6],[7,8,9],]
显然：arr[m][n]--->m表示第几行，n表示第几列列，所以m表示行数，n表示列数
所以行的长度和列的长度很多题目都会用到的，可以在最开始写出来
const [m,n] = [matrix.length,matrix[0].length]
73.矩阵置零
题目描述
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231<= matrix[i][j] <= 231- 1
解题思路
第一步：输入-->联系-->输出-->提示，摸清题意
- 输入：number[][]（矩阵）
- 联系：0元素所在的行和列都设置为0
- 输出：number[][]（矩阵）
- 提示：对于矩阵10^2数量级意味着允许O(m*n)的复杂度，实际上还是等效于O(n)
第二步：合适示例遍历分析
很直观，无需遍历
第三步：提问法思索算法
算法也很清晰：
1.记录需要变成0的行和列
2.遍历根据记录进行修改
第四步：思考解题步骤，完成粗解
var setZeroes = function(matrix) {
//获取二维数组的行和列的长度
const rowlen = matrix.length
const collen = matrix[0].length
//用集合记录需要变成0的行和列
const rowsSet = new Set()
const colsSet = new Set()
//循环遇到0就把对应的行和列记录下来
for(let i =0;i<rowlen;i++){
for(let j=0;j<collen;j++){
if(matrix[i][j]===0){
//记录
rowsSet.add(i)
colsSet.add(j)
}
}
}
//根据记录的集合把对应的元素变为0
for(let i=0;i<rowlen;i++){
for(let j=0;j<collen;j++){
//如果记录的列或者行能对应上，则变为0
if(rowsSet.has(i)||colsSet.has(j)){
matrix[i][j]=0
}
}
}
};
第五步：检查边界条件和特殊用例
还能简化，后续再优化成空间复杂度O（1）
练习1：重述思路（1-3天）
练习2：根据提示进行填充（1-3天）
var setZeroes = function(matrix) {
//获取二维数组的行和列的长度
//用集合记录需要变成0的行和列
//循环遇到0就把对应的行和列记录下来
//记录
//根据记录的集合把对应的元素变为0
//如果记录的列或者行能对应上，则变为0
};
练习3:上leetcode重写一遍（1周）
54.螺旋矩阵
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
解题思路
第一步：输入-->联系-->输出-->提示，摸清题意
- 输入：number[][]（矩阵）
- 联系：按照顺时针螺旋把矩阵的元素取出放到数组中
- 输出：number[]
- 提示：复杂度O(mn)
第二步：合适示例遍历分析
示例同样非常清晰
第三步：提问法思索算法
如何进行遍历呢？--->有什么规律吗？
思路：
每次遍历一圈，遍历完毕就向内部收缩
最后还会剩余一行或者一列，我们再进行特殊处理，这同样也是遍历的结束条件
第四步：思考解题步骤，完成粗解
var spiralOrder = function(matrix) {
//声明输出
const ans = []
//获取上下左右四个角
let top = 0
let bottom = matrix.length -1
let left = 0
let right = matrix[0].length -1
//只要能构成环，就进行一次螺旋遍历，然后再缩圈(如图)
while(bottom>top&&right>left){
//遍历top
for(let i=left;i<right;i++){ans.push(matrix[top][i])}
//遍历right
for(let i=top;i<bottom;i++){ans.push(matrix[i][right])}
//遍历bottom
for(let i=right;i>left;i--){ans.push(matrix[bottom][i])}
//遍历left
for(let i=bottom;i>top;i--){ans.push(matrix[i][left])}
//更新
top++
left++
right--
bottom--
}
//此时可能会剩下一行或者一列，需要单独处理
//剩下一行
if(top==bottom){
for(let i=left;i<=right;i++){
ans.push(matrix[top][i])
}
//剩下一列
}else if(left==right){
for(let i=top;i<=bottom;i++){
ans.push(matrix[i][left])
}
}
//返回输出
return ans
};
问题1：while循环的结束条件是什么？
问题2：这四个for循环的条件是什么？
问题3:如何处理最后的边界条件？
练习：力扣重新写
48.旋转图像
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
解题思路
第一步：输入-->联系-->输出-->提示，摸清题意
- 输入：number[][]（n*n的矩阵）
- 联系：输入矩阵顺时针旋转90度变成输出
- 输出：number[][]（矩阵）
- 提示：O(n^2)的时间复杂度
第二步：合适示例遍历分析
从示例1中我们可以看出，最外圈的每个元素都是移动了2次，如果是4x4的话，最外圈应该每个元素移动3次，向内递减，中间不动
第三步：提问法思索算法
怎么样移动才能使元素移动到正确位置呢？
答：先上下互换，再对角互换，如图：
第四步：思考解题步骤，完成粗解
var rotate = function(matrix) {
//获取长度
const n = matrix.length
//水平中轴线反转
//行数等于n的一半向下取整
for(let i=0;i<Math.floor(n/2);i++){
//列数全部遍历，等于n
for(let j=0;j<n;j++){
//n-i-1可以举例特殊值得出，比如n=3,那i=0需要对应一个2，因为1为中轴线，0对称过去为2，代入就可以得到要+1
//这里使用了解构赋值，避免使用新的变量，更加简洁
[matrix[i][j],matrix[n-i-1][j]] = [matrix[n-i-1][j],matrix[i][j]]
}
}
//主对角线反转
for(let i=0;i<n;i++){
//同样以3举例，我们需要遍历的是4,1,2，7不能遍历到，因此取j<i
for(let j=0;j<i;j++){
//行列互换即可对称过去，就跟数学中坐标关于y=x对称的变换公式是一样的，因为你可以把矩阵的坐标系想象成左上角为原点，向右向下射线为坐标轴的坐标系
[matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]]
}
}
};
第五步：检查边界条件和特殊用例
粗解已经正确
练习1：说出思路（1-3天）
练习2：说出中轴线反转和主对角线反转的具体实现（1-3天）
练习3:上leetcode重写一遍（1周）
240.搜索二维矩阵
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109<= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109<= target <= 109
解题思路
第一步：输入-->联系-->输出-->提示，摸清题意
- 输入：number[][]（m*n的矩阵）
- 联系：根据输入矩阵，搜索目标值
- 输出：boolean（布尔值）
- 提示：复杂度小于O(m*n)。矩阵不为空
第二步：合适示例遍历分析
示例1很清晰了
第三步：提问法思索算法
如何能找到目标值呢？
答：不妨从右上角开始遍历找找规律，如果比目标值大，那说明要变小一些，可以往左走，反之，大则往右走
第四步：思考解题步骤，完成粗解
这样算法就很清晰了，从右上角开始遍历到出界即可。
var searchMatrix = function(matrix, target) {
//获取长度
const [m,n]=[matrix.length,matrix[0].length]
//获取起始坐标
let [i,j] = [0,n-1]
//只要不出界就一直找
while(i<m&&j>0){
//找到了直接返回true
if(matrix[i][j]==target){return true}
//小的话就向下移动变大
else if(matrix[i][j]<target){i++}
else{j--}
}
//运行到这里说明没找到，返回false
return false
};
第五步：检查边界条件和特殊用例
运行出错了，发现j的条件判断有问题，j应该等于0的不然会错过一列
所以应该是while(i<m&&j>=0),这样就对了
