前言
螺旋矩阵I,II,III的题解。三道题均应用模拟法解决。
螺旋矩阵I
题目
给定一个蕴含 m x n 个元素的矩阵（m 行, n 列），请依照顺时针螺旋程序，返回矩阵中的所有元素。示例 1:输出:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]输入: [1,2,3,6,9,8,7,4,5]思路
从终点坐标[0,0]开始登程，顺时针遍历分为四个方向，方向的变动如下：
left --转向--> bottom --转向--> right --转向--> top --转向--> left
在left方向静止时，坐标的变动，x逐步自增1，y不变
在bottom方向静止时，坐标的变动，x不变，y逐步自增1
在right方向静止时，坐标的变动，x逐步自减1，y不变
在top方向静止时，坐标的变动，x不变，y逐步自减1
这道题目的要害是如何转向
- 超出边界时转向
- 静止到曾经增加的后果数组的坐标时转向（应用hash记录那些坐标以及增加到了后果数组）
解答
/** * @param {number[][]} matrix * @return {number[]} */var spiralOrder = function(matrix) { const w = matrix[0].length; const h = matrix.length; const total = w * h; const hash = {}; const result = []; let direction = 'left'; let x = 0; let y = 0; const isOutOfBounds = (x, y) => { if ( x >= w || y >= h || x < 0 || y < 0 || hash[`${x},${y}`] ) { return true; } return false; } const left = (x, y) => { direction = 'left' const nextX = x + 1; const nextY = y; if (isOutOfBounds(nextX, nextY)) { return bottom(x, y) } else { return [nextX, nextY] } } const bottom = (x, y) => { direction = 'bottom' const nextX = x; const nextY = y + 1; if (isOutOfBounds(nextX, nextY)) { return right(x, y) } else { return [nextX, nextY] } } const right = (x, y) => { direction = 'right' const nextX = x - 1; const nextY = y; if (isOutOfBounds(nextX, nextY)) { return top(x, y) } else { return [nextX, nextY] } } const top = (x, y) => { direction = 'top' const nextX = x; const nextY = y - 1; if (isOutOfBounds(nextX, nextY)) { return left(x, y) } else { return [nextX, nextY] } } for (let i = 0; i < total; i++) { let item = matrix[y][x]; hash[`${x},${y}`] = true; result.push(item); // 防止有限递归 if (i < total - 1) { let nextX, nextY switch (direction) { case 'left': [nextX, nextY] = left(x, y); break; case 'bottom': [nextX, nextY] = bottom(x, y); break; case 'right': [nextX, nextY] = right(x, y); break; case 'top': [nextX, nextY] = top(x, y); break } x = nextX; y = nextY; } } return result;};螺旋矩阵II
给定一个正整数 n，生成一个蕴含 1 到 n2 所有元素，且元素按顺时针程序螺旋排列的正方形矩阵。示例:输出: 3输入:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]思路
思路和螺旋矩阵I统一，只是这次从遍历二维数组，改为了生成二维数组。
解答
/** * @param {number} n * @return {number[][]} */var generateMatrix = function(n) { if (n === 0) { return [] } if (n === 1) { return [[1]] } const w = n; const h = n; const hash = {}; const result = []; let direction = 'left'; let x = 0; let y = 0; for (let i = 0; i < n; i++) { result.push([]) } const isOutOfBounds = (x, y) => { if ( x >= w || y >= h || x < 0 || y < 0 || hash[`${x},${y}`] ) { return true; } return false; } const left = (x, y) => { direction = 'left' const nextX = x + 1; const nextY = y; if (isOutOfBounds(nextX, nextY)) { direction = 'bottom' return [x, y + 1] } else { return [nextX, nextY] } } const bottom = (x, y) => { direction = 'bottom' const nextX = x; const nextY = y + 1; if (isOutOfBounds(nextX, nextY)) { direction = 'right' return [x - 1, y] } else { return [nextX, nextY] } } const right = (x, y) => { direction = 'right' const nextX = x - 1; const nextY = y; if (isOutOfBounds(nextX, nextY)) { direction = 'top' return [x, y - 1] } else { return [nextX, nextY] } } const top = (x, y) => { direction = 'top' const nextX = x; const nextY = y - 1; if (isOutOfBounds(nextX, nextY)) { direction = 'left' return [x + 1, y] } else { return [nextX, nextY] } } for (let i = 1; i <= n ** 2; i++) { const item = i; hash[`${x},${y}`] = true; result[y][x] = item; if (i < n ** 2) { let nextX, nextY switch (direction) { case 'left': [nextX, nextY] = left(x, y); break; case 'bottom': [nextX, nextY] = bottom(x, y); break; case 'right': [nextX, nextY] = right(x, y); break; case 'top': [nextX, nextY] = top(x, y); break } x = nextX; y = nextY; } } return result;};螺旋矩阵III
思路
本题仍然应用模拟法解决，只是转向的边界判断有所扭转。
咱们首先将原点坐标push进入后果数组中，而后从bottom方向开始遍历（方向的变动：bottom -> right -> top -> left -> bottom )。在四个方向上x，y坐标变动的法则和螺旋矩阵I统一。咱们次要是须要找到转向的法则。
通过上图，能够得出两个论断：
- 对于前3次转向（从bottom方向开始），都是在坐标挪动2个长度后转向
- 之后的转向，都是坐标静止3 + n个长度后转向（n初始等于0）。当转向的次数每累计2次后，n须要自增1
解答
/** * @param {number} R * @param {number} C * @param {number} r0 * @param {number} c0 * @return {number[][]} */var spiralMatrixIII = function(R, C, r0, c0) { const total = R * C const result = [] let current = 0 let turnsNumber = 1; // 每距离2次转弯的时候，边长须要加1（然而前3次都是2，3次之后是这个法则） let direction = 'bottom' // left -> bottom -> right -> top -> left 方向变动的程序 let sideLength = 2; let x = c0; let y = r0; // 判断坐标是否非法 const isLegal = () => { if (x < 0 || y < 0 || x >= C || y >= R) { return false; } else { current += 1; return true; } } // 首先尝试增加终点的坐标 if (isLegal()) { result.push([y, x]) x = x + 1; y = y; } const calculateSideLength = () => { if (turnsNumber <= 3) { sideLength = 2 } else { sideLength = 2 + Math.ceil((turnsNumber - 3) / 2) } } const left = () => { let num = 0; while (num < sideLength) { if (isLegal()) { result.push([y, x]); } num += 1; if (num < sideLength) { x = x + 1; y = y; } } direction = 'bottom' x = x; y = y + 1; } const bottom = () => { let num = 0; while (num < sideLength) { if (isLegal()) { result.push([y, x]); } num += 1; if (num < sideLength) { x = x; y = y + 1; } } direction = 'right' x = x - 1; y = y; } const right = () => { let num = 0; while (num < sideLength) { if (isLegal()) { result.push([y, x]); } num += 1; if (num < sideLength) { x = x - 1; y = y; } } direction = 'top' x = x; y = y - 1; } const top = () => { let num = 0; while (num < sideLength) { if (isLegal()) { console.log('top', y,x) result.push([y, x]); } num += 1; if (num < sideLength) { x = x; y = y - 1; } } direction = 'left' x = x + 1; y = y; } while (current < total) { calculateSideLength(); switch (direction) { case 'left': left(); break; case 'bottom': bottom(); break; case 'right': right(); break; case 'top': top(); break; } turnsNumber += 1 } return result};