共计 4584 个字符，预计需要花费 12 分钟才能阅读完成。
前言
螺旋矩阵 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
};
正文完