js算法-矩阵

力扣73. 矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
进阶:

一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

解答1

思路1 非原地算法，
第一次遍历将值为0的横坐标与纵坐标存入表中，
第二次遍历将横坐标与纵坐标对应的行与列置为0

/**
 * 思路1 非原地算法，
 * 第一次遍历将值为0的横坐标与纵坐标存入表中，
 * 第二次遍历将横坐标与纵坐标对应的行与列置为0
 * @param matrix
 */
var setZeroes = function (matrix) {
    var s1 = new Set()
    var s2 = new Set()
    for (var i = 0; i < matrix.length; i++) {
        for (var j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] === 0) {
                s1.add(i);
                s2.add(j);
            }
        }
    }
    for (var i = 0; i < matrix.length; i++) {
        if (s1.has(i)) {
            matrix[i] = new Array(matrix[i].length).fill(0)
            continue
        }
        for (var j = 0; j < matrix[i].length; j++) {
            if (s2.has(j)) {
                matrix[i][j] = 0
            }
        }
    }
    return matrix
};

var result = setZeroes([
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
])
console.log(result)

思路2，原地算法

var setZeroes2 = function (matrix) {
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            //当前是0的话
            if (Object.is(matrix[i][j], 0)) {
                // 处理当前行，将当前行的值都赋值为-0
                // 为什么赋值为0 请查阅 https://web03.cn/notes#/notes/detail/96
                // 0与-0在Object.is不相等，且在结果中相等，避免后来判断前面已经赋值的0
                for (let k = 0; k < matrix.length; k++) {
                    if (!Object.is(matrix[k][j], 0) && k !== i) {
                        matrix[k][j] = -0
                    }
                }
                // 处理当前列，将其置0
                for (let k = 0; k < matrix[0].length; k++) {
                    if (!Object.is(matrix[i][k], 0) && k !== j) {
                        matrix[i][k] = -0
                    }
                }
            }
        }
    }
    return matrix
};

var result2 = setZeroes2([
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5]
])
console.log(result2)

螺旋矩阵Ⅰ

54. 螺旋矩阵

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

代码

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

var spiralOrder = function (matrix) {
    if (matrix.length === 0) return []
    var res = []
    var top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
    while (top <= bottom && left <= right) {
        for (var i = left; i <= right; i++) res.push(matrix[top][i])
        top++
        for (var i = top; i <= bottom; i++) res.push(matrix[i][right])
        right--
        if (top > bottom || left > right) break
        for (var i = right; i >= left; i--) res.push(matrix[bottom][i])
        bottom--
        for (var i = bottom; i >= top; i--) res.push(matrix[i][left])
        left++
    }
    return res
};

var result = spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
console.log(result)

思路: 分为上下左右四个边界，从左到右，从上到下，左(left=0)右(right=行长-1)上(top=0)下(buttom=列长-1)，通过对四条边的循环，加上判断条件进行每一圈的搜索

执行过程

while满足条件，第一遍，走遍最外圈

while满足条件，第二遍，走遍最外-1圈

螺旋矩阵 II

螺旋矩阵 II

题目
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：
输入：n = 1
输出：[[1]]

提示：
1 <= n <= 20

var generaten = function(n) {
    // 初始化矩阵
    var result = Array.from({ length: n }, () => Array(n))
    var num = 1,
        rowStart = 0, // 行首边界
        rowEnd = n - 1, // 行尾边界
        columnStart = 0, // 列首边界
        columnEnd = n - 1 // 列尾边界
    while (num <= n * n) {
        // 首行
        for (var i = columnStart; i <= columnEnd; i++) {
            result[rowStart][i] = num++
        }
        rowStart++
        // 尾列
        for (var i = rowStart; i <= rowEnd; i++) {
            result[i][columnEnd] = num++
        }
        columnEnd--
        // 尾行
        for (var i = columnEnd; i >= columnStart; i--) {
            result[rowEnd][i] = num++
        }
        rowEnd--
        // 首列
        for (var i = rowEnd; i >= rowStart; i--) {
            result[i][columnStart] = num++
        }
        columnStart++
    }
    return result
};
console.log(generaten(1))
console.log(generaten(3))

思路：与【螺旋矩阵Ⅰ】类似，其实就是它的生成过程，先初始化一个n*n的二维数组，然后通过上下左右边界依次判断，进行赋值

运行过程