前言
螺旋矩阵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
};
发表回复