螺旋矩阵

2020-12-07 19:34:12 张越

螺旋矩阵I

题目

``````

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

思路

left --转向--> bottom --转向--> right --转向--> top --转向--> left

1. 超出边界时转向
2. 运动到已经添加的结果数组的坐标时转向（使用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)) {
} 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

``````

[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]``````

解答

``````/**
* @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

思路

1. 对于前3次转向（从bottom方向开始），都是在坐标移动2个长度后转向
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
};
``````

https://segmentfault.com/a/1190000038404402